An algorithm is a precise plan (in the format of a sequence of steps) on how to solve a particular problem.
0
votes
1answer
11 views
recursive tree traversal, lowest common ancestor, o(n) ? JAVA
LCA = Lowest Common Ancestor
The following code, finds the lowest common ancestor in tree of nodes, where a node can have two parents, left and right.
If tree looks like this :
J-K
/ \
...
12
votes
2answers
48 views
Condorcet voting method in OOP Python
I'm currently learning Python and having a great time so far (coming from PHP, I have a feeling of suddenly seeing the light).
At the same time, I'm studying voting algorithms. So, for training ...
1
vote
2answers
43 views
Produce a nearly sorted (or K sorted) array
Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time.
For example, let us consider k is 2, an element at ...
3
votes
2answers
152 views
Performing non-production analytics on data
I have the following Lua script which I use against my redis environment to perform some non-production analytics on my data.
My dataset contains hundreds of millions of records, hence I want to make ...
3
votes
2answers
45 views
Returning all the LIS of given array of int
I have this assignment where I'm supposed to code an algorithm for finding the quantity of Longest Increasing Subsequences from an array of (different) integers and print them all.
I developed one ...
3
votes
1answer
54 views
Algorithm optimization on date calculation
I need to calculate the calendar week of a given date. Constraints:
It should be properly calculated based on ISO 8601 if week starts on
Monday
It should calculate based on US standards if the week ...
2
votes
1answer
46 views
Interval search tree
An interval is a data structure that represents a range (start & end, from & to, or min & max, etc.). An Interval Tree stores these intervals in a sorted tree structure that makes ...
2
votes
1answer
41 views
Join/ connect all levels of Binary tree without any aux storage
This program connects all nodes of the binary tree at the same level. A node of a tree contains a left, right and a sibling pointer which would connect it to the next node at the same level. This ...
7
votes
3answers
95 views
Checking brackets nesting in a string
I took a training challenge on Codility that checks for the proper nesting of brackets in a string. The brackets to be checked are {,},(,),[,]. I have written the following Java program which passes ...
8
votes
1answer
107 views
Rotating greyscale images
For educational purposes I wrote a little piece of code to rotate greyscale images as "low level" as possible, that is, not using any rotate() function, but doing the math. I was wondering if it could ...
4
votes
2answers
106 views
How to improve this Needleman-Wunsch implementation in C#?
I split my implementation of this sequence alignment algorithm in three methods. Where NeedlemanWunsch-method makes use of the ScoringFunction and the Traceback methods. Further I decided to go with ...
3
votes
0answers
14 views
Review of genetic algorithm code in Erlang
I've written an Erlang implementation of the genetic algorithm for a hello world program described here: http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hello-world/
This is my first time ...
3
votes
2answers
72 views
Permutation of a string eliminating duplicates
This code lists the permutations of the string, and eliminates duplicates if any.
I'm looking for code review, best practices, optimizations etc.
Also verifying complexity: O(n! * n) as time ...
2
votes
1answer
52 views
Bloom filter implementation
Implementation of Bloom filter with add and contain functionality. I'm looking for code review, best practices, optimizations etc.
Also verifying complexity: O(1)
public class BloomFilter<E> ...
6
votes
1answer
62 views
Is this an efficient way of removing duplicate words from an unsorted list?
I was using brute force to remove duplicate words since the lists were really small. But I want a solution that won't become too slow if the input grows.
This function creates a binary tree and ...
7
votes
3answers
189 views
Sieve of Erathostenes optimization
I am making a program to find primes between the given range of numbers. Unfortunately, the algorithm I created is too slow. Do you have any ideas of how to optimize the code?
import java.io.*;
...
3
votes
1answer
46 views
Insertion sort with binary search in Python
def binary_search(A, value, start, end):
# we need to distinugish whether we should insert
# before or after the left boundary.
# imagine [0] is the last step of the binary search
# ...
0
votes
1answer
28 views
Euler Problem # 13 Code Debug [closed]
my code is compiling fine with mingw on windows
#include <iostream>
int main()
{
int maxCount[2] = {0, 0};
for(int c = 999999; c > 1; c --)
{
int n = c;
int count ...
7
votes
3answers
564 views
Shortest path algorithm is too slow [closed]
I am solving one problem with shortest path algorithm, but it is too slow.
The problem is that I have N points and these can be connected only if the distance between them is smaller or equal than ...
12
votes
5answers
1k views
Identifying first negative number in array of doubles
I was asked to create a function that checks if an array of doubles has all negative numbers or none. If these 2 (all negative, all positive) are false, check the first negative number, using ...
5
votes
1answer
72 views
Find whether a given number is a perfect square or not
I am trying to find whether a given number is a perfect square or not by using just addition and subtraction.
Please review my code.
#include<stdio.h>
int check(int);
main()
{
int N;
...
6
votes
2answers
97 views
Algorithm to return unique values from unsorted input
I need to create an efficient algorithm that returns unique values from an unsorted input. I don't know the length of the input.
As the function that will call this algorithm can abort the reading at ...
6
votes
1answer
168 views
Tower of Hanoi solver
Requesting code review, best practices, optimizations for this solution to the Tower of Hanoi problem.
final class PlatePair {
private final String source;
private final String destination;
...
3
votes
1answer
53 views
Nearest pair of points
Given a set of 2 dimensional points, it returns the two nearest points. If more pairs have the same min-distance between them, then an arbitrary choice is made. This program expects the points to be ...
3
votes
0answers
41 views
Dijkstra's and Prim's algorithms: correctness/efficiency
This is in preparation for a competition that only allows C++03.
// Neighbor index plus weight of edge connecting this vertex with neighbor
struct NeighborWeight
{
Index neighbor;
Distance ...
0
votes
1answer
35 views
Moving steps in KMP algorithm [closed]
KMP algorithm is for searching and matching string with a given pattern. The most important part is to build a table for the pattern then move a proper step rather than just one step increment.
In ...
1
vote
3answers
106 views
To check if a string C is an interleaving of A and B Code
This is my code to check if a string C is an interleaving of Strings A and B. Please suggests optimizations, and where I can improve.
#include <vector>
#include <list>
#include ...
7
votes
2answers
69 views
Is this quicksort efficient and acceptable?
In order to complete one of my assignment I needed to include a quicksort so I was wondering if this is correct and acceptable.
The code:
private ArrayList<String> ...
4
votes
1answer
39 views
Tilt maze solution
If one does not know tilt maze then the game looks like this. Basically one can travel in 4 directions North, East, South and West, but this travel's endpoint is the furthest non-obstructed block. If ...
6
votes
2answers
67 views
Draw the table like 6³ = 3³ + 4³ + 5³ to 100³ = 35³ + 70³ + 85³
I want to draw the table like this:
6³ = 3³ + 4³ + 5³
9³ = 1³ + 6³ + 8³
12³ = 6³ + 8³ + 10³
18³ = 2³ + 12³ + 16³
18³ = 9³ + 12³ + 15³
19³ = 3³ + 10³ + 18³
20³ = 7³ + 14³ + 17³
.....
100³ = 35³ + 70³ ...
2
votes
2answers
60 views
Merge Sort Algorithm in Python
Implementing basic sorting algorithms to learn them, and coding, better. Criticisms/ critiques welcome. Also possible optimizations.
import unittest
import random
def merge_sort(seq):
"""Accepts ...
7
votes
7answers
458 views
Better way to get shortest sequence
I want to get the shortest sequence to reach a number.
Rules:
A[0] is always 1
Either A[i] = A[i-1]*2 or A[i] = A[i-1]+1
For example, if my input number is 17, my output should be 6, because
...
1
vote
1answer
44 views
Reservoir sampling
Reservoir sampling implementation. Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or ...
5
votes
2answers
199 views
Algorithm to determine if a string is all unique characters
This my solution to one of the practice problems from Cracking the Coding Interview: 150 Programming Interview Questions and Solutions [Book]
implement an algorithm to determine of a string has ...
4
votes
3answers
87 views
Weighted probabilistic sampling
Problem description.
Returns strings with probability determined by the frequency
of each of the strings.
eg: if "foo" has weight of 50% and "bar" has weight of another 50% then both foo and
bar ...
4
votes
2answers
89 views
Insertion Sort Algorithm in Python
Implementing basic sorting algorithms to learn them, and coding, better. Criticisms/ critiques welcome. Also possible optimizations.
import unittest
import random
def insertion_sort(seq):
...
3
votes
1answer
100 views
Selection sort algorithm in Python
I'm learning basic algorithms and implementing them in Python. Critiques needed/welcome.
import pudb; pu.db
import random
def selection_sort(list_):
"""Implement selection_sort algorithm: iterate ...
10
votes
6answers
559 views
Help refactor this to be less procedural and more recursive
Reference: Is this a faithful rendition of the selection sort algorithm?
I'm working through an elementary book on sort and search algorithms, and writing some sample code to test my understanding. ...
7
votes
2answers
233 views
Bubble sort algorithm in Python
I'm starting to implement basic sorting algorithms. Criticisms on the implementation is welcome.
#import pudb; pu.db
def bubble_sort(list_):
"""Implement bubblesort algorithm: iterate L to R in ...
14
votes
5answers
1k views
Tic-tac-toe 'get winner' algorithm
As a first step to attempting the Weekend Challenger Reboot, I decided to first implement a regular 'tic-tac-toe' game and then expand it later to be 'ultimate tic-tac-toe'.
Below is the code for the ...
3
votes
2answers
485 views
What is the 10001st prime number?
Project Euler problem 7 says:
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?
I believe that my code is ...
7
votes
2answers
125 views
Is this non-recursive mergesort efficient and a good way to simulate the recursive version?
My teacher assigned us to do the recursive version of mergesort, yet I heard that the non-recursive version (bottom up) is a bit tougher, so I decided to this one as well. My main concerns are:
...
7
votes
2answers
323 views
Finding prime factors of a number?
Okay, so just having a little fun I thought I'd see if I could write an algorithm to find all of the prime factors of a number. The solution I came up with is as follows:
class Program
{
static ...
5
votes
3answers
86 views
Small guessing game in Ruby
I'm writing a small guessing game. I'm writing a points calculation algorithm.
I wrote the following, and it works. But I feel like I'm bringing over procedural background into Ruby, or not ...
1
vote
1answer
64 views
Determine if a std::string has all of the same character
I'm working on an algorithm to determine if a std::string has all of the same character. Here is what I have:
bool string_has_all_of_the_same_chars(const std::string& s) {
return ...
6
votes
1answer
134 views
How do I make this duplicate sort algorithm run faster?
I've written a program whose code is included at the end of the question. It is working fine but the performance time is approximately 5 minutes and 29 seconds. I am dealing with 1090 images.
This ...
0
votes
0answers
35 views
A package for sort algorithms - v4 - final [duplicate]
Addressed both issues in this codereview post.
Cached an expression and commented that removing a function call would increase performance but chose not to do so to keep the code DRY.
This is just ...
8
votes
3answers
103 views
Scrabble algorithm review and performance suggestions
After finishing Project Euler 24, I decided to make a scrabble type of application using /usr/lib/dict as my dictionary what I cat that into a word file. It does take a few seconds, and the dictionary ...
3
votes
1answer
78 views
A package for sort algorithms - v3
Addressed both issues in this codereview post.
Fixed the indexing issue and the call mechanism of the function expression.
Looking for perfect code. Hope this is the last rev.
...
6
votes
0answers
99 views
stability of an exponential moving average
I used the following code:
#include<vector>
class UltrasonicRecorder
{
public:
UltrasonicRecorder(int referenceValue, Input referenceInput) :
_referenceValue(referenceValue),
...
