Tagged Questions

An algorithm is a precise plan (in the format of a sequence of steps) on how to solve a particular problem.

learn more… | top users | synonyms

0
votes
0answers
21 views

Radix sort (LSD) and Counting sort

I'm reading CLRS, and to practice, I rolled my version of radix sort and counting sort. I was looking at some reference implementations, particularly the LSD one from rosetta code, and mine performs ...
8
votes
2answers
156 views

Finding shortest paths in directed graphs

I have very little experience in programming with C++ and the following small "program" is the 2nd one I have ever written in that language. I am most interested in comments regarding naming ...
4
votes
2answers
102 views

Testing whether a given string has unique characters

Here is my code which tests whether a given string has unique characters. The function is_unique which does a linear search for each character in the string is ...
5
votes
1answer
97 views

Codility MaxCounters Peformance in Python capping out at 77% performance

My problem is quite similar to the question found here, except I am attempting to answer the question in Python. Given an array of N counters, all initialized to 0, and an array ...
6
votes
4answers
456 views

Sum of digits in a^b

I'm trying to calculate a problem which requires sum of digits in \$a^b\$, where \$0 \le a \le 9\$ and \$0 \le b \le 4000\$. I have seen various other posts similar to this, but I haven't acquired ...
7
votes
1answer
57 views

Karp-Rabin with bitwise hash

As a Rags-to-Riches re-implementation of the Karp-Rabin question here, from @tsleyson, I thought it would be interesting to understand the algorithm better, and to use bitwise-shifting instead of ...
2
votes
0answers
46 views

Binary Index tree optimization

I have written code for binary index tree. My problem is there are many functions based on the binary index tree the function stores the sum of element within a given range of binary index tree and my ...
5
votes
3answers
67 views

Karp-Rabin String Matching, Part 2

Part 1 is here. I wrote a Java implementation of the Karp-Rabin semi-numerical string matching algorithm. I incorporated the suggestions of @fge and @maaartinus from the other question into my new ...
2
votes
2answers
73 views

Extended Euclidean algorithm and modular multiplicative inverse element

After my first exercise here is another. Again, this is exactly that: Exercise, which means that the output doesn't necessarily need to be beautifully formatted, etc. I probably have some variable ...
3
votes
2answers
108 views

Evaluating f(N,R) mod(m)

The goal is to find \$f(n,r)\mod(m)\$ for the given values of \$n\$, \$r\$, \$m\$, where \$m\$ is a prime number. $$f(n,r) = \dfrac{F(n)}{F(n-r) \cdot F(r)}$$ where $$F(n) = 1^1 \cdot 2^2 \cdot ...
2
votes
1answer
28 views

Optimize calculation of string self-similarly with its suffixes

I am trying to solve a Hacker Rank problem about string suffixes: For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. ...
5
votes
1answer
50 views

Karp-Rabin string matching in Java

I wrote an implementation of the Karp-Rabin string matching algorithm in Java 7, based on the discussion in Section 32.2 of Introduction to Algorithms (CLRS). Clearly, I need more experience with ...
1
vote
1answer
48 views

Trinary tree insertion and deletion

I have worked on the trinary tree problem insert and delete. Can anyone look at it and tell me how it is? TrinaryNode.java ...
5
votes
3answers
385 views

Building a parent/child tree relationship

I have a problem: build a tree relationship parent/child like this one: Can you review this piece of code please since I am convinced it could be improved? ...
1
vote
1answer
52 views

MinCostMaxFlow implementation is not fast enough

I'm trying to solve this problem: A root tree is a directed acyclic graph that contains one node (root), from which there is exactly one path to any other node. A root tree is binary if ...
1
vote
2answers
53 views

String color mixer [closed]

I am working on a homework assignment where we are supposed to ask the user for 2 primary colors (red, blue, and yellow). They cannot be numerical values, they must be words. It should then take the ...
3
votes
1answer
87 views

PermCheck Codility with time complexity of O(N)

I have this solution for Codility's PermCheck problem. In summary, the task is to check whether array A contains each number in \$1 \ldots N\$ exactly once. I got ...
4
votes
2answers
79 views

Rotating an array by position n

Input is 1,2,3,4,5,6,7,8 If rotateOrder = 2 Output should be 7,8,1,2,3,4,5,6 If rotateOrder = 3 Output should be 6,7,8,1,2,3,4,5 Here is my program to do it: ...
5
votes
3answers
72 views

Merging Overlapping Intervals

A while back I was asked the following question in a phone interview, and to be honest it stumped me. After many long nights of rolling the problem around in my head I think I came up with a decent ...
1
vote
0answers
56 views

Filling a cumulative array in Swift

I have a "cumulative" lookup array for a custom collection view layout. The idea is that I have an array of rectangles, each with an index. The index is not unique, and is monotonically increasing. ...
10
votes
1answer
105 views

Gray codes addition

As some of you know, I have been working with Gray codes and am trying to design a good gray_code class in modern C++. I will end up posting several parts of the ...
0
votes
1answer
80 views

Approximate integral in one line of code

This is what I came up with: Version 1: ...
3
votes
1answer
67 views

Finding a word ladder using Breadth First Search

This is a LeetCode problem called Word Ladder: Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, where only one letter can ...
2
votes
1answer
40 views

Is there an easier way to find the prime factors of a number?

I am trying to write a program which, given a number as an input, prints the prime factors AND the exponents of the prime factors of that number. Example: ...
8
votes
4answers
436 views

