[Interview type questions] First pair non matching leaves

Input: Given two (binary) trees, return the first pair of non-matching leaves Tree 1: A, B, C, D, E, null, null Tree 2: A, D, B
Output: (E,B)

Example:
Tree1 :              
      A
     /   \
   B     C
  /  \
D    E    

Tree2 :
    A
  /    \
D     B

Solution:

 static class TreeNode {
  public TreeNode(char v) { val = v;}
  char val;
  TreeNode left;
  TreeNode right;
 }
 
 static class MyIterator {
  Stack<TreeNode> stack = new Stack<>();
  MyIterator(TreeNode root) {
   pullAll(root);
  }
  
  void pullAll(TreeNode node) {
   while(node != null) {
    stack.push(node);
    node = node.left;
   }
  }
  
  public TreeNode next() {
   TreeNode next = stack.pop();
   if (next.right != null) {
    pullAll(next.right);
   }
   return next;
  }
  
  public TreeNode nextLeaf() {
   while(hasNext()) {
    TreeNode next = next();
    if (next.left == null && next.right == null) {
     return next;
    }
   }
   return null;
  }
  
  boolean hasNext() {
   return stack.isEmpty() == false;
  }
 }
 
 public static void main(String[] args) {
  TreeNode root1 = new TreeNode('A');
  root1.left = new TreeNode('B');
  root1.right = new TreeNode('C');
  root1.left.left = new TreeNode('D');
  root1.left.right = new TreeNode('E');
  TreeNode root2 = new TreeNode('A');
  root2.left = new TreeNode('D');
  root2.right = new TreeNode('B');
  char[] res = findFirstNonMatch(root1, root2);
  System.out.println(res);
 }
 
 static char[] findFirstNonMatch(TreeNode root1, TreeNode root2) {
  MyIterator iter1 = new MyIterator(root1);
  MyIterator iter2 = new MyIterator(root2);
  while(true) {
   TreeNode leaf1 = iter1.nextLeaf();
   TreeNode leaf2 = iter2.nextLeaf();
   if (leaf1 == null || leaf2 == null) break;
   if (leaf1.val != leaf2.val) {
    return new char[] {leaf1.val, leaf2.val};
   }
  }
  return new char[] {};
 }
       

[Interview type questions] Construct Binary search tree from given preorder array

Input: Give a preorder array
Output: Tree root

Example: If the given traversal is {10, 5, 1, 7, 40, 50}, then the output should be root of following tree.
     10
   /   \
  5     40
 /  \      \
1    7      50

Solution:

 static class TreeNode {
  public TreeNode(int v) { val = v;}
  int val;
  TreeNode left;
  TreeNode right;
 }

 public static void main(String[] args) {
  //       10
  //    5     40
  //  1  7       50
  int pre[] = new int[] { 10, 5, 1, 7, 40, 50 };
  int size = pre.length;
  TreeNode root = constructTree(pre, 0, size - 1);
  printInorder(root);
 }

 public static TreeNode constructTree(int[] pre, int l, int h) {
  if (l > h) return null;
  if (l == h) return new TreeNode(pre[l]);
  TreeNode root = new TreeNode(pre[l]);
  int ind = l + 1;
  // Find the first index which is greater than or equal to root
  for (int i = l + 1; i <= h; i++) {
   if (root.val < pre[i]) {
    ind = i;
    break;
   }
  }
  root.left = constructTree(pre, l + 1, ind - 1);
  root.right = constructTree(pre, ind, h);
  return root;
 }

 public static TreeNode constructTreeIterative(int[] pre, int l, int h) {
  if (l > h) return null;
  Stack<TreeNode> stack = new Stack<>();
  TreeNode root = new TreeNode(pre[l]);
  stack.push(root);
  for (int i = l + 1 ; i <= h ; i++) {
   int val = pre[i];
   // Handle left side
   if (stack.peek().val > val) {
    TreeNode left = new TreeNode(val);
    stack.peek().left = left;
    stack.push(left);
   } else {
    // Handle right side and find its paraent
    TreeNode rightParent = null;
    while(!stack.isEmpty() && stack.peek().val < val) {
     rightParent = stack.pop();
    }
    rightParent.right = new TreeNode(val);
    stack.push(rightParent);
   }
  }
  return root;
 }

 public static void printInorder(TreeNode node) {
  if (node == null) {
   return;
  }
  printInorder(node.left);
  System.out.print(node.val + " ");
  printInorder(node.right);
 }
       




