Fernando
 0of 0 votes
AnswersGiven a array of integers there is one that is repeated several time. How would you compute the length of the sequence of repeated elements.
 Fernando
Assuming the initial array is sorted can you do better than O(n) both for spatial and temporal cost? Report Duplicate  Flag
unknown Software Engineer Coding
Solution in python
from itertools import combinations
def compute_sum_t_with_k(seq, k, t):
return filter(lambda x: sum(x) == t, combinations(seq, k))
Some possible optimizations that could be done are:
 Sorting the array and stop the iteration when we go over the sum.
 Keeping a counter for the sum so instead of adding the k elements we subtract one element and a new one
@tnutty2k8 cool solution but the code is counting possible subsets more than one isn't? For example, [1,2,3,4,5,7] with k 3 and t 6 would count the subset {1,2,3} three times. One for the fist call on the for loop with [2,3,4,5,7], 2, 5, another one for the second iteration [1,3,4,5,7], 2, 4 and the last one for the third iteration [1,2,4,5,7], 2, 3. Javascript is not one of my strong points and perhaps you were planning to check that elsewhere on the code sorry if that is the case this is also for me to learn :).
Edit: I read the question again and it says any so my previous comment is about counting more than once is not valid.
Cheers.
I would break the multiplication into a set of separate sums, In that case you only need to store the result as an int. You might have to use a big decimal library depending on the language, the solution I am proposing is in python and the language takes care of that detail. Given x the length of the first number and y the length of the second number there are x * y sums.
Code in python
def multiply_nums_as_sums(a, b):
len_a, len_b = len(a), len(b)
res = 0
for x in xrange(len_a  1, 1, 1):
for y in xrange(len_b  1, 1, 1):
res += (int(a[x]) * int(b[y])) * 10 ** (len_b  (y + 1) + len_a  (x + 1))
return res

Fernando
August 16, 2017 Humm for me the question as an input you have an array of trees with operators, they share the memory between them so you can have variables. As an output you have to return the result of the trees that have an operation of return. Here is the code in python that solves the problem. (As I think it is)
class node:
def __init__(self, value):
self.value = value
self.right = self.left = None
def AnalyzeClousure():
mem = dict()
def _(root):
# Integer
if type(root.value) == int: return root.value
# Variable
if type(root.value) == str and len(root.value) == 1\
and root.value not in "+*/":
if root.value in mem:
return mem[root.value]
else:
return root.value
# Return
if root.value == 'Return': return AnalyzeTree(root.left)
op = root.value
left = AnalyzeTree(root.left)
right = AnalyzeTree(root.right)
if op == 'Assign': mem[left] = right
if op == '+': return left + right
if op == '': return left  right
if op == '*': return left * right
if op == '/': return left / right
return _
AnalyzeTree = AnalyzeClousure()
a = node("Assign")
a.left = node("x")
a.right = node('+')
a.right.left = node(2)
a.right.right = node(3)
b = node("Return")
b.left = node("x")
print map(AnalyzeTree, [a, b])

Fernando
August 15, 2017 I would use a hash in which the keys are the pages and the values the list of users that visited them. Next the code in Python that illustrates it showing how to solve the queries using the proposed data structure
from collections import defaultdict
def build_query_structure(data):
d = defaultdict(list)
for x, y in data:
d[y].append(x)
return d
query_data = [('u1', 'p4'), ('u3', 'p2'), ('u7', 'p9')]
query = build_query_structure(query_data)
# Query 1: Pages visited exactly 100 times
print filter(lambda x: len(query[x]) == 100, query.iterkeys())
# Query 2: Pages visited by only one user exactly 15 times
print filter(lambda x: len(query[x]) == 15 and len(set(query[x])) == 1,\
query.iterkeys())
# Query 3: Page visited by u3 more than 20 times
print filter(lambda x: query[x].count('u3') >= 20, query.iterkeys())

