All Questions
Tagged with python-2.x algorithm
162 questions
2
votes
1
answer
100
views
Find valid triples for a sorted list of integers (part 2)
Have some ideas to improve code from this discussion (Find valid triples for a sorted list of integers) and post new code in a new post.
The new idea is to try to remember where low bound searched ...
- 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
1
vote
2
answers
279
views
Clone a linked list with a random pointer (part 2)
This question is a follow-up question from here, where I implement the method from @vnp.
I have tested my code and it works, but the 3 steps processing seems a bit long to me. I also tried to write a ...
- 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
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
0
votes
1
answer
113
views
Social network broadcast message algorithm (part 2)
This is new code and continue discussion from thread (Social network broadcast message algorithm), and this thread focus on build new graph from strong connected graph part. Let me post the problem ...
- 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
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
2
votes
1
answer
3k
views
ROC and AUC calculation
Using Python 2.7 and here is my code to calculate ROC/AUC and I compare my results of tpr/fpr with threshold, it is the same result of whay scikit-learn returns.
My questions, (1) any ideas for ...
- 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
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
1
vote
1
answer
12k
views
Print tree level by level including Empty node
Here is my code to print tree in a level by level way. It needs to print an empty node as well to keep tree structure like full binary tree for elegancy reasons.
I'm wondering if anything you think ...
- 3,453
1
vote
1
answer
113
views
Check whether a given sequence can be rearranged using a stack
Working on a problem, for a given input sequence to a stack, check whether it could produce (using stack push/pop operations) the output sequence.
For example if input is ...
- 3,453
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
3
votes
3
answers
86
views
Generating variables to be named, filled in and operated on the fly in Python
I am very new to Python and trying to refactor my code which is ripe for error.
Currently, I manually name a bunch of arrays:
...
- 163
3
votes
1
answer
7k
views
LRU cache in Python
Here is my simple code for LRU cache in Python 2.7. Appreciate if anyone could review for logic correctness and also potential performance improvements.
A confusion want to ask for advice is, I am ...
- 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
1
answer
111
views
Princeton KMP implementation
I implemented a Python version of KMP followed by Princeton Prof Robert Sedgewick's discussion.
However, I got a Time Limit Exceeds error. Per leetcode's explanation, TLE indicates that the solution ...
- 51
3
votes
2
answers
2k
views
Calculate the path sum of a binary tree
I want to calculate all sum of all possible paths from root to leaf. Each node has value of an integer number (decimal).
In the following example:
...
- 3,453
3
votes
1
answer
1k
views
Minimum window substring
The minimum window substring problem from leetcode.com asks:
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity \$O(n)\$.
...
- 3,453
3
votes
1
answer
119
views
Beating a dead horse: Project Euler 4
The task
A palindromic number reads the same both ways. The largest palindrome
made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the ...
- 5,725
2
votes
2
answers
3k
views
Counting pairs of integers which have a predefined difference
I'm doing this HackerRank problem:
Given \$N\$ integers, count the number of pairs of integers whose difference is \$K\$.
So far, I've ended up with this code:
...
- 493
4
votes
1
answer
2k
views
Checking to see if array can be sorted using only one operation
I'm doing this HackerRank problem, which asks whether an array of up to 100000 integers can be sorted in ascending order by exactly one of the following:
swapping two elements
reversing a subarray
...
- 493
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
3
votes
2
answers
936
views
Checking literary works for Zipf's Law
I wrote a Python script that, given a literary work in text file format, takes it apart, makes a word list, counts how many times each words appears in the literary work, and then checks if it follows ...
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
2
votes
3
answers
6k
views
Longest Collatz sequence in Python
I came across this problem:
The following iterative sequence is defined for the set of positive
integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
...
james smith
2
votes
1
answer
1k
views
Functional Scrabble Word Score
Homework: Write a function to score a scrabble word.
values is a global dict formatted as values = {'a': 1, 'b': 3,...}
The ...
- 453
2
votes
2
answers
5k
views
Count overlapping substrings
I'm looking for feedback on the actual logic of this simple Python 2.7 script. The automated grader passed it, but I expect it could be make more 'pythonic'. It was written for homework, and some of ...
- 453
4
votes
1
answer
1k
views
Prove that the graph is a valid tree in Python
I recently solved this leetcode problem:
Given n nodes labeled from 0 to n - 1 and a list of undirected edges
(each edge is a pair of nodes), write a function to check whether
these edges make ...
- 623
2
votes
2
answers
264
views
Improving the time complexity of my back pack algorithm
Is there anyone who can help me improve the time complexity of this backpack algorithm, for which I already use sliding array to improve the space complexity.
The problem is as follows:
Given <...
- 71
4
votes
2
answers
6k
views
Check if a binary tree is a binary search tree
Given a binary tree, I need to check if it satisfies the binary search tree property i.e. left child is less than or equal to the current node and right child is greater than or equal to the current ...
- 5,127
3
votes
1
answer
3k
views
2
votes
2
answers
2k
views
Count number of matching nodes in a Binary tree
Problem
Count the number of matching nodes in the subtree rooted at some node n.
Solution
...
- 5,127
4
votes
2
answers
7k
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 ...
- 5,127
1
vote
1
answer
583
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 ...
- 5,127
4
votes
1
answer
4k
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 ...
- 163
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
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
4
votes
4
answers
2k
views
"Tractor" Python implementation
This is the Tractor problem from the Kattis problems archive.
Problem Statement
Bessie the Cow has stolen Farmer John’s tractor and is running wild on the coordinate plane! She, however, is a ...
- 5,127
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
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
4
votes
2
answers
1k
views
"Even Tree" Python implementation
Problem Statement
You are given a tree (a simple connected graph with no cycles). You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each ...
- 5,127
8
votes
4
answers
10k
views
4
votes
1
answer
311
views
Counting the number of bits of a positive integer #2
I think the running time of this should be \$O(log_{2}(n))\$:
...
- 5,127
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
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
4
votes
1
answer
487
views
Solving a variation of the "Partition Problem"
In my version of the Partition Problem, I have a set of weights that are all powers of three (1, 3, 9, 27 etc.). I only have one of each weight. There is some object (the weight of this object is ...
- 41
3
votes
1
answer
153
views
Batch Gradient Descent running too slowly
Following Data Science from Scratch by Joel Grus, I wrote a simple batch gradient descent solver in Python 2.7. I know this isn't the most efficient way to solve this problem, but this code should be ...
- 133
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