Computing factorials

I am computing factorials as part of teaching myself C++. I am looking for feedback on efficiency, style and any bad practices I may be using. ...
5
votes
2answers
322 views

Shell sort seems inefficient

I am testing various sorting algorithms. Right now I am testing shell sort, insertion sort and selection sort. I ran all three algorithms on a randomly-generated list of 1000 integers. The selection ...
12
votes
4answers
901 views

O(N) vs O(N * N) for Word Frequency Algorithm

I am trying to come up with a better solution to the following problem: Statement You are supposed to write a function which takes the contents of a document in string format and also a whole ...
4
votes
2answers
132 views

Getting the neighbors of a Point in a 2D grid

I am trying to find an algorithm to find all the defined neighbors of a 2D Point (efficiently would be nice, but does not make much of a difference). Here is my ...
5
votes
2answers
107 views

Finding the weight of the heaviest path in a binary tree

I'm fairly new to Java, arriving in the "future" from C and returning to type safety from Python. I've programmed an algorithm to return the weight of the heaviest path from the root of a binary tree ...
3
votes
3answers
74 views

Optimizing name highlighting

I have created a set of functions, that when given a struct of structs full of names, it will highlight those names that appear in a body of HTML based text. Is this the best method of doing this? ...
6
votes
1answer
95 views

Excel VBA binary search class module [closed]

I have a long list of sorted strings in a Workbook, and I have to find a lot of values in it. I was hoping to build a binary search Class Module that will find them for me faster than Excel's built-in ...
1
vote
0answers
27 views

Extract logic applied in a sequence of integers

I've done it in C# before but thought that a functional language would be a good fit for this kind of thing. From this ascending list of integers: [100,103,106,112,118,121] I had to calculate ...
9
votes
4answers
2k views

Brute force password cracker

I wrote this script for a proof of concept JavaScript password cracker: ...
5
votes
2answers
256 views

Tremaux Algorithm

I am trying to implement Tremaux Algorithm for a 2D maze. So far the robot works well however I have some problems with retraceStep(). I'm not asking how to ...
4
votes
0answers
34 views

Mostly portable 128 by 64 bit division

I wrote this out of curiosity. It is based on the theory behind Knuth's Algorithm D, and intended to emulate the behavior of the x86 div instruction (though the ...
10
votes
2answers
152 views

Validating a Binary Search Tree

This is an implementation of a function to check the property of a Binary Search Tree, that is: the key in any node is larger than the keys in all nodes in that node's left subtree and smaller ...
4
votes
3answers
74 views

Finding strings inside of other strings in order in C

A question on Stack Overflow recently intrigued me to the point of me implementing the functionality in C. Can you critique this algorithm and tell me what is good and bad about it? This program will ...
2
votes
1answer
46 views

Binary Search in C

The standard C library function bsearch wasn't giving me correct results, apparently. So I decided to implement a binary searching function in place of it. It ...
0
votes
2answers
90 views

Optimizing Dijkstra implementation using PriorityQueue in Java

I am trying to make Dijkstra implementation more efficient. Below is the code for class Node which implements Comparable so it ...
3
votes
1answer
60 views

Improving efficiency of Prim's Algorithm

I have implemented Prim's Algorithm in Java. I am wondering how it can be made more efficient. Below is the class Node for vertices. ...
13
votes
4answers
409 views

Array alive/dead entity “refresh” algorithm

I have an Entity class that can be either dead or alive. I store entities contiguously in a resizable array. During an ...
9
votes
2answers
110 views

Min triangle path - bottom-up

I got a bit intrigued with the recent question DP solution to min triangle path and after a certain chat message I decided that I wanted to implement my solution. Given a triangle, find the ...
6
votes
5answers
158 views

DP solution to min triangle path

I am studying for interviews for various companies. I wrote a solution to this problem, but if an experience programmer looks at it I am sure there are certain areas the code can be made in to a more ...
5
votes
1answer
43 views

Formatting database like table

The goal of my program is take some headers and fields and display a nicely formatted table like this: ...
2
votes
2answers
54 views

has_cycle in directed and undirected graphs

I wrote a program that can tell if a graph has_cycle or not. Can you please suggest more elegant and eloquent ways for this program? (Perhaps better ways to represent a graph with vertices and ...
6
votes
5answers
615 views

Given a String, return a boolean if it is a number

Yesterday in an online interview, the interviewer asked me this question: If I give you a string, you have to return if a string is number or not. You are not allowed to use any parse function ...
6
votes
3answers
201 views

Making backtracking Knight's Tours solution more efficient

This was a previous homework assignment I was required to do. While I did the assignment and turned it in for credit, I am not completely satisfied with the result I have. The rule for the assignment ...
2
votes
2answers
47 views

Collatz Conjecture in Python

The Collatz's Conjecture states that any number can either be halved (if it is even) or multiplied by three and added one to (if it is odd) and eventually reach 1. I was wondering if there was a more ...
7
votes
1answer
41 views

Joining collections… because it's fun

I'm working on a LinqEnumerable class (reviewable here), and I'm no Big-O expert and I'm pretty bad with algorithms, so I wonder what the complexity is for what ...
0
votes
0answers
106 views

Skyline problem solved by sweep line

Can you please suggest more elegant and eloquent ways for this problem? (Perhaps better ways to represent a graph with vertices and edges?) Skyline problem is described here. ...