Tagged Questions
31
votes
8answers
2k views
Find the number of occurrences of a subsequence in a string
For example, let the string be the first 10 digits of pi, 3141592653, and the subsequence be 123. Note that the sequence occurs twice:
3141592653
1 2 3
1 2 3
This was an interview ...
23
votes
6answers
2k views
Challenging dynamic programming problem
This is a toned down version of a computer vision problem I need to solve. Suppose you are given parameters n,q and have to count the number of ways of assigning integers 0..(q-1) to elements of ...
22
votes
5answers
638 views
Algorithm for finding the busiest period?
I have some data like this:
1: 2 - 10
2: 3 - 15
3: 4 - 9
4: 8 - 14
5: 7 - 13
6: 5 - 10
7: 11 - 15
I will attempt a representation to make it clearer:
1 2 3 4 5 6 7 ...
22
votes
3answers
2k views
FSharp runs my algorithm slower than Python!
Years ago, I solved a problem via dynamic programming:
http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html
The solution was coded in Python.
As part of expanding my horizons, I recently started ...
15
votes
14answers
6k views
Algorithm to Divide a list of numbers into 2 equal sum lists
There is a list of numbers.
The list is to be divided into 2 equal sized lists, with a minimal difference in sum. The sums have to be printed.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
...
10
votes
10answers
652 views
In python, how does one efficiently find the largest consecutive set of numbers in a list that are not necessarily adjacent?
For instance, if I have a list
[1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]
This algorithm should return [1,2,3,4,5,6,7,8,9,10,11].
To clarify, the longest list should run forwards. I was wondering what ...
9
votes
2answers
331 views
Memoization Handler
Is it "good practice" to create a class like the one below that can handle the memoization process for you? The benefits of memoization are so great (in some cases, like this one, where it drops from ...
6
votes
3answers
327 views
Finding an optimal solution that minimizes a constraint?
Let us call this problem the Slinger-Bird problem (actually the Slinger is analogous to a server and the bird to a request but I was having a nervous breakdown thinking about it so I changed them ...
5
votes
4answers
666 views
Finding shortest combinations in array/sequence that equals sum
I'm totally stuck and have no idea how to go about solving this. Let's say I've an array
arr = [1, 4, 5, 10]
and a number
n = 8
I need shortest sequence from within arr which equals n. So for ...
4
votes
1answer
537 views
Algorithm to get every possible subset of a list, in order of their product, without building and sorting the entire list (i.e Generators)
Practically, I've got a set of objects with probabilities, and I want to look at each possible group of them, in order of how likely it is that they're all true assuming they're independent -- i.e. in ...
4
votes
4answers
181 views
Dynamic Programming Optimal Coin Change
I've been reviewing some dynamic programming problems, and I have had hard time wrapping my head around some code in regards to finding the smallest number of coins to make change.
Say we have coins ...
4
votes
1answer
276 views
partition of a list using dynamic programming
I have posted a bit here related to a project I have been trying to work on and I keep hitting design problems and have to design from scratch. So I'm wondering if I can post what I'm trying to do ...
3
votes
1answer
62 views
Calculating the complexity of Levenshtein Edit Distance
I have been looking at this simple python implementation of Levenshtein Edit Distance for all day now.
def lev(a, b):
"""Recursively calculate the Levenshtein edit distance between two strings, a ...
3
votes
3answers
169 views
Sorted tuples from cartesian product of lists
I have dictionary of lists, like so:
D = {'x': [15, 20],
'y': [11, 12, 14, 16, 19],
'z': [7, 9, 17, 18]}
I want to take the keys 3 at a time (I'll use itertools.permutations), and then ...
3
votes
3answers
1k views
Subset sum recursively in Python
I will be happy to get some help.
I have the following problem:
I'm given a list of numbers seq and a target number and I need to write 2 things:
A recursive solution that returns True if there is ...