Fernando
August 14, 2017 It took me a little while to understand how interpret the possible paths.
The difference of two consecutive numbers in the path must be a number that can be computed as a power of 2. Then to compute the values of i you have to start from the end of the path subtracting the previous number and computing the power of two that give us that value. It is a little bit cumbersome so it think some examples will help to understand it better
[0 4] 4  0 is 4. Which power of 2 gives 4? 2 so i = 2
[0 2 4] 4  2 = 2, 2  0 = 2 so 2^1 and 2^1
[0 1 3 4] 1 2 1, so 2^0, 2^1 and 2^0

Fernando
August 09, 2017 @Chris yeah!! If you take C=A and D=B that is what I was doing, computing all the possible subsets, taking the complement with the original one and checking the min from one and the max from the other one. Ironically both versions give almost the same answer. Some times the version I gave on my first post will count one less element, that is because if the whole array is a valid solution then that solution will not be counted as the complement will be the empty set. Anyway, here is a solution for how you interpreted the problem which makes more sense than the one I thought.
from itertools import combinations, chain
def powerset(k):
res = [ combinations(k, x) for x in xrange(1, len(k)+1) ]
return chain.from_iterable(res)
def compute_y(l, K):
return sum(1 if (min(x) + max(x) < K) else 0 for x in powerset(l))
Cheers :)
Edit: Formating
Which version is counting solutions more than once?? I have coded a brute force solution in python and I am getting the same results for the non duplicated version, I haven't tried the other one.
def powerset(a):
if len(a) == 1: return [[], a]
solutions = []
for x in xrange(len(a)):
s = powerset(a[x+1:])
solutions.extend(s[:])
solutions.extend(map(lambda r: r + [a[x]], s))
return solutions
def compute_x(l, K):
total = 0
x = set(l)
pairs = set((tuple(x.difference(c)), tuple(c)) for c in powerset(l))
for a,b in pairs:
if len(a) == 0 or len(b) == 0:
continue
if min(a) + max(b) < K:
total += 1
return total

Fernando
August 07, 2017 @Brugo I know I realized I got the indexes not working correctly and removed the comment as I didn't have time to fix the code but the web page didn't update until several hours later. Great answer using a queue to keep sorted the pairs. Anyway, as both arrays are sorted you can provide a solution in O(k)
Naive solution O(a*b)
from iterttools import product
def smallKPairs(K, a, b):
return sorted(product(a, b), key=sum)[:K]
Solution in O(K)
def smallKPairs(K, a, b):
f_a, f_b = 0, 0
l_a, l_b, c_a, c_b = 0, 0, 0, 0
pairs = []
while (len(pairs) < K):
pairs.append((a[c_a], b[c_b]))
f_a += 1
if f_a == len(a):
l_a += 1
f_a = l_a
f_b += 1
if f_b == len(b):
l_b += 1
f_b = l_b
if a[l_a] + b[f_b] <= a[f_a] + b[l_b]:
c_a = l_a
c_b = f_b
f_a = 1
else:
c_a = f_a
c_b = l_b
f_b = 1
return pairs
Cheers :)
 Fernando August 06, 2017Perform a binary search of K on the array and from that iterate over until we get the all the C closest elements. The cost is log(n) + C. By the way the solution for the example should be 5 isn't?
Solution in Python
def closest_to_K(seq, K, C):
lo, hi = 0, len(seq)  1
value = 0
while lo < hi:
mid = (lo + hi) / 2
if seq[mid] == K:
value = mid
break
elif seq[mid] > K:
hi = mid  1
else:
lo = mid + 1
if lo >= hi: value = lo # In case K is not in the array
res = []
lo, hi = value, value + 1
if seq[value] == K:
res.append(K)
lo, hi = value  1, value + 1
while len(res) != C:
if K  seq[lo] <= seq[hi]  K:
res.insert(0, seq[lo])
lo = 1
else:
res.append(seq[hi])
hi += 1
return res[0]
In: closest_to_K([1,2,5,8,9,13], 8, 4)
Out: 5
In: closest_to_K([1,2,5,8,9,13], 7, 4)
Out: 2
Edit: Added some examples
 Fernando August 04, 2017Solution in python
