An algorithm is a sequence of well-defined steps that define an abstract solution to a problem. Use this tag when your issue is related to algorithm design.
0
votes
0answers
2 views
My 15 puzzle solver is too slow
It takes my code over 700 seconds to solve simple puzzle:
2 13 14 10
7 0 1 3
11 9 8 12
5 4 6 15
My function findSolution(puzzle, minH) takes puzzle as ...
4
votes
0answers
26 views
Github pagination
I wanted to copy the behavior of github's pagination. Here is what it turned out: http://jsbin.com/dihohiseca/5/edit?js,output
It works fine, but I have a feeling that there is a lot of room for ...
1
vote
0answers
21 views
AVL tree implementation
So I've just created an AVL tree in Java. However when I test its running time using the following code:
...
0
votes
0answers
18 views
Max and min of n sets of numbers [on hold]
I am supposed to write a program in C++ which will find maximum and minimum of n sets of numbers in the following way:
The first input is a positive integer n = the number of 5-element sets of ...
1
vote
2answers
248 views
Binary tree data structure
I am learning about the binary tree data structure and implemented some basic functionality.
It was working great with module level functions until I realized that I need to keep track of the root ...
2
votes
1answer
23 views
Extract data from large JSON and find frequency of contiguous sub lists
I have been writing some code (see component parts here and here) that:
Takes a very large JSON (15GB gzipped, ~10million records)
Extracts the relevant parts of the JSON into a list of lists
...
2
votes
1answer
40 views
Shortest path from U to V using at most k nodes
I'm trying to solve a problem that asks for a shortest path between two cities with at most k nodes.
The first line of input has the number of test cases. On the second line 3 integers are given, ...
4
votes
3answers
423 views
Implementation of a sparse Markov Chain
I need to create a sparse Markov chain. It is supposed to receive text, so the number of rows or columns can easily go up to 20000. Besides, if I want to consider higher orders of the Markov chain ...
3
votes
2answers
311 views
Find the closest number to each given number
I have a program which works but it is a bit too slow with big numbers.
nbBlocs contains the size of the array, it can be up to 20000 and I enter the value inside ...
2
votes
2answers
81 views
Non-Contiguous Substrings
Problem:
A non-contiguous substring of string \$s\$ is a sequence of \$k \geq 0\$ characters in \$s\$, in the order in which they occur in \$s\$. For instance, the set of all non-contiguous ...
5
votes
1answer
37 views
Test whether target string is substring of source string
The code is self-explanatory. It has \$O(n)\$ complexity, and it tells whether a given string is the substring of the source string. Are there any cases where this algorithm fails? Is there anything ...
4
votes
4answers
224 views
Merge two list and discarding duplicates
I am trying to implement a function that merges two ordered lists into a third (ordered) one, but duplicates have to be discarded (basically the last step of a mergesort).
I think that this code can ...
2
votes
1answer
27 views
My own implementation of an hashtable
This is my own implementation of an hashtable. I would like to receive some reviews or some feedbacks.
...
6
votes
2answers
74 views
Sudoku game with varied difficulty level
I created a Sudoku game with varied difficulty level.
The Sudoku board creation process consist three stages:
Creation of an empty board
Filling the board with numbers
Making holes in the filled ...
1
vote
1answer
46 views
Check if a Binary Tree is full
Problem statement
Given a node check whether the sub-tree rooted at given node is full binary tree or not.
Definition
A full binary tree (sometimes proper binary tree or 2-tree) is a tree in ...
2
votes
3answers
60 views
Creating a tuple from a CSV file
I have written code that reads in a CSV file and creates a tuple from all the items in a group. The group ID is in column 1 of the table and the item name is in column 2. The actual datafile is ~500M ...
6
votes
4answers
196 views
Add one to a very large integer
I was asked to implement this in an interview a while back. I didn't pass the interview, mostly likely because it took me far too long to do. However, I'm interested to know how well implemented the ...
3
votes
1answer
46 views
Finding most common contiguous sub-lists in an array of lists
Objective: Given a set of sequences ( eg: step1->step2->step3, step1->step3->step5) ) arranged in an array of lists, count the number of times every contiguous sub-lists occur
Where I need your help:
...
2
votes
2answers
430 views
Efficient algorithm for counting frequency of a numbers in intervals
I need to build a bar graph that illustrate a distribution of pseudorandom numbers that determined by linear congruential method
$$X_n+1 = (a X_n + c) \mod m$$
$$U = X/m$$
on the interval [0,1]
...
2
votes
1answer
79 views
Inversion count via divide and conquer
I'm happy to hear thoughts and ideas on structure/performance/testing/whatever and multi-threading, which I haven't gotten into yet with Python.
Full code here. Assignment file and a test file ...
4
votes
1answer
62 views
Knights Tour — Something I am doing wrong
I have an assignment to write a knights tour backtracking program in Java where the professor says to:
Eliminate backtracking time by:
...
5
votes
2answers
77 views
Knuth–Morris–Pratt string match algorithm
The Knuth–Morris–Pratt string search algorithm is described in the paper Fast Pattern Matching in Strings (SIAM J. Computing vol. 6 no. 2, June 1977). The initial step of the algorithm is to compute ...
-3
votes
0answers
27 views
k permutations of n integers without repetitions [closed]
I already have code for k combinations of n elements. How can it be edited to produce k permutations of n elements without repetitions (\$0 \le k \le n\$)?
How can I make minimal changes to the exact ...
5
votes
1answer
50 views
Project Euler no. 17: Counting letters to write the numbers from 1 to 1000
I'm very new to programming and am admittedly embarrassed sharing my code for critique. This code works and produces the correct answer to the Project Euler Problem 17, which asks how many letters ...
14
votes
5answers
482 views
+100
Algorithm to transform one word to another through valid words
I have been practicing backtracking and I wanted to know how I can improve my code. For eg, I don't want to use global. Also, have I am not sure if my code will work for all the cases.
...
8
votes
4answers
390 views
Simple GCD utility in Java
I previously discussed the performance concerns about different GCD algorithms. I wrote a simple Java class that implements the Binary GCD algorithm. It is a really tiny class that has only two ...
-3
votes
0answers
24 views
Length and sum of longest increasing subsequence [closed]
I wanted to count sum and length of the longest subsequence in the given array t.
...
4
votes
1answer
42 views
Find values in list which sum to a given value within tolerance
This is really a follow on from a question I asked earlier this year on Stack Overflow. I received a great answer to the following problem:
I'm trying to code up something simple and pythonic to ...
4
votes
2answers
81 views
Sort array of Numbers with some values always first
The first number will be dynamically selected and remaining array should be sorted ascending
...
5
votes
2answers
59 views
Reorder a list in Python to avoid repeats
I am trying to check if a list has any consecutive repeating elements and then reorder it such that the repeats are avoided. If that is impossible, then return False. For example:
...
7
votes
3answers
80 views
1
vote
1answer
40 views
Array search algorithms: performance comparison
I'm making a program that compares multi-key sequential search and Interpolation search in a sorted array by the number of array accesses for my assignment.
...
4
votes
2answers
124 views
Find co-occurrence of elements
My input consists of a list of lists (not necessary of the same length), like
...
1
vote
3answers
74 views
Merging two sorted linked lists C++
Routine to merge two linked lists together and return a new merged list. One optimization I can think of is passing by reference instead of value. Any other suggestions ? Is there a shorthand to make ...
2
votes
2answers
82 views
Gluing pieces of scrambled text (challenge on CodeEval)
I'm trying to solve this challenge on CodeEval. Quoting:
For example, you can put pieces together and get the original text:
evil pl
vil pla
il plan
The answer is ‘evil plan’.
Your ...
7
votes
2answers
237 views
Generating 3 combinations in Python
I have been experimenting around with generating all the n-combinations of an array. This code quickly generates all \$\text{k-combinations}\$ of a given array. I am testing my own implementation ...
3
votes
3answers
59 views
Max and Min in array using minimum comparisons
Is this the most robust and fastest way for finding the min and max out of an array without using STL functions? How can I improve it?
...
1
vote
1answer
37 views
Kruskal's algorithm
I'm working through Coffeescript implementing simple algorithms (started with Prim's as reviewed in this previous post) and wrote out Kruskal's algorithm as below, with a few helper functions. I'd ...
4
votes
0answers
59 views
Directed graph isomorphism in Java
Given two input directed graphs \$G_1 = (V_1, A_1)\$ and \$G_2 = (V_2, A_2)\$, the problem of isomorphism asks whether the two directed graphs are isomorphic, or in other words, whether the two input ...
2
votes
0answers
32 views
Are AVL trees equal? - revision 3
The original question
Given two binary trees, return true if they are structurally
identical, and false otherwise.
Are AVL trees equal?
Are AVL trees equal? - revision 2
This revision on ...
4
votes
1answer
94 views
How to tweak Tape Equilibrium assignment on Codility to be of complexity O(N)?
Why Codility detects my solution for Tape Equilibrium to have complexity of \$O(n^2)\$. How can I make my code better?
...
3
votes
2answers
44 views
Caesar Encryption Tool
I'm newbie in Python and I wrote a tool called Caesar Encryption Tool. At the moment it only encrypts. It takes a plain text and a key from the user then encrypts the plain text using the key. How can ...
5
votes
1answer
82 views
Calculating count of square numbers between two numbers
The problem is to find out the squares between two numbers, inclusive of the numbers. The two numbers are in the range between 1 and 109.
...
2
votes
3answers
63 views
Prim's algorithm in CoffeeScript
I'm just starting to learn CoffeeScript and am trying to work through simple examples, this one being Prim's algorithm. I'd like feedback on everything but especially on making this script take ...
4
votes
3answers
126 views
Kadane's Algorithm for 2D array with known boundaries
I asked this question first on StackOverflow but I didn't get an answer and was advised to try here too. So here we go.
I have implemented Kadane's algorithm for a 2D array in Python 2 with known ...
13
votes
3answers
165 views
What kind of Wall should it be? (for an RPG)
I'm creating an RPG type game, and now I am working on procedural town generation. The algorithm for that creates some roads going horizontally and vertically, and then attempts to place buildings in ...
0
votes
1answer
31 views
Taking a node in rootA and finding a clone node in other tree
I was asked this as an interview question. I was also asked to assume that there is a function which can compare and say two nodes are identical. I would like to implement that function as well. I'm ...
2
votes
3answers
70 views
Reverse part of a linked list
I'm learning data structures. I'm working on linked lists at the moment, and I'd like to have a strong grasp on them. Below is the last problem I solved. I'd like to know what you think of the ...
4
votes
4answers
130 views
Dividing a range into N sub-ranges
Introduction
The function divides a range given by a begin_iterator and an end_iterator into ...
4
votes
2answers
61 views
Find if the prefix of the string exists in the values of the hash table
I have a hash map which maps to some strings which serve as prefixes and are of small length (max length is 6):
...