Round 1: [System Design]

• Design Amazon Recomendation System

Round 2:

• Design File System to search files with critieries

Round 3:

• Variation of https://leetcode.com/problems/concatenated-words/ except return words that word is concatenated from.

  My solution

  time complexity : O(m^2*N), m - stands for one word length, n-words number
  public List<List<String>> wordBreak(List<String> wordDict) {
  	  Set<String> wordSet = new HashSet<>(wordDict);
  
  	  List<List<String>> solution = new ArrayList<>();
  
  	  for (String word : wordDict) {
  		LinkedList<String> list = new LinkedList<>();
  		Boolean[] memo = new Boolean[word.length()];
  
  		wordBreak(word, 0, wordSet, list, memo);
  
  		solution.add(list);
  	  }
  
  	  return solution;
  	}
  
  	private boolean wordBreak(String s, int index, Set<String> wordDict, LinkedList<String> list,
  	  Boolean[] memo) {
  	  if (index == s.length()) {
  		return true;
  	  }
  
  	  if (memo[index] != null) {
  		return memo[index];
  	  }
  
  	  for (int i = index; i < s.length(); i++) {
  		String prefix = s.substring(index, i + 1);
  
  		if (wordDict.contains(prefix)) {
  		  list.add(prefix);
  
  		  memo[index] = wordBreak(s, i + 1, wordDict, list, memo);
  
  		  if (memo[index] && prefix.length() < s.length()) {
  			return true;
  		  } else {
  			list.removeLast();
  		  }
  		}
  	  }
  
  	  memo[index] = false;
  
  	  return false;
  	}

Round 4:

• https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

  My solution

  linear time complexity: O(N) both space and time
  // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
  	if (root == null) {
  	  return null;
  	}
  
  	StringBuilder sb = new StringBuilder();
  
  	Queue<TreeNode> queue = new LinkedList<>();
  	queue.add(root);
  
  	while (!queue.isEmpty()) {
  	  if (sb.length() > 0) {
  		sb.append(":");
  	  }
  
  	  int size = queue.size();
  
  	  for (int i = 0; i < size; i++) {
  		TreeNode node = queue.poll();
  
  		if (i > 0) {
  		  sb.append(";");
  		}
  
  		sb.append(node != null? node.val: "null");
  
  		if (node != null) {
  		  queue.add(node.left);
  		  queue.add(node.right);
  		}
  	  }
  	}
  
  	return sb.toString();
    }
  
    // Decodes your encoded data to tree.
  	  public TreeNode deserialize(String data) {
  		if (data == null) {
  		  return null;
  		}
  
  		String[] levels = data.split(":");
  
  		TreeNode root = new TreeNode(Integer.parseInt(levels[0]));
  
  		Queue<TreeNode> queue = new ArrayDeque<>();
  		queue.add(root);
  
  		for (int i = 1; i < levels.length; i++) {
  		  String s = levels[i];
  
  		  String[] nodes = s.split(";");
  
  		  for (int j = 0; j < nodes.length; j += 2) {
  			TreeNode node = queue.poll();
  			String left = nodes[j];
  			String right = nodes[j + 1];
  
  			if (!left.equals("null")) {
  			  node.left = new TreeNode(Integer.parseInt(left));
  			  queue.add(node.left);
  			}
  
  			if (!right.equals("null")) {
  			  node.right = new TreeNode(Integer.parseInt(right));
  			  queue.add(node.right);
  			}
  		  }
  		}
  
  		return root;
  	  }

I was super nervous and failed the interview. i would recommend to treat interview easily and to focus on hard problems and be prepared to the variations of the problems. I also have attached my solutions to the problems that i decided to solve after the interview. Try to write clean code and very simple solution.