from collections import deque
def print_tree_zig_zag(root):
level_values = deque()
last_level = 1
frontier = [(root, 1)]
while frontier:
node, current_level = frontier.pop(0)
if current_level != last_level:
l = []
while level_values:
l.append(level_values.popleft())
print 'Level:', last_level, 'Values:', l
last_level = current_level
if node.left:
frontier.append((node.left, current_level+1))
if node.right:
frontier.append((node.right, current_level+1))
if (current_level % 2) == 0:
level_values.appendleft(node.value)
else:
level_values.append(node.value)
l = []
while level_values:
l.append(level_values.popleft())
print 'Level', last_level, 'Values:', l

Fernando
August 04, 2017 @tnutty2k8 if you used the area instead of the length it would work (the length is just for one dimension) but then you would have the problem to convert from the point to the rectangle and that is exactly what the algorithm is doing. It adds all the areas and choose one rectangle randomly.
 Fernando August 04, 2017I think the answer is correct, all rectangles are non overlapped that means that if you choose uniformly between all the rectangles you are not choosing uniformly between the all the possible points. For example what happens if the first rectangle is the smallest one but you choose uniformly between all the rectangles? The points of this rectangle will appear repeated more often as there a less available and the choosing frequency is the same as for the rest of the rectangles. I guess it is a matter of how you interpret the question but the given answer is the most complex one.
Also Java is not my most used language so I can be mistaken, please correct me if that is the case :). The probabilities are like this isn't??
Probability of rectangle 0 is: 1  prob of choosing r1  ....  prob of choosing rn
Probability of rectangle 1 is: area1 / (area0 + area1)  prob of choosing r2  ...  prob of choosing rn
Probabilty of rectangle n is: areaN / (area0 + area1 + ... areaN)
Cheers :)
Hello!!! I have been reading the code and I am confused with the function
void beColleague(Employee p);
Why is it basically a renaming of setManager?? Shouldn't be something like
void beColleague(Employee p) {
if (manager == p) { // p is our manager
manager = p.manager;
p.deleteSubordinate(this);
}
else if (p.manager == this) { // we are the manager of p
p.manager = manager;
deleteSubordinate(p);
}
}
Cheers :)
 Fernando August 03, 2017This a solution using sqlite3 on python so the queries can be checked
import sqlite3
SQL_QUERY = '''
SELECT a.student_id, a.department_id, a.start_dt , b.start_dt as End_Date
FROM student a
LEFT JOIN student b ON a.student_id = b.student_id
WHERE b.start_dt = (SELECT min(start_dt) FROM student c WHERE c.student_id = a.student_id AND c.start_dt > a.start_dt )
ORDER BY 1,3;
'''
conn = sqlite3.connect(':memory:')
c = conn.cursor()
c.execute('''CREATE TABLE Student
(student_id int, department_id text, start_dt text)''')
c.execute("INSERT INTO Student VALUES ('1', 'A', '2017011')")
c.execute("INSERT INTO Student VALUES ('1', 'B', '2017071')")
c.execute("INSERT INTO Student VALUES ('1', 'C', '2017121')")
conn.commit()
for row in c.execute(SQL_QUERY):
print row
conn.close()

