All Questions
Tagged with python-2.x algorithm
162 questions
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
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
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
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
4
answers
14k
views
Consolidate list of ranges that overlap
I wanted to implemented an algorithm in Python 2.4 (so the odd construction for the conditional assignment) where given a list of ranges, the function returns another list with all ranges that overlap ...
- 228
10
votes
1
answer
14k
views
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
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
4
answers
10k
views
8
votes
2
answers
3k
views
Sudoku solver recursive solution
Here is my code in Python 2.7 for a Sudoku resolver. Any advice on performance improvement, code bugs or general code style advice is appreciated.
My major idea is:
Using method generate some random ...
- 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
8
votes
1
answer
448
views
Artificial Neural Network implementaion
I'm looking for some general tips on code practices, doing things properly in idiomatic pythonic way. But mostly I want to know if this was build correctly. I tried making neural nets in the past, but ...
- 712
7
votes
4
answers
7k
views
Buy once and sell once for maximum profit
Suppose we have stock price history, and we are allowed to buy only once and sell only once. The problem is to find the maximum profit we can make. Here is my code that I tested for basic test cases. ...
- 3,453
7
votes
4
answers
1k
views
Solving jumbled letters using a given dictionary
Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters.
Example:
...
- 605
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
7
votes
3
answers
179
views
Python methods to reduce running times KTNS algorithm
I have been trying to develop an algorithm called keep the tool needed soonest (for more information about the KTNS explanation (page 3)) but during the simulations, I have realized that it takes too ...
- 185
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
7
votes
2
answers
991
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 ...
- 5,127
7
votes
3
answers
2k
views
"Angry Professor" Python implementation
Problem Statement
The professor is conducting a course on Discrete Mathematics to a class of N students. He is angry at the lack of their discipline, and he decides to cancel the class if there are ...
- 5,127
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
6
votes
4
answers
23k
views
Plus Minus in Python
You're given an array containing integer values. You need to print the
fraction of count of positive numbers, negative numbers and zeroes to
the total numbers. Print the value of the fractions ...
- 5,127
6
votes
4
answers
2k
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 ...
- 163
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
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
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
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
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
6
votes
2
answers
7k
views
Prefix search by trie tree
I'm working on the prefix search problem:
Given a set of words, for example words = ['a', 'apple', 'angle', 'angel', 'bat', 'bats'], for any given prefix, find ...
- 3,453
6
votes
1
answer
1k
views
6
votes
3
answers
4k
views
"Cut the sticks" Python implementation
Problem Statement
You are given N sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the ...
- 5,127
6
votes
1
answer
488
views
Python knapsack program
I have this data for the knapsack problem:
List of product prices = MENU
Most popular product count = MOST_POPULAR_COCKTAIL
...
- 109
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
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
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
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
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
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
5
votes
2
answers
554
views
Print tree in a zigzag manner
I want to print a tree in a zigzag manner level-by-level. I'm wondering if there are any logic issues in my code and any further performance improvement ideas by using a smarter algorithm ...
- 3,453
5
votes
4
answers
937
views
Decrease Computation Time for Python Tic-Tac-Toe Minimax Algorithm
Background
I am currently participating in a tic-tac-toe coding challenge. During their move, each participant is given the board state and their team, X or O. The blank board is:
...
- 153
5
votes
2
answers
1k
views
Prime Number Generator (6n + 1 or 6n - 1)
This generator is like most where it brute forces an integer: it see whether the integer is divisible by any of the primes; if so, then it's not a prime and vice versa. This though only compares ...
- 845
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
1
answer
839
views
Counting the number of elements in a sorted array
Suppose I have a sorted array, and each element may appear multiple times.
To make it simple, here is an example:
...
- 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
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
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
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
5
votes
1
answer
1k
views
Dynamic programming solution for cross river algorithm
Working on below cross river problem, and post my code in Python 2.7 using dynamic programming. Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style ...
- 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