Mock interview experience (I)

February 23, 2016
   
 Julia never had chance to give other people code interview before, and then, she will have one. Excited! Finally, she got her first experience.

 Algorithm for the interview being an interviewer:

 Find The Duplicates

Given two arrays of US social security numbers: Arr1 and Arr2 of lengths n and m respectively, how can you most efficiently compute an array of all persons included on both arrays?

Solve and analyze the complexity for 2 cases:
1. m ≈ n - lengths are approximately the same
2. m ≫ n - one is much longer than the other

 Julia worked on the question by herself first, around 20 minutes (no coding) before she reads :

1. Brute force solution, time complexity: O(nm), go through two loops, in other words, go through Arr1, and for each element in Arr1, check if it is in Arr2. 

2. Can we do better than O(nm)? Of course. 

case 1: m ≈ n - lengths are approximately the same

  sort Arr1, it takes time O(nlogn); 

  and then, for each node in Arr2, find it is duplicated one in Arr1. Use binary search, each search takes O(logn), m elements, so time complexity is O(mlogn)

  So, time complexity in total: O(nlogn) + O(mlogn) ≈ O(nlogn), which is better than brute force one: O(nm) time complexity

  <-  Julia, you missed another important step: Ask if the arrays are sorted or not? 

  <-  Julia, if two arrays are sorted, what is the optimal time complexity? 
        Linear time <-  O(n+m) <- you missed the opportunity to ask yourself the question. 
  <-   Julia, algorithm time complexity - How to say that? Level 1 (sorted array time complexity), level 2, asking level 2 in detail (assuming that two arrays are sorted, now what? linear vs nLogm vs n^2).