Fernando
August 03, 2017 @ChrisK that is the problem I was encountering if you have the desired sum you can guide the search using two counters but on the given problem you have length of the array  2 possible desired sums (the two first elements of the array can't be the desired sum for obvious reasons) so you can't use the algorithm as is to solve the problem.
 Fernando August 01, 2017@ChrisK I thought about that but I got stuck, I can see a linear algorithm using two counters if you have a number to guide the search. I mean given the next array
[10, 20, 35, 40, 75, 90, 180]
If you have two counters one for the lower element and one for the higher element how you do modify them? Potentially any number except the two first ones and the last one can be used to generate a solution.
I have been thinking about some other approaches but none worked.
I have been trying to find a solution to improve the cost but I haven't been able to. Solution with O(n^2) time and O(n) memory
def thereIsSum(seq):
valid_sums = set(seq)
for x in xrange(len(seq)):
for y in xrange(x+1, len(seq)):
if seq[x] + seq[y] in valid_sums:
return True
return False

Fernando
August 01, 2017 As always the solutions of @aonecoding are pretty amazing. Forgot to mention that the cost of my function is O(1) amortizing the O(n) initialization for time and O(n) for memory. Anyway I am commenting to solve possible follow ups for the question in case a random generator for 0 to n  length of the excluded set of numbers is not available. For example, a possible follow up would be to write the same function using a fixed random number generator, for example, from 0 to 7. Here I am providing a solution in python to solve it once we have the sequence not including the excluded numbers (only python 2.7 sorry)
from random import randint
def gen_random(seq, max_int):
choices = seq * max_int
while True:
yield choices[sum(randint(0, max_int  1) for _ in xrange(len(seq)))]
# To check it
a = gen_random(range(5), 7)
values = [0 for _ in xrange(5)]
for x in xrange(100000):
values[a.next()] += 1
print values
Cheers!!!
 Fernando July 31, 2017Here is a solution in Python.
import random
def gen_random(n, excluded):
posibilities = list(set(xrange(n)).difference(excluded))
while True:
yield random.choice(posibilities)
I am assuming some sort of random number generator is provided. Depending on the random generator provided the question can get harder I am providing the solution for the easiest case
 Fernando July 31, 2017Hello Chris, both my solution and the previous one assume that you can't have duplicates. At the beginning I also was doubting if duplicates were allowed or not but as it is stated I think it makes more sense that you can't have them, also based on the given example. Anyway, the first solution I made accepted duplicates, the code is quite similar to the solution koustav.adorable offered but the visited list was initialized inside the for loop. In that way you check every possible loop starting from each position of the array (also you have to promote lenCurr to a set in order to avoid counting the duplicates more than once).
Cheers :)
@Koustav.adorable gave a solution using O(n) for both time and memory here I am providing a solution that is O(n) for time but O(1) for memory. Coded in a python one liner
def largestSK(seq):
return sum(0 if (pos == value or pos == seq[value]) else 1 for pos, value in enumerate(seq))
@koustav.adorable great solution it helped me greatly to understand the problem, just one thing, maxLen should be 0 not 1. What if you have an empty list or a sorted vector as input?
 Fernando July 29, 2017Thanks for clarifying the problem to me, now the prototype makes perfect sense and also why there can take more than O(n).
I have came up with the following algorithm.
The distance to the closest leaf is the minimum from the next three possible values: the distance from the current node to a leaf, the distance of father of the current node to a leaf or the distance from the current node to the root and from the others root child to a leaf. This algorithm runs in O(n). Code in Python
class node:
def __init__(self, value):
self.value = value
self.left = self.right = None
def compute_distance_between_nodes(n1, n2):
if n1 == None: return None
frontier = [(n1, 0, None)]
while frontier:
current_node, distance, last = frontier.pop()
if current_node == n2:
return (distance + 1, last)
if current_node.left:
frontier.append((current_node.left, distance + 1, current_node))
if current_node.right:
frontier.append((current_node.right, distance + 1, current_node))
return None
def least_height(node):
if node == None:
return 0
else:
return min(tree_height(node.left), tree_height(node.right)) + 1
def closest_leaf(root, target):
if root == target:
return least_height(root)
found_left_side = True
a = compute_distance_between_nodes(root.left, target)
if not a:
found_left_side = False
a = compute_distance_between_nodes(root.right, target)
distance_to_root, last_node = a
distance_from_root = least_height(root.left) if found_left_side else least_height(root.right)
distance_from_last_node = least_height(last_node)
return min(least_height(target), distance_to_root + distance_from_root, distance_from_last_node + 1)
Edit: Apologies for not coding what the question states. The idea of returning a tuple with the node and the distance will work
 Fernando July 27, 2017Solution in python in case of a invalid ip address the function returns 1
