CareerCup

I think the idea with serialization is too complicated... I doubt this was what the interviewer wanted. But, the problem is easy... I didn't check all the corner cases, but this should be the solution (like Setu said... is just a xor between nodes, however the problem with id=0 remains):

public class Solution {
	
	private class Node {
		public Node left;
		public Node right;
		public int id ;
		
		public Node(int id) {
			this.left = null;
			this.right = null;
			this.id = id;
		}
	};

	private Node generateDiff(Node u, Node v) {
		if (u == null && v == null)
			return null;

		int id = 0;
		if (u != null)
			id = u.id;
		if (v != null)
			id ^= v.id;

		Node n = new Node(id);
		n.left = generateDiff(u == null ? null : u.left, v == null ? null : v.left);
		n.right = generateDiff(u == null ? null : u.right, v == null ? null : v.right);
		return n;
	}

	private Node generateBTfromDiff(Node d, Node u) {
		if (d == null && u == null)
			return null;

		int id = d.id;
		if (u != null)
			id ^= u.id;
		if (id == 0)
			return null;
		
		Node n = new Node(id);
		n.left = generateBTfromDiff(d.left, u == null ? null : u.left);
		n.right = generateBTfromDiff(d.right, u == null ? null : u.right);
		return n;
	}

	
	private Node[] buildBT() {
		Node [] roots = new Node[2];
		roots[0] = new Node(1);
		roots[0].right = new Node(3);
		roots[0].left = new Node(9);
		roots[0].right.left = new Node(8);

		roots[1] = new Node(2);
		roots[1].right = new Node(7);
		roots[1].left = new Node(4);
		roots[1].left.right = new Node(5);
		return roots;
	}
	
	private boolean checkBT(Node u, Node v) {
		if (u == null && v == null)
			return true;
		else if (u == null || v == null)
			return false;

		if (u.id != v.id)
			return false;
		
		return checkBT(u.left, v.left) && checkBT(u.right, v.right);
	}
	
	/* The MAIN ---------------------------------------------------------------------------------*/
	public static void main (String args[]) {
		BinaryTreeDifference t = new BinaryTreeDifference();
		Node roots[] = t.buildBT();
		Node d = t.generateDiff(roots[0], roots[1]);
		Node root_1 = t.generateBTfromDiff(d, roots[0]);
		Node root_0 = t.generateBTfromDiff(d, roots[1]);
		System.out.println("root 0 > Same ?  " + t.checkBT(root_0, roots[0]));
		System.out.println("root 1 > Same ?  " + t.checkBT(root_1, roots[1]));
	}
}

Level order/pre-order serialization/deserialization with diff. But, there is a problem, for example, when you have 1 2 3 and 4 5 # you will get diff as 3 3 3. Assume, you get 1 2 3 and 3 3 3 and you have to generate 4 5 #, so 3-3=0 means in fact #... this means you have to code 0 somehow or not allowed 0 in your tree. This is how I would do it.

procedure DFS(G, s, dest, g):
	let marked[1..G.V] keep track of the visited vertices
	call DFS_recursive(G, s, dest, marked, g)
end procedure

procedure DFS_recursive(G, u, dest, marked, pred, g):
	marked[u] = True
	if (u == dest) then:
		return True

	is_dest = False
	for each v such that gcd(u,v) < g:
		if marked[v] == False then:
			is_dest = DFS_recursive(G, u, dest, marked, pred, g)

	return is_dest

# for a pair (u,v) and for a value of g call: 
is_path = call DFS(G, u, v, g)

Note:
1. For gcd(a,b) you can use Euclid's algorithm.
2. If the value of g is the same for any (u,v) call then you can use some sort of dynamic programming (populate G.E as you go) for future queries!

So, here is the implementation in python:

"""
Problem:
--------
Given a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n) 

For example 

s = 'ababac' 

Then substrings are as follow: 

1: s(1, 6) = ababac 
2: s(2, 6) = babac 
3: s(3, 6) = abac 
4: s(4, 6) = bac 
5: s(5, 6) = ac 
6: s(6, 6) = c 

Now, The lengths of LCP of all substrings are as follow 

1: len(LCP(s(1, 6), s)) = 6 
2: len(LCP(s(2, 6), s)) = 0 
3: len(LCP(s(3, 6), s)) = 3 
4: len(LCP(s(4, 6), s)) = 0 
5: len(LCP(s(5, 6), s)) = 1 
6: len(LCP(s(6, 6), s)) = 0 
"""
class LCP:
	@staticmethod
	def build_lps_asc_parent_tables(p:str):
		lps = [0] * len(p)
		asc = [-1] * len(p)
		parent = [i for i in range(0, len(p))]
		
		k = -1
		lps[0] = -1
		parent[0] = 0
		for i in range(1, len(p)):
			while (k >= 0 and p[k+1] != p[i]):
				k = lps[k]
			if p[k+1] == p[i]:
				k += 1
			
			# longest prefix which is also a suffix for p[0:i]
			lps[i] = k;
			parent[i] = parent[k]
			if (asc[i-1]<0 and k>=0):
				asc[i] = i
			elif (asc[i-1]>=0 and k>=0):
				asc[i] = asc[i-1]

		return (lps,asc,parent)

	@staticmethod
	def rotate_asc_subarr(a: list, asc:list):
		i = len(asc) - 1
		while i>=0:
			if asc[i] >= 0:
				# rotate
				end = i
				start = asc[i]
				while (start < end):
					a[start],a[end] = a[end],a[start]
					end -=1
					start +=1
				# jump to the next one
				i = asc[i] - 1
			else:
				i -= 1

	@staticmethod
	def filter_lsp(lsp, parent):
		for i in range(0, len(lsp)):
			if parent[i] != 0:
				lsp[i] = 0
			else:
				lsp[i] += 1
		lsp[0] = len(lsp)
		return lsp
			
class test:
	def do_test_1(self):
		s = "ababac"
		(lsp,asc,parent) = LCP.build_lps_asc_parent_tables(s)
		LCP.rotate_asc_subarr(lsp, asc)
		lcp = LCP.filter_lsp(lsp, parent)
		print(lcp)

t = test()
t.do_test_1()

I see that CLRS cut the string search algorithms from the last edition: KMP, Boyer-Moore, and Rabin-Karp. I also wrote a book (Blueprints of Common Algorithms: A simplified approach to the analysis and implementation of common algorithms) and I didn't include them in it... but it seems that they are needed, so I'm thinking to add them in the next editions.

I'm a veteran, but it made me think a bit of this problem that at first glance can not be done in O (n), yet ...
So, the good news is that it can be done in O(n)... the bad news is that I would not have passed the interview :)), because it took me a while. Today I had a little time and find this idea using KMP. The idea came from the following statement: "the longest prefix which is a good suffix"... exactly what we need.

So, here are the steps:
1. Do the lps table (this is done in O(n) - see KMP algorithm), plus set the oldest parent for each suffix.
2. Rotate all ascending sub-arrays in the lps table ( O(n) )
3. If the parent for a chr is not 0 then set the lps[chr] = 0 (also done in O(n) ) and for the first char set len(s) - the longest
So, as you can see you need 3 traversal for the initial string no matter how long it is (how big is n)... thus O(3n) = O(n)

Here is an example:
step 1:
s      = a b a b a c
lps    = 0 0 1 2 3 0
parent = 0 1 0 1 0 6
- this is done in O(n)

step 2:
s      = a b a b a c
lps    = 0 0 3 2 1 0
parent = 0 1 0 1 0 6

step 3:
s      = a b a b a c
lps    = 6 0 3 0 1 0
parent = 0 1 0 1 0 6
Done.

nlog(n) ?

The most classic dynamic programming problem I know :).