[Interview type questions] Divide friends into two groups, and people in the same group do not know each other

Input: Give edges to represent their relations.
Output: Divide the friends into two groups, and people in the same group do now know each other.

Example: Give 4 persons. [0, 1] [1, 2] [1, 3]
         0 and 1 know each other, 1 and 2 know each other...
         We can take 0,2 as group 1 and 1,3 as group 2.

Solution: Use bipartite graph with BFS to resolve this problem:

  int n = 4;
  int[][] relations = new int[][] { { 0, 1 }, { 1, 2 }, { 2, 3 } };

  // Build a graph and initialize groups
  HashMap<Integer, Set<Integer>> graph = new HashMap<>();
  int[] group = new int[4];
  Arrays.fill(group, -1);
  for (int[] edge : relations) {
   Set neighbors = graph.getOrDefault(edge[0], new HashSet<>());
   neighbors.add(edge[1]);
   graph.put(edge[0], neighbors);
  }
  // BFS, start with 0
  Queue queue = new LinkedList<>();
  queue.offer(0);
  int groupdId = 0;
  group[0] = groupdId;
  while(queue.isEmpty() == false) {
   int v = queue.poll();
   groupdId = 1 - group[v];
   // Get its neighbors
   // No neighbors..
   if (graph.get(v) == null) continue;
   for (int neighbor : graph.get(v)) {
    if (group[neighbor] == -1) {
     group[neighbor] = groupdId;
     queue.offer(neighbor);
    } else if (group[neighbor] == group[v]) {
     // It cannot be divided into two group. Invalid bipartite graph
     break;
    }
   }
  }
  
  for (int g : group) {
   System.out.println(g);
  }
       

Serialize/De-serialize data to a file using Flatbuffers

Read & Write

       

#include "flatbuffers/util.h"

flatbuffers::FlatBufferBuilder builder;

// Create something using builder
// ......

// Save to file
bool result = flatbuffers::SaveFile(filename.c_str(),
                                      (const char *) builder.GetBufferPointer(),
                                      (size_t) builder.GetSize(), true);

// Load from file
std::string buffer;
result = flatbuffers::LoadFile(fileName, true, &buffer);
printf("\nLoadFile Result = %d", result);


// You can write your own Save/load function
bool MySaveFile(const char *name, const char *buf, size_t len,
                     bool binary) {
  std::ofstream ofs(name, binary ? std::ofstream::binary : std::ofstream::out);
  if (!ofs.is_open()) return false;
  ofs.write(buf, len);
  return !ofs.bad();
}

bool MyLoadFileRaw(const char *name, bool binary, std::string *buf) {
  std::ifstream ifs(name, binary ? std::ifstream::binary : std::ifstream::in);
  if (!ifs.is_open()) {
    return false;
  }
  if (binary) {
    // The fastest way to read a file into a string.
    ifs.seekg(0, std::ios::end);
    auto size = ifs.tellg();
    (*buf).resize(static_cast(size));
    ifs.seekg(0, std::ios::beg);
    ifs.read(&(*buf)[0], (*buf).size());
  } else {
    // This is slower, but works correctly on all platforms for text files.
    std::ostringstream oss;
    oss << ifs.rdbuf();
    *buf = oss.str();
  }
  return !ifs.bad();
}
       
 

Find out what all symbols are exported from a ELF shared object

 $ readelf -Ws XXXX.so