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

5
votes
3answers
49 views

Stepping Number Solution Optimization

I have the following problem: The stepping number: A number is called a stepping number if every adjacent digits, except those separated by commas, differ by 1. A stepping number can't be a ...
0
votes
0answers
31 views

Calculate possible balances in piggy-bank by weight

I have solved Piggy-Bank problem on SPOJ using dynamic programming. The question asks you to get the minimum value that is possible with given weight (\$w\$) and one or more coins (\$n\$) with given ...
3
votes
0answers
24 views

Parallel MSD radix sort in Java

I have this parallel implementation of MSD radix sort, which processes the entries by one particular byte. At each byte index, it has three phases: Count the bucket sizes. Insert each entry to its ...
1
vote
0answers
13 views

MSD radix sort in Java for parallel arrays - follow-up 2

The previous and second iteration at: MSD radix sort in Java for parallel arrays - follow-up Changes: arrays[j][i] != arrays[j + 1][i] to ...
5
votes
3answers
198 views

Count cars passing in opposite directions

The problem comes from codility, whose coding problems I'm starting to enjoy as their evaluation criteria really looks at runtime. Task description A non-empty zero-indexed array ...
4
votes
1answer
43 views

MSD radix sort in Java for parallel arrays - follow-up

The previous and initial iteration at MSD radix sort in Java for parallel arrays. Changes: Entry hides both the sort key and satellite datum in private final ...
10
votes
3answers
108 views

Becoming the greatest tower builder

I am trying to learn how to write proper code in python, and stumbled upon the following problem. Bob is given a set of building blocks b, and a number ...
1
vote
0answers
50 views

Following the logic of Dijkstra's algorithm [on hold]

My code appears to like traveling 2000 miles to a place 200 miles away: ...
3
votes
3answers
109 views

Find the missing number in a array

I'm working on a personal project to practice my programming skills and I came to this problem. I tried to create a program that will find the missing number in a array. I'm looking forward to ...
1
vote
0answers
49 views

Object counting sort in Java

The counting sort for integers counts the amount of each integer, then traverses the count entries in order, and for each entry inserts the integer representing the bucket into the array as many times ...
3
votes
1answer
36 views

Getting rid of extra test during initialization of loop/recursion

I'm reluctant to ask this question. My code below works, it's intelligible, and it seems reasonably efficient. It's just that there's a trivial, nitpicky issue that's driving me crazy. The function ...
3
votes
1answer
38 views

3-way merge sort in Java

All those numerous merge sorts split the range in two halves. This is a modification that splits each range into 3 subranges. My demo suggests that 3-way merge sort is pretty efficient on large ...
11
votes
2answers
682 views

Optimize simple C++ function to minimize copying

I've been coding C for almost 20 years and figured I should learn C++. As a starting point I wrote the following trivial code to generate the powerset of a set. I'm hoping that some experienced C++ ...
2
votes
1answer
39 views

3Sum 2 Different implementations complexity

These are 2 implementations for the http://en.wikipedia.org/wiki/3SUM problem, The first one is mine. and in the second one I implemented Wiki's pseudo code. Can someone please tell me if there is a ...
6
votes
2answers
91 views

Tree traversal into List

The interview question was to traverse a tree into a list. ...
4
votes
2answers
75 views

Pairing anagrams in a string list

The task was to check for pairs of anagrams in a string list. I first sorted all the words. and looped over the letters. The interview continues with a follow-up, to do the same with limited memory. ...
5
votes
1answer
35 views

Monotone cubic interpolation

http://en.wikipedia.org/wiki/Monotone_cubic_interpolation We have implemented it using the formula from Wikipedia : ...
0
votes
0answers
40 views

A different implementation of Heap Sort

The following implementation is a bit different form the standard implementations I have read. Is it correct? ...
8
votes
1answer
221 views

Jarvis's March Convex Hull

I'm more concerned about the coding best practices and how it's written here than the actual algorithm and math. I'm concerned about stack constraints, passing arguments,..etc. If there is anything ...
4
votes
3answers
113 views

String reverse and pairing reversed words

These are questions from an interview: Reverse a string Find matching anagrams in a word list ...
4
votes
1answer
59 views

UVA 10474 - “Where is the marble?”

I have been solving the problem from UVA 10474. In this problem, there will be marbles with numbers written on them. For example suppose five marbles with numbers 50 , 43, 43, 43, 2, 90, 44. There ...
7
votes
3answers
81 views

Removing equivalent authors in a list

I have a list of authors, where seeking duplicity. The indexes of these duplicates are stored in a list of lists named duplicity. For example, at index 0 in the list duplicity is nested list, which ...
2
votes
1answer
58 views

2-opt algorithm for traveling salesman

I wrote a 2-opt algorithm to be used in a program and noticed (using profile) that the 2-opt is eating up a lot of time. I have tried a few things to make it run faster, but I am out of ideas. Any ...
2
votes
2answers
108 views

Excel-like column numbering [duplicate]