import re
ip_regex = r'^(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})$'
def compute_ip(s):
ip_digits = re.match(ip_regex, s)
if not ip_digits:
return 1
digits = map(int, ip_digits.groups())
for x in digits:
if x <= 0 or x > 255:
return 1
ip_value = 0
for pos, x in enumerate(digits):
if pos == 0:
ip_value += x << 24
elif pos == 1:
ip_value += x << 16
elif pos == 2:
ip_value += x << 8
else:
ip_value += x
return ip_value

Fernando
July 26, 2017 I don't understand the question. As stated the closest leaf can be computed as a variation of the height of a tree, but instead of taking the maximum possible height taking the minimum height. That algorithm takes O(n) in relation with the number of nodes (in the worst case you only visit each node once). Also doesn't match the prototype of the function, you only need one node to compute the distance to the leaf. Why the root??.
Code in python
class node:
def __init__(self, value):
self.value = value
self.left = self.right = None
def closest_leaf(node):
if node == None:
return 0
else:
return min(tree_height(node.left), tree_height(node.right)) + 1
Note: You can return a tuple with the node and the height in case you are interested on the node as the problem states.
 Fernando July 26, 2017Solution in python
class stack:
def __init__(self):
self.queue = []
def pop(self):
if len(self.queue) == 0:
raise ValueError("Stack is empty")
temp_queue = []
while len(self.queue) > 1:
temp_queue.append(self.queue.pop(0))
return_value = self.queue.pop(0)
self.queue = temp_queue
return return_value
def push(self, value):
self.queue.append(value)

Fernando
July 25, 2017 Solution in python
def check_sums_pyramid(p, s):
x, paths = 1, [(0, p[0][0])]
for row in p[1:]:
i_paths = []
for position, value in paths:
v1 = row[position] + value
if v1 <= s:
i_paths.append((position, v1))
v2 = row[position + 1] + value
if v2 <= s:
i_paths.append((position + 1, v2))
paths = i_paths
return s in map(lambda x: x[1], paths)
Some comments to the code. Given a pyramid there are 2 ^ (number_of_rows  1) possible paths. To represent the pyramid I am assuming the input will be a list of lists (each list should be one element larger than the previous list). To represent a path I am using a tuple of two elements, one being the last position from which we computed the path and the other the accumulated sum.
Edit: Forgot to mention that to handle negative numbers the code used to prune some paths that are over the sum should be removed.
Cheers.
@ChrisK, Hey hello Chris!! Hope you are doing well. Thanks for your comment. Perhaps I should have used the term a Dijkstra's algorithm variation. I know the code is a little bit convoluted and it doesn't look like it but I am using a priority queue on the code. By the way the elements are added to the queue the ones with a shortest distance are always first, the algorithm is uniformcost search if anybody is interested into digging in the details.
 Fernando July 14, 2017I don't know if I got the question alright but for this question I would use the Dijkstra's algorithm. Compute the Dijkstra's algorithm from every available position and keep a minimum (there might be more than one).
A little bit cumbersome to code but here is an implementation in python.
import sys
from collections import deque
office = [ 'WWWWWWWWW',
'WW O WW',
'WWO OWW',
'WW O WW',
'WWWWWWWWW' ]
def new_positions(current, free_positions):
x, y = current
res = []
for (x_1, y_1) in [(0, 1), (1, 0), (0, 1), (1, 0)]:
if (x + x_1, y + y_1) in free_positions:
res.append((x + x_1, y + y_1))
return res
def find_paths(office):
offices = [(x, y) for (x, row) in enumerate(office) for (y, v) in
enumerate(row) if v == 'O']
free_positions = {}
positions = [ (x, y) for (x, row) in enumerate(office) for (y, v) in
enumerate(row) if v == ' ' or v == 'O' ]
min_total = sys.maxint
min_position = None
for starting_position in positions:
for position in positions:
free_positions[position] = sys.maxint
free_positions[starting_position] = 0
frontier = deque()
frontier.append((starting_position, 0))
while frontier:
position, distance = frontier.popleft()
new_distance = distance + 1
for new_position in new_positions(position, free_positions):
if new_distance < free_positions[new_position]:
free_positions[new_position] = new_distance
frontier.append((new_position, new_distance))
total = 0
for office_position in offices:
total += free_positions[office_position]
if total < min_total:
min_total = total
min_position = starting_position
return min_position, min_total

