All Questions
Tagged with python-2.x algorithm
162 questions
3
votes
3
answers
1k
views
Dynamic programming based range minimum query
I am implementing a DP-based range minimum query data structure and algorithm in Python 2.7. Any advice on algorithm time complexity improvements, code bugs or code style issues are appreciated.
More ...
- 3,453
1
vote
1
answer
229
views
Serialize and deserialize binary search tree
Is there any good advice on how to improve performance in terms of algorithm time complexity? I am using a recursive solution and am not sure if any faster non-recursive solution exists.
...
- 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
2
votes
0
answers
562
views
Second degree connection ranking
Problem
Find 2nd degree connections ( friends’ friends), output these 2nd
degree connections ranked by number of common friends (i.e 1st degree
connections) with you, (example: if 2nd degree ...
- 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
1
vote
1
answer
1k
views
Longest absolute path in file system
Problem
Suppose we abstract our file system by a string in the following
manners:
The string dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext represents:
...
- 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
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
4
answers
2k
views
Two sum with two lists
Suppose we have two sorted lists, and we want to find one element from the first, and the other element from the 2nd list, where the sum of the two elements equal to a given target. If there are ...
- 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
3
votes
0
answers
1k
views
Implementing the stochastic gradient descent algorithm of the softmax regression with only NumPy [closed]
I am implementing the stochastic gradient descent algorithm. I think there is plenty of room for improvement.
...
- 325
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
0
answers
742
views
Counting squares in a grid that is subdivided by line segments
Problem:
Given a picture of square with a bunch of horizontal and vertical lines in it (lines are not necessarily spanning the full square length, in other words think of a fine grid with many ...
- 3,453
5
votes
1
answer
741
views
Find equal pairs
Problem
Given an array A of unique integers, find the index of values that
satisfy A + B =C + D, where A,B,C & D are integers values in the
array. Find all combinations of quadruples.
I ...
- 3,453
3
votes
3
answers
280
views
Continuous sequence against target number
Post problem and my code written in Python 2.7. Any advice for code bugs, performance in terms of algorithm time complexity and code style are appreciated. I did PEB8 self-check in PyCharm.
BTW, a ...
- 3,453
2
votes
0
answers
468
views
Tarjan's strongly connected component finding algorithm
Here is my code for Tarjan's strongly connected component algorithm. Please point out any bugs, performance/space (algorithm time/space complexity) optimization or code style issues.
...
- 3,453
9
votes
1
answer
14k
views
Check if two rectangles overlap
Suppose rectangles are parallel to x-axis/y-axis. Check if two rectangles overlap or not and if they do, output the overlap area.
Here is my code and I track min/max x-coordinate and min/max y-...
- 3,453
2
votes
0
answers
622
views
Vertical sum in a given binary tree
I'm working on this problem,
Problem statement,
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.
Examples:
...
- 3,453
12
votes
3
answers
237
views
Maximizing grad student happiness
A local university's graduate school has a field placement that's a required component for graduation. Each student works in the field (something like a residency for medical students) for one year ...
- 66.6k
2
votes
2
answers
3k
views
Find two numbers that sum closest to a given number
I'm working on the problem of finding 2 numbers that their sum is closest to a specific number. Input numbers are not sorted.
My major idea is to sort the numbers and find from two ends. I'm ...
- 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
4
votes
2
answers
654
views
Bubble Sorting Algorithm
I made a simple Python program which takes a list of unique numbers and orders them from smallest to greatest. The algorithm (which is actually quite similar to bubble sort) works like this:
Take the ...
- 845
1
vote
1
answer
184
views
3 sum implementation in python 2.7
Working on below problem, looking for advice on code style, functional bug and time complexity improvements.
Also looking for advice in,
If array is not sorted, any solutions available for O(n^2) ...
- 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
57
views
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
6
votes
1
answer
2k
views
Sparse matrix compressed sparse row (CSR) in Python 2.7
Brief introduction for CSR:
The compressed sparse row (CSR) or compressed row storage (CRS) format
represents a matrix M by three (one-dimensional) arrays, that
respectively contain nonzero ...
- 3,453
2
votes
1
answer
3k
views
Implementing a queue using a circular buffer
I'm working on implementing a queue using a circular buffer problem. Any smarter ideas for better time complexity, any code bug or code style advice are highly appreciated.
...
- 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
5
votes
2
answers
2k
views
Valid palindrome solution
I'm working on this valid palindrome problem. Any advice on code bug, better idea for low algorithm execution time complexity, code style, etc. are highly appreciated.
Problem
Given a string, ...
- 3,453
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
2
votes
2
answers
3k
views
Serialize and deserialize binary tree
Here is my code of serialize and de-serialize a binary tree, looking for advice. One issue in my mind which I cannot resolve is, I am using a global variable index, wondering if more elegant solutions ...
- 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
2
votes
0
answers
732
views
Counting numbers in an array that are divisible by any 2 numbers
While solving one question I got stuck with a time limit error. The main objective in question is to count numbers in an array \$A\$ that are either divisible by \$P\$, \$Q\$ or both.
Input format:
...
- 255
2
votes
2
answers
2k
views
Sort array by low, medium and high
I'm working on a problem to sort array by low, medium and high -- in-place tweak original array. I'm looking for advice, especially any algorithm implementation efficiency. My current bottleneck of ...
- 3,453
3
votes
2
answers
728
views
Simplify Unix path
Here is my code for simplifying a Unix path. Any advice is highly appreciated, including higher efficiency from an algorithm time complexity perspective, or any bugs.
...
- 3,453
1
vote
0
answers
855
views
Huffman encoding implementation
Here is my implementation of Huffman encoding using min-heap approach mentioned in this Wikipedia page. I'm looking for advice, using Python 2.7.
...
- 3,453
2
votes
0
answers
1k
views
Find k nearest points
I'm working on a problem to select k nearest points for a given point. Any advice for bugs, improvements are appreciated, including general advice to implement find nearest k points.
My major idea is ...
- 3,453
6
votes
2
answers
10k
views
sparse vector dot product
I'm trying to implement a sparse vector (most elements are zero) dot product calculation. My major idea is to represent each sparse vector as a list (which holds only non-zero dimensions), and each ...
- 3,453
3
votes
1
answer
4k
views
Remove comments from C-like source code
I am working on the problem of removing comments from C-like source code. Here is my code in Python 2.7, and if anyone could advise improvement areas (especially performance), or any functional bugs ...
- 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
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
3
votes
1
answer
2k
views
Serialize and deserialize a tree
Suppose each node of a tree has maximum n children. I want to serialize and de-serialize for a tree. My current solution is doing pre-order traverse, and using <...
- 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
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
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
6
votes
5
answers
4k
views
1D Peak Finder Algorithm
I'm reviewing MIT Introduction to Algorithm lectures/exercises and am trying to implement a one dimensional peak finder algorithm.
I've got a working copy but it's a bit messy and I've had to put ...
- 211
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
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
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