dp[1] = 1
for i = 2, n do
	dp[i] = 1
	pred[i] = i
	for j = 1,i do
		if a[i] < a[j] and dp [i] < dp[j] + 1
			dp[i] = dp[j] + 1
			pred[i] = j

lexicographic_permutation(arr):
		n = length(arr)
		len = n - 1
		p = {0, 1, 2, ..., n-1}
		
		while True:
			k = len - 1
			while p[k] > p[k+1]:
				k -= 1

			if k >= 0:
				l = len
				while p[k] > p[l]:
					l -= 1
		
				p[k],p[l] = p[l],p[k]

				reverse p[k + 1] up to p[n]
				
				for i=0,n do
					print(a[p[i]])
			else:
				break

This is how I would do it... some sort of DFS with a little dynamic programming.
So, if for a current vertex that is visited all the path for all adjacent vertices goes T, then all the paths from the current vertex go to T also. If this is done recursively... it should give you the right answer. Basically, if conn[S] == True then NECESSARILY CONNECTED.

connected(v, T)
	visited[v] = True
	
	flag = False
	for u in adj(v) do
		if  (u == T) OR // this is the ending vertex, so True
			(visited[u] == True AND conn[u] == True) then // this is visited and also the paths from it goes to T
			flag = True
		
		if visited[u] == False then
			flag = connected(u, T)
			// no need to check further...
			if flag == False then
				break;

	conn[v] = flag
	return flag
	
MAIN:
	flag = connected(S, T)
	if flag == False then
		NOT NECESSARILY CONNECTED
	else
		NECESSARILY CONNECTED

Basically, this is a combinatorics problem combined with dynamic programming.
So, compute the delta=sum(MAX)-sum(MIN) for all k subsets that can be made and the smallest one is the solution.
Because the array/list is circular, the maximum number of elements that can be used in a subset with the last element from the list is n-k, so I used another list b that generates all list that can be made.

Below is the brute-force approach, but using dynamic programming the complexity can be improved considerably. That is, if a split has been already computed, then there is no need to do it again, instead, first time must be recorded in a table.

Anyway, the complexity of the brute-force solution below is ~O(k*2^n).

Plus, if the table is implemented as a self-balancing binary tree(i.e. red-black tree), then the lookup is improved to logarithmic.

subset(S, b, k, sol, min)
	if size(S) == k then
		if sum(S) <= n then
			S[head] = s[head] + (n-sum(S))

			// we have a candidate solution here (k subsets from list b)
			// if the candidate's delta is less than the current known one, then update
			delta = do_delta(b, S) // delta does MAX-MIN for split S
			if delta < min then
				min = candidate
				sol = S

		// now lets generate another solution
		// first pop the head of the stack until it can be incremented thus
		// to generate another candidate solution
		POP(S)
		while S[head] >= (n-k+1) and head > 0 do
			POP(S)
		if head > 0 then
			S[head] = S[head] + 1
			subset (S, b, k, sol, min)
	else if sum(S) < n then
		PUSH(S, 1) // head = head +1 and S[head] = 1
		subset (S, b, k, sol, min)
	else
		POP(S)

do_dMaxMin(b, k)
	let min = infinity // minimum delta: sum(MAX)-sum(MIN)
	let sol = NIL // the solution (the split)
	let S = NIL // a stack
	call subset(S, b, k, sol, min)
	return (sol, min)

MAIN:
	input: let a be the list of numbers
	input: let k be the number of subsets
	let b be the current list of numbers
	let sol to be the best split
	let min to be the minimum delta
	
	sol = NIL
	min = infinity
	b = a
	for i=0 to n-k do
		if i>0 then
			// this moves i elements from the beginning of a to the end of it (since a is circular)
			b = concat(a[i+1:n], a[1:i])
			
			// lets see the candidate solution
			(candidate_sol, candidate_delta) = do_dMaxMin(b,k)
			if (candidate_delta < min) then
				sol = candidate_sol
				min = candidate_delta
	return (sol, min)