nilkn
BAN USERThis is equivalent to finding longest common subsequences. Specifically, any discontinuous occurrence of a pattern P in a search string S is by definition a longest common subsequence. We just want the number of matches rather than the length, and we want to return zero in case the length of the LCS is less than that of P (i.e., no full match exists).
We build an array c[i,j] which represents the number of matches of P[0, ..., i-1] in S[0, ..., j-1]. This naturally satisfies the following recurrences:
c[i,j] = c[i-1, j-1] + c[i, j-1] if P[i] = S[j] (number of matches using the current character, plus number of matches using only prior characters);
c[i,j] = c[i, j-1] if P[i] != S[j].
Here's a direct implementation of this in Python:
def discontinuous_matches(p, s):
c = [[0 for i in range(0, len(s) + 1)] for j in range(0, len(p) + 1)]
for i in range(0, len(s) + 1):
c[0][i] = 1
for i in range(1, len(p) + 1):
for j in range(1, len(s) + 1):
if p[i-1] == s[j-1]:
c[i][j] = c[i-1][j-1] + c[i][j-1]
else:
c[i][j] = c[i][j-1]
return c[len(p)][len(s)]
I personally find a recursive approach a lot more comprehensible, though. The idea is simpler. We look at each index of the search string and find the number of occurrences of the pattern starting at that index. We add up all these results.
The number of occurrences of the pattern p and index i of the search string s, if s[i] == p[0], is simply the number of occurrences of the *rest* of the pattern in the remainder of the string.
def discontinuous_matches_recursive(p, s):
if len(p) == 0:
return 1
count = 0
for i, c in enumerate(s):
if p[0] == c:
count += discontinuous_matches_recursive(p[1:], s[i+1:])
return count
Store dictionary words in a trie for fast membership tests (much more memory efficient than a hash table).
For each letter, find the highest score possible for a word starting with that letter. Do this by first looking up that letter in the trie, then recursively looking up all possible follow-up letters. This will minimize the number of words which are considered which are not in the dictionary.
This is an extended topological sort which keeps track of the different "levels" in the graph. Here's a quick implementation in Python as a generator:
def parallel_schedule(data):
while True:
ordered = set(item for item, dep in data.items() if not dep)
if not ordered:
break
yield ' '.join(sorted(ordered))
data = {item: (dep - ordered) for item, dep in data.items() \
if item not in ordered}
Note that data here is a dictionary which maps each task to a set of its dependencies. I'm also assuming that a task with no dependencies occurs in data as mapped to the empty set (e.g., data = {'A': set(), 'B': set(['A']), ...}).
This works by grabbing those tasks with no dependencies, executing them in parallel, removing them from the graph, and then repeating the process.
This is a weird question, and a detail that I think a lot of posters here are missing is that on day N you must have N candles lit.
I guess you'd just have a priority queue with the candles. On day 1, grab the tallest candle. On day 2, extinguish the candle, put it back into the queue with reduced height, grab the two tallest candles and light them. On day 3, extinguish those, put them back in the queue, grab the three tallest candles and light them. Keep going.
Because N candles must be lit on day N, obviously you can't do this for more days than there are candles. So for N candles the absolute max is N days.
On deeper reflection, I think this only works if the tree is a *binary* tree. It's fairly easy to construct a counter-example when the tree is not necessarily binary. For instance, consider a root node with three children, L, M, and R. L has a huge tree beneath it as does R, but M has no children. It's obvious that the path corresponding to the diameter goes from a leaf of L through the root down to a leaf of R. Adding a child to M does not change this.
- nilkn March 22, 2015Dynamic programming. Here's an iterative bottom-up approach using memoization:
import math
def perfect_squares(n):
squares = [x * x for x in range(1, int(math.floor(math.sqrt(n)) + 1))]
counts = [x for x in range(0, n+1)]
for i in range(1, n+1):
for j in squares:
counts[i] = min(counts[i], 1 + counts[i-j])
return counts[n]
Two observations...
(1) The graph is always a tree, and the first node is always the root.
(2) The diameter only increases when the parent of the new node didn't already have any children.
The following solution in Python hopefully works. I've taken the shortcut here of just representing nodes as unique integers. The kind of surprising thing here is that we don't even need to remember the tree structure at all -- we just remember the degree of each vertex, where degree is the number of edges incident on the vertex (ingoing or outgoing).
class NodeConsumer:
def __init__(self):
# 0 is the root.
self.degrees = {0: 0}
self.diameter = 0
def add_node(self, n, p):
self.degrees[n] = 1
if self.degrees[p] <= 1:
self.diameter += 1
self.degrees[p] += 1
def get_diameter(self):
return self.diameter
This doesn't make sense as phrased. Based on the example input/output, I assume the intention was this: given an integer N, determine all subsets of {1,2,3,...,N} whose sum is N.
In that case, this is just a classic dynamic programming problem. Define S[i] to be the set of subsets of {1,2,3,...,N} whose sums are i, for 1 <= i <= N. Then we observe the following recurrence relation:
S[i] = {{1} U X for X in S[i-1]} U {{2} U X for X in S[i-2]} U ... U {i}.
def subsets(N):
S = [[] for i in range(0,N+1)]
S[0] = [[]]
for i in range(1, N+1):
for j in range(1, i+1):
S[i] += [[j] + X for X in S[i-j]]
return S[N]
It can be done with a single pass over the array (Python):
import random
def rand_max(arr):
curr_max = 0
curr_max_idx = 0
curr_max_count = 1
for i,x in enumerate(arr):
if x > curr_max:
curr_max = x
curr_max_idx = i
curr_max_count = 1
elif x == curr_max:
curr_max_count = curr_max_count + 1
if random.random() < 1.0 / curr_max_count:
curr_max_idx = i
return curr_max_idx
Given the array A, we build an array c[i] such that c[i] is the longest increasing subsequence ending at index i. c[i] can be iteratively built up, which yields the following solution using dynamic programming. This produces the actual subsequence, not just its length:
- nilkn March 23, 2015