All Questions
Tagged with python-2.x algorithm
50 questions
11
votes
1
answer
4k
views
Z-Algorithm for pattern matching in strings
I was trying to refactor the following Python code (keeping the same time-complexity) which is an implementation of Z-Algorithm for pattern matching in strings.
...
- 221
10
votes
1
answer
14k
views
13
votes
1
answer
2k
views
Extended stable marriage challenge
I've written a solution for the stable marriage problem in the case that the number of men is not equal to the number of women. My problem is not that I can't prove my code is right. The problem is I ...
- 251
7
votes
1
answer
165
views
Classic merge sort (part 2)
(Initial discussion from Classic merge sort, since it is new code, I start a new thread)
Post my code below, my major question is, I have to create another array ...
- 3,453
7
votes
4
answers
7k
views
Find the shortest whole repetitive substring
I'm working on a problem to find wholly repeated shortest substring of a given string, and if no match, return length of the string.
My major idea is using a Trie ...
- 3,453
6
votes
2
answers
806
views
4 sum challenge (part 2)
This is a continued discussion from (4 sum challenge) by return count only.
Problem
Given four lists A, B, C, D of integer values, compute how many tuples
(i, j, k, l) there are such that A[...
- 3,453
4
votes
1
answer
155
views
Group duplicate files
Here is my source code which group duplicate files together, written in Python 2.7. Any advice on smarter ideas to group duplicate files together more efficient, it will be great. Any general advice ...
- 3,453
4
votes
1
answer
513
views
Using range minimal query for lowest common ancestor (LCA)
Here is my code to use range minimal query to resolve the LCA problem. Any advice on code bugs, performance improvement in terms of algorithm time complexity, code style are appreciated.
More ...
- 3,453
4
votes
1
answer
855
views
Find valid triples for a sorted list of integers
I'm working on a problem in which I have an input array, sorted positive unique integers, and have to try to find all possible triples \$(x,y,z)\$ which satisfy \$x+y>z\$ and \$x<y<z\$. For ...
- 3,453
3
votes
1
answer
88
views
Group duplicate files (part 3)
This is a continued discussion (from here => Group duplicate files (part 2)) with new code and new thoughts/questions (see special question part for details for new questions), and I decide to make a ...
- 3,453
3
votes
1
answer
166
views
Data structure and movement for tilt maze (part 2)
This is a design data structure and movement for a tilt maze. For example, this one.
My major idea is learned from abrarisme's smart idea of using two boolean matrix to represent wall. Please refer ...
- 3,453
2
votes
3
answers
140
views
Different path for grid move (part 2)
This is a continued discussion from (Different path for grid move) to optimize for space complexity, and since it is new code and I make a new post.
Given a m * n grids, and one is allowed to move ...
- 3,453
1
vote
1
answer
273
views
Find path from source to destination in tilt maze
For a tilt maze general reference, you can refer to this example. The previous related code review discussion could be referred here.
The problem I want to resolve is to find all possible path (so ...
- 3,453
1
vote
1
answer
118
views
Group duplicate files (part 2)
This is a continued discussion (from here => Group duplicate files) with new code and new thoughts/questions (see special question part for details for new questions), and I decide to make a new post.
...
- 3,453
15
votes
1
answer
23k
views
Sudoku Puzzle Generator
I've written a Sudoku puzzle generator. It currently runs through each line of the 9x9 grid and places numbers randomly if they're valid. It loops over all the numbers from 1-9 and then if it finds ...
- 13.1k
14
votes
4
answers
2k
views
Codechef: Prime Number Generator
Peter wants to generate some prime numbers for his cryptosystem. Help
him! Your task is to generate all prime numbers between two given
numbers!
Input
The input begins with the number t of test cases ...
- 241
9
votes
1
answer
9k
views
Find the nearest point of a given set of points
Suppose there are a set of given points (represented by x and y two dimensional coordinates), and for any given point A, I want ...
- 3,453
9
votes
1
answer
846
views
Check “five in a row” for a 15x15 chess board (part 2)
This is a follow-up from here. I have a further optimization for space complexity by store only direction status data for one row for each directions (refer to variable ...
- 3,453
8
votes
1
answer
1k
views
Find the nearest point of a given set of points (part 2)
This is a continued discussion from here, and I use new a approach (bounding box/or envelop algorithm) to improve the algorithm efficiency. Any code bugs, algorithm time complexity improvement or ...
- 3,453
7
votes
1
answer
3k
views
Trie Tree match string containing ? and *
Using Python 2.7 and here is my code which implement trie match for a whole word, and also support if the whole word contains ? (match any one character) or ...
- 3,453
6
votes
2
answers
3k
views
Check "five in a row" for a 15x15 chess board
Problem:
For a given board, judge who had complete a continuously line (could
be horizontal, vertical or diagonal) of 5 pieces. Input is a 15×15
chess board, could be white (1), black (...
- 3,453
6
votes
2
answers
2k
views
Strongly connected component algorithm in Python 2.7
This is my implementation of Kosaraju's algorithm for detecting strongly connected components, post here for advice. Some special areas looking for advice,
Not sure if my current implementation for ...
- 3,453
6
votes
1
answer
364
views
Algorithm to park cars with minimal moves (2nd version)
I'm working on a car move problem. Suppose we have origin parking position for each car, [-1,1,2,3,7,6,4,5] (which means first position is empty, car with ID 1 ...
- 3,453
5
votes
1
answer
1k
views
Quick select the kth smallest value
Here is my code for quick select in Python 2.7. I am trying to optimize code for fewer comparisons. And my specific question is marked in code, 3 lines marked with ...
- 3,453
5
votes
1
answer
223
views
Using range minimal query for lowest common ancestor (LCA) -- part 2
Here is my code to use range minimal query to resolve the LCA problem. I applied comments from here.
Any advice on code bugs, performance improvement in terms of algorithm time complexity, code style ...
- 3,453
5
votes
1
answer
756
views
Balanced smileys check algorithm (part 3)
This is a follow-up for here, for bug fixes and applied advice.
Problem
Your friend John uses a lot of emoticons when you talk to him on
Messenger. In addition to being a person who likes to ...
- 3,453
5
votes
0
answers
432
views
4 sum challenge [duplicate]
Problem
Given four lists A, B, C, D of integer values, compute how many tuples
(i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C,...
- 3,453
5
votes
2
answers
6k
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 \$O(...
- 5,127
5
votes
3
answers
14k
views
Diagonal difference
Given
You are given a square matrix of size \$N×N\$. Calculate the absolute difference of the sums across the two main diagonals.
Input Format
The first line contains a single integer N. The ...
- 5,127
5
votes
1
answer
648
views
Social network broadcast message algorithm
Working on below problem and post problem and my current code. My idea is to always iterate from the minimal in-degree node which has not been visited before. Then based on this node to do a BFS. I am ...
- 3,453
5
votes
2
answers
1k
views
High execution time of LCS length program in Python2
I was trying to solve the Longest Common Subsequence problem on a HackerRank exercise.
It's quite simple and straightforward, just print out the length of the LCS. I submitted this code:
...
- 493
4
votes
1
answer
2k
views
Algorithm to park cars with minimal moves
I'm working on a car move problem. Suppose we have origin parking position for each car, [-1,1,2,3,7,6,4,5] (which means first position is empty, car with ID 1 ...
- 3,453
4
votes
1
answer
432
views
Different path for grid move
Given a m * n grids, and one is allowed to move up or right, find the different number of paths between two grid points.
My major idea is, if move r steps right, <...
- 3,453
3
votes
2
answers
613
views
Balanced smileys check algorithm (part 4)
This is a follow-up for here, for bug fixes and applied advice.
Problem
Your friend John uses a lot of emoticons when you talk to him on
Messenger. In addition to being a person who likes to ...
- 3,453
3
votes
2
answers
3k
views
Given an unsorted integer array, find the first missing positive integer
Here is the problem, any advice about code improvement, more efficient implementation in terms of time complexity, functional bugs, etc. are appreciated.
Given an unsorted integer array, find the ...
- 3,453
3
votes
1
answer
990
views
Clone a linked list with a random pointer
I'm working on a problem to clone a linked list (each node has a regular next pointer), and each node also has a random pointer which could point to any node in the linked list. Each linked list node ...
- 3,453
3
votes
1
answer
1k
views
Rabin Karp algorithm improvement for string contains A to Z only
I have made some improvement to Rabin Karp algorithm when the source and pattern only contain the characters from A to Z. The improvement is, I use base 26 for hashing (as there are total 26 ...
- 3,453
3
votes
1
answer
285
views
Data structure and movement for tilt maze
This is a design data structure and movement for a tilt maze. For example, this one.
My major idea is to divide into Ball, Maze,...
- 3,453
3
votes
3
answers
3k
views
Game where two players take turns picking numbers until a target sum
Working on the problem of sum game. Suppose we have consecutive numbers from 1 to n, and an expected sum number, there are two players, and each player tries to select one number in turn (once a ...
- 3,453
3
votes
1
answer
248
views
Dynamic programming solution for cross river algorithm (part 2)
I'm working on the cross river problem (previous post here). Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style advice is appreciated.
More ...
- 3,453
2
votes
3
answers
290
views
Different path for grid move (part 3)
This is a continued discussion from (Different path for grid move (part 2)) to optimize for space complexity (using only cur list, other than a ...
- 3,453
2
votes
2
answers
854
views
Find smallest subset prefixes
Here is my code for this problem. Any bugs, performance in terms of algorithm time complexity, code style advice are appreciated.
The areas which I want to improve, but do not know how to improve are:...
- 3,453
2
votes
1
answer
477
views
find first bad version
Working on below find first bad version problem, post my code in Python 2.7, any smarter ideas for better time complexity, any code bug or code style advice are highly appreciated. My major idea is ...
- 3,453
2
votes
1
answer
99
views
Find first bad version (part 2)
This is new code based on some new ideas to reduce calls to is_bad_version. Refer to the previous version of the code discussion from here.
Any smarter ideas for ...
- 3,453
2
votes
2
answers
760
views
Find the shortest whole repetitive substring (part 3)
This is a new discussion from this post (Find the shortest whole repetitive substring) and since it is totally new code, I post as a new thread here.
The major initiative of posting a new thread is, ...
- 3,453
2
votes
1
answer
177
views
Find the shortest whole repetitive substring (part 2)
This is a continued improvement from discussion here (Find the shortest whole repetitive substring), since code has changed a lot dues to improvement, I post it here. Major smart ideas are from ...
- 3,453
2
votes
1
answer
1k
views
Game where two players take turns picking numbers until a target sum (part 2)
Here is a continued discussion (Game where two players take turns picking numbers until a target sum) from here since my previous code has bug, I fixed it with totally new algorithm implementation.
...
- 3,453
2
votes
2
answers
645
views
Balanced smileys check algorithm (part 2)
This is a follow-up for here.
Problem
Your friend John uses a lot of emoticons when you talk to him on
Messenger. In addition to being a person who likes to express himself
through ...
- 3,453
1
vote
1
answer
2k
views
Parsing JSON in one go using state machine solution
I need to parse a simple JSON string (flat JSON, no hierarchy) for keys and values, and there is a system constraint that I cannot use any built-in JSON library and can only read a string once due to ...
- 3,453
1
vote
1
answer
203
views
Find smallest subset prefixes (part 2)
Here is my code for this problem. Any bugs, performance in terms of algorithm time complexity, code style advice are appreciated.
This is a continued discussion from (Find smallest subset prefixes) ...
- 3,453