Pramp - mock interview experience
February 23, 2016
Read the article today from hackerRank blog on facebook:
http://venturebeat.com/2016/02/18/how-i-landed-a-google-internship-in-6-months/?utm_content=buffer5c137&utm_medium=social&utm_source=facebook.com&utm_campaign=buffer
Pramp - free mock interview website - Great! give it a try!
Julia never had chance to give other people code interview before, and then, she will have one on Pramp. Excited!
Algorithm for the interview being an interviewer:
Find The Duplicates
Read the article today from hackerRank blog on facebook:
http://venturebeat.com/2016/02/18/how-i-landed-a-google-internship-in-6-months/?utm_content=buffer5c137&utm_medium=social&utm_source=facebook.com&utm_campaign=buffer
Pramp - free mock interview website - Great! give it a try!
Julia never had chance to give other people code interview before, and then, she will have one on Pramp. Excited!
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
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.
Linear time <- O(n+m) <- you missed the opportunity to ask yourself the question.
What a fun night to play algorithm again.