Fernando
July 13, 2017 Solution in python for the round 1
from random import choice
from string import ascii_lowercase
def stream_of_chars():
while True:
yield choice(ascii_lowercase)
def longest_unique_str(k, max_rounds=1000):
unique_str, max_unique_str = list(), list()
repeated = set()
for round, char in enumerate(stream_of_chars()):
# Maximum number of characters that we can consume from the stream
if round == max_rounds:
break
# If it is a unique character just add it to the list
if char not in repeated:
repeated.add(char)
unique_str.append(char)
if len(unique_str) == k:
return unique_str
else:
# Check if it is a maximal string
if len(unique_str) > len(max_unique_str):
max_unique_str = unique_str
# Find where the repeated character appears on the string
index = unique_str.index(char)
# Update the repeated values and the list of values removing
# the characters that appear before the repeated character
for c in unique_str[:index+1]:
repeated.remove(c)
unique_str = unique_str[index+1:]
return max_unique_str

Fernando
July 13, 2017 Here it is a short solution in python. The cost is n * (x lg x) being x the length of the shortest string
def get_chunks(s, n, step=1):
for x in xrange(0, len(s)n+1, step):
yield s[x:x+n]
def find_anagrams(a, b):
total = 0
s1, s2 = a, b
sorted_str = sorted(b)
if len(b) > len(a):
s1, s2 = b, a
sorted_str = sorted(a)
for chunk in get_chunks(s1, len(s2)):
if sorted(chunk) == sorted_str:
total += 1
return total

Fernando
July 11, 2017 Can be done in linear time.
One pass to tokenize the string, another to create a dictionary to carry the count of the words and one last time to find which is the second most repeated word
import sys
def second_most_repeated_word(sentence):
last = 0;
words_counter = {}
words = []
x = 0
while x != len(sentence):
if sentence[x] == ' ':
words.append(sentence[last:x])
while sentence[x] == ' ': x += 1
last = x
continue
x += 1
if last != x: words.append(sentence[last:x])
for word in words:
if word not in words_counter: words_counter[word] = 1
else: words_counter[word] += 1
first = sys.maxint; second = sys.maxint; f_w = ''; s_w = ''
for word, count in words_counter.items():
if count < first:
if first != sys.maxint:
second = first
s_w = f_w
first = count
f_w = word
if count > first and count < second:
second = count
s_w = word
return s_w
Here is the same basically in a python one liner
from collections import Counter
def second_most_repeated_word(sentence):
return Counter(sentence.split()).most_common(2)[1][0]

Fernando
June 28, 2017 Solution in python using a stack (promoted to a counter as we only have one type of parens). Regarding the input examples. For the input: '(((((' the output should be: '((((()))))' isn't?
def balanceParens(s):
parens_stack = 0
res = ''
for c in s:
if c == '(':
parens_stack += 1
elif c == ')':
if parens_stack == 0: continue
parens_stack = 1
res += c
res += ')' * parens_stack
return res

Fernando
June 27, 2017 To solve it as stated before we can argue the solutions if the k elements have to be contiguous or not.
Let's start when the elements don't need to be contiguous. The naive solution is is to compute all the possible combinations of k elements and return the maximum sum. The cost for this solution is factorial (from the cost of computing the combinations, computing the sum of k elements is constant).
Code in Python:
from itertools import combinations
def getMaxKSum(s, k):
max_sum = 0; numbers = []
for c in combinations(s, k):
r = sum(c)
if r > max_sum:
max_sum = r
numbers = c
return r, numbers
We can improve the cost if we sort the array. In this case the cost would be nlogn from the cost of sorting the array. Solution in python
def getMaxKSum(s, k):
return sorted(s)[k:]
We can improve the cost even further using a heap. For this case the cost is nlogk. Solution in python
from heapq import nlargest
def getMaxKSum(s, k):
return nlargest(s, k)
If it has to be contiguous we can just create a window of k elements to traverse the array. The cost is linear. Functional solution in python
def get_chunks(s, k, step=1):
for x in xrange(0, len(s)k+step, step):
yield s[x:x+k]
def getMaxKSum(s, k):
return max(map(sum, get_chunks(s, k)))

Fernando
June 21, 2017 @guilhebi
With this formula you have the number of breadbutter, pizzas and hamburgers you can eat but not the number of ways you can eat them.
If the number of days is 3 for example you could have: bread, bread, bread; bread, bread, pizza; ...; pizza, bread, bread.
Indeed you could have 3 breadbutters at maximum or 2 pizzas or 1 hamburger (the +1 only applies if the number is greater than 3).
In order to compute the number of ways you have what you have to do is to compute the permutations of those values (permutations with repetitions in this case as you have repeated elements).
Using your formula the number of ways would be:
answerPn / (breadbutter * pizza * burguer)
This is not the complete answer as here we are counting incorrect solutions (for example (pizza, pizza, bread)). In order to give the correct answer you have to compute the number of extra incorrect solutions and subtract it to previous the number. For the case of the three days it is 5. Here are all the possibilities for three days:
{('bread', 'bread', 'bread'),
('bread', 'bread', 'hamburguer'),
('bread', 'bread', 'pizza'),
('bread', 'hamburguer', 'bread'),
('bread', 'hamburguer', 'pizza'),
('bread', 'pizza', 'bread'),
('bread', 'pizza', 'hamburguer'),
('hamburguer', 'bread', 'bread'),
('hamburguer', 'bread', 'pizza'),
('hamburguer', 'pizza', 'bread'),
('pizza', 'bread', 'bread'),
('pizza', 'bread', 'hamburguer'),
('pizza', 'bread', 'pizza'),
('pizza', 'hamburguer', 'bread'),
('pizza', 'hamburguer', 'pizza'),

Fernando
June 19, 2017 Solution in python
class node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def buildABCString(root, value):
res = ""
if root.value == value: return "Undefined"
node = root
while node != None:
if node.value == value: return res
elif value > node.value:
res += "1"
node = node.right
else:
res += "0"
node = node.left
return "Not Found"

Fernando
June 19, 2017 I am assuming the question was referring a BST. You can store the three basically in preorder, inorder and postorder.
If you store the Tree in an inorder fashion you are basically storing the values sorted, in that case you can modify the file without having to rewrite the tree again.
Example:
BST:
6
3 7
1 4 8
File:
1 3 4 6 7 8
Let's say you add 2 on the tree in order to update the file you only have to iterate until the number three and add it before.
 Fernando June 19, 2017If the metadata of the files don't fit on memory I would use using external sorting. You can split the metadata of the 40 million files on chunks that fit on memory and that you can sort. Once all the files are sorted by date you can start transferring them.
If the metadata for all the files can be fit on memory I would use a min heap to get the files in order.
The cost temporal cost for both is approaches is nlogn but the heap approach takes less overhead
Solution in python. The cost is the result of multiplying each character of the string by the values that can be replaced for.
def computeCombinations(string, mapping):
values = [ mapping[x] for x in string ]
results = [[]]
for v in values:
results = [x + [y] for x in results
for y in v]
return results

Fernando
June 12, 2017 Naive solution in python. Cost (n^3). n^2 possible strings and the cost to check if each string is a palidrome is n.
def isPalindrome(s):
return s == s[::1]
def longestPalindrome(s):
max_length = 0
for x in xrange(len(s)):
for y in xrange(x+1, len(s)+1):
if (y  x) > max_length and isPalindrome(s[x:y]):
max_length = (y  x)
return max_length

Fernando
June 12, 2017 The algorithim has already been explained by NoOne. This is the heap solution in a python one liner the cost is nlogk
from heapq import nlargest
from collections import Counter
def getFirstK(array, n):
return map(lambda x: x[1],
nlargest(n, [ (v, k) for k, v in Counter(array).iteritems() ]))

Fernando
June 12, 2017 The basic recursion works as follows: at each point you have a sequence from which you can take 1 or 2 elements (given the constraints). The Base case is when the given sequence of elements is empty, if the if set of numbers is equal to the lucky number (7 in this case) we return true; otherwise it is not a valid solution. Cost O(2^n) in this case we can't use dynamic programming to improve the complexity as we can't use any property to get the best option between any of the multiple ones (I think :P). In other words I haven't been able to find an optimal substructure to prune the recursion
Inputs:
s > list of integers
n > the number of numbers (7 in this case)
v > must be set()
def isLotteryTicket(s, n, v):
if len(s) == 0: return len(v) == n
a = False; b = False
if s[0] <= 5 and len(s) > 1:
x = s[0] * 10 + s[1]
if x not in v:
a = isLotteryTicket(s[2:], n, v.copy().union([x]))
if s[0] not in v:
b = isLotteryTicket(s[1:], n, v.copy().union([s[0]]))
return a or b

Fernando
June 09, 2017 Solution in python. Cost O(k^n).
This is a brute force solution with no heuristics so it is not very efficient, make sure there is a solution or it will loop forever.
Some heuristics may include don't make a movement if you are increasing the total number of disordered pieces or putting adjacent numbers together even if they are not in the right posisition
Example:
solveMaze([[2,3], [1, 'x']])
([[1, 2], [3, 'x']], [(1, 1), (0, 1), (0, 0), (1, 0), (1, 1)])
from itertools import chain
def isSolution(m):
x = list(chain.from_iterable(m))
for p in xrange(len(x)1):
if x[p] > x[p+1]:
return False
return True
def swapMatrix(m, s1, s2):
temp = m[s1[0]][s1[1]]
m[s1[0]][s1[1]] = m[s2[0]][s2[1]]
m[s2[0]][s2[1]] = temp
def computeSuccessors(s1, top, l):
res = []
for p in [(0, 1), (1, 0), (0, 1), (1, 0)]:
s = (s1[0] + p[0], s1[1] + p[1])
if s[0] < 0 or s[0] >= top or\
s[1] < 0 or s[1] >= top or s == l:
continue
res.append(s)
return res
def solveMaze(m):
frontier = [(m, [(len(m) 1, len(m)  1)], (len(m) 1, len(m)  1))]
while len(frontier):
m, s, l = frontier.pop(0)
s1 = s[1]
if isSolution(m):
return (m, s)
for s2 in computeSuccessors(s1, len(m), l):
swapMatrix(m, s1, s2)
frontier.append(([r[:] for r in m], s[:] + [s2], s1))
swapMatrix(m, s1, s2)
return None

Fernando
June 09, 2017 The cost can be difficult to compute but an upper bound could be O(nlogn) assuming that we traverse through all the primes and assume the cost of computing the number of factors given a prime is logn.
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
def computeFactors(n):
if n in primes: return [n]
factors = []
for prime in primes:
while (n % prime) == 0:
factors.append(prime)
n /= prime
if n == 1:
break
return factors

Fernando
June 09, 2017 Cost O(nlogn). The operation of computing if a number contains a 9 is logarithmic as we check each digit we perform this operation n times.
Solution in Python:
def contains9(n):
while (n > 10):
if (n % 10) == 9: return True
n /= 10
if n == 9: return True
return False
def filter9(n):
return filter(lambda x: not contains9(x),
xrange(1, n+1))

Fernando
June 09, 2017 Solution in python. Cost O(nLogn).
Log n is the cost of computing the number of 3 at a given number (we divide the number by 10 each time) and we perform this operation n times.
def numof3(n):
total = 0
while (n > 10):
if (n % 10) == 3: total += 1
n /= 10
if n == 3: total += 1
return total
def count3(n):
total = 0
for x in xrange(1, n+1):
total += numof3(x)
return total

Fernando
June 09, 2017 Open Chat in New Window
There is a n^3 answer. n^2 possible substring with cost n to check if the substring appears again.
 Fernando August 22, 2017