I have a working code (below) to convert a number to Excel-like (A...Z AA...AZ BA...BZ ...ZA-ZZ) column codes (headers). For ...
0
votes
3answers
62 views

Replace spaces in string

...
5
votes
2answers
118 views

Balance braces method

This is a continuation of this question, at least the first part of that question. I want to check if everything in the new code is right or if there are other way to make it better. Exercise The ...
2
votes
1answer
42 views

MSD radix sort in Java for parallel arrays

I have this MSD (most-significant digit) radix sort sorting Entry objects holding a sorting key of type long and a satellite ...
4
votes
3answers
131 views

String difference algorithm

I would like to get a feedback about the code below. Is there any way to improve its performance? Maybe you know input values that might print bad output? The idea of the code is to count unique ...
3
votes
1answer
91 views

Flood fill algorithm in Java

Doing homework, implementation of the algorithm flood fills. I'm writing a program to this guide: http://en.wikipedia.org/wiki/Flood_fill. And I have some questions: Is it normal to specify the ...
4
votes
1answer
82 views

Speed up lights-out variant solver in pure Python

I'm doing some challenges to learn new and interesting concepts, this one is about a Lights out variant, instead of toggling only the adjacent tiles, it toggles the whole row and col. It must be ...
3
votes
2answers
98 views

Finding string roots

This is the following Python code that I have coded for an algorithmic problem online. For each line of input, the goal is to find the greatest number of repeating blocks into which the string can be ...
1
vote
1answer
96 views

Graph Creation and BFS + DFS in C#

I was asked to implement a graph and BFS and DFS. Please comment. Is it understandable? Is my algorithm correct? Are there any optimizations? ...
3
votes
5answers
208 views

Evaluating Valid Date

I want to write a function which returns true if a selected date is smaller than the current date, else return false. This function is working as expected but I want to know the best possible way to ...
0
votes
0answers
17 views

Karp-Rabin String Matching in Java, Final Part

I debated about whether to make another post, since this code is getting pretty close to a form I'm satisfied with, but I'd like to put some finishing touches on it. Part 2 is here. I incorporated ...
2
votes
1answer
50 views

Natural merge sort in Java - follow-up

See the previous iteration: Natural merge sort in Java Arrays.java ...
1
vote
1answer
24 views

Compare strings by custom sort order

Each letter represent a category. Example the group with "M" Code is greater Than "I" and "C" group. "F" is the higher group Here is what I did but I wonder if there is a better way to do it. ...
1
vote
1answer
77 views

Minimum Spanning Tree using Prim's algorithm and an indexed minimum priority queue

I have written some basic implementation of a Minimum Spanning Tree using a indexed minimum priority queue. For the implementation of the Priority Queue I used Sedgewick's Tutorials. However, it seems ...
1
vote
1answer
79 views

Largest subarray with sum equal to 0

This is a typical interview question: Given an array that contains both positive and negative elements without 0, find the largest subarray whose sum equals 0. I am not sure if this will satisfy ...
3
votes
2answers
45 views

Scoring system of a pool of dice

I want to do some Monte Carlo simulations on a system based on a pool of dice. For each trial, a number of dies are rolled, and the winner is the highest value, getting as many points as dice are over ...
4
votes
2answers
76 views

Palindrome Checker Algorithm

Here is an example of how I solved this problem (though this is not the only nor the best way by any means) for an assignment where it was also requisite to determine if a string was a reverse prefix ...
2
votes
1answer
68 views

Natural merge sort in Java

Natural merge sort is a modification of merge sort that sacrifices O(N) to actually build a list of "runs" that may be defined as monotonically increasing or strictly decreasing contiguous ...
3
votes
1answer
197 views

Shortest path Dijkstra's algorithm

I'm trying to implement Dijkstra's algorithm to find the shortest path from a starting node to the last node of a 250px by 200px raw image file (e.g. starting node = [0][0], ending node = [250][200]). ...
1
vote
0answers
41 views

Using the Template Design Pattern to reduce code duplication between two algorithms

I have made a Skyline query solver which for now can solve the query with two different algorithms. The first is Block-nested loop (BNL) and the second is Sort filter skyline (SFS). The two are ...
7
votes
2answers
341 views

Counting Fermat witnesses and liars

We were asked to implement a program that calculates the number of Fermat witnesses and liars for odd numbers greater 1. This involves Fermat’s little theorem. Fermat’s little is used to identify ...
4
votes
3answers
242 views

Compute (x+yCx)%mod

I want to compute, as quickly as possible, $$ \dfrac{(x+y)!}{x!y!} \mod m $$ with \$x,y \le 10^6\$ and a prime \$m=10^9+7\$ (called mod in my code). My current ...
2
votes
3answers
65 views

Searching text for a string

This is my current code: ...
0
votes
1answer
61 views

Nearest point using 2D tree, static variable for the closest point so far

This is a problem from a Coursera class: Write a data type to represent a set of points in the unit square (all points have x- and y-coordinates between 0 and 1) using a 2D tree to support ...
0
votes
0answers
49 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 ...
9
votes
3answers
261 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
120 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 ...