CareerCup

There is a n^3 answer. n^2 possible substring with cost n to check if the substring appears again.

def max_substring(s):
     long_repeated = ""
     for x in xrange(len(s)):
         for y in xrange(x+1, len(s)+1):
             t = s[x:y] 
             if t in s[x+1:] and len(t) > len(long_repeated):
                 long_repeated = t
     return long_repeated

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

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])

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())

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

@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 :)

Perform 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

Solution 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

@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.

I 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 :)

This 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', '2017-01-1')")
c.execute("INSERT INTO Student VALUES ('1', 'B', '2017-07-1')")
c.execute("INSERT INTO Student VALUES ('1', 'C', '2017-12-1')")

conn.commit()

for row in c.execute(SQL_QUERY):
    print row

conn.close()

@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.

To @sohail and @nishant_ki_maa_ka those solutions are not doing exactly what the question is asking. The dictionary doesn't remember if two letters were consecutive or not
for the given example it will return "a4b3" which is incorrect

Solution in python using itertools

from itertools import groupby

def compress(a):
     s = ''
     for x in [list(g) for k, g in groupby(a)]:
         s += x[0] + str(len(x))
     return s

@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

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!!!

Here 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

Hello 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?

Thanks 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

Solution 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

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.

Solution to problem number 2 in python.

def flatten(seq):
    r = []
    for x in seq:
        if type(x) == list:
            r += flatten(x)
        else:
            r.append(x)
    return r

Solution 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)

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.

Solution in python, no recursion

def compute_combinations(s):
	res = ['']
	for c in s:
		res = [x + c.lower() for x in res] + [x + c.upper() for x in res]
	return res

@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 uniform-cost search if anybody is interested into digging in the details.

I 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

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

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

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]

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

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)))

@guilhebi
With this formula you have the number of bread-butter, 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 bread-butters 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 / (bread-butter * 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'),

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"

I am assuming the question was referring a BST. You can store the three basically in pre-order, in-order and post-order.
If you store the Tree in an in-order 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.

If 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

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

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() ]))

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

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

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

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))

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

Solution in python.
Cost O(n). (We update the variables once in the loop constant time computed n times => O(n))

def fib():
     a = 0; b = 1
     while True:
             yield a
             temp = a
             a += b
             b = temp

The brute force can be computed using the powerset the cost is 2^n

def powerset(a):
    solutions = [[]]
    for x in a:
        solutions = solutions[:] + map(lambda r: r + [x], solutions)
    return solutions

def computesum(sequence, desired_sum):
    results = []
    for x in powerset(sequence):
        if desired_sum == sum(x):
            results.append(x)
    return results

As for the recursive version I like it more this version. You recurse using the set of elements and the sum.
C(S, sum)
if sum < 0: do nothing
if sum == 0:
S is a valid subset
else:
for each i in S do C({S} - i, sum - i)
Here is the code that does it in python

def computesum(sequence, desired_sum):
    results = []
    if desired_sum == 0:
        return [answers]
    elif desired_sum > 0:
        for e in sequence:
            s = sequence.copy()
            s.remove(e)
            results.extend(computesum(s, desired_sum - e))
    return results

Please take note that the previous code returns the complements if you want to return the actual sets you can pass the original set as a function parameter and return the complement when desired_sum is 0
Finally here is a nice iterative version that computes the same as before pruning the subsets that can't contain a valid sum

def computesum(a, s):
    solutions = [[]]
    for x in a:
        solutions = solutions[:] + map(lambda r: r + [x], solutions)
        solutions = filter(lambda x: sum(x) <= s, solutions)
    return filter(lambda x: sum(x) == s, solutions)