Longest common prefix - LCP - facebook code lab

July 25, 2016

Write a function to find the longest common prefix string amongst an array of strings.

Longest common prefix for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2.

As an example, longest common prefix of "abcdefgh" and "abcefgh" is "abc".

Given the array of strings, you need to find the longest S which is the prefix of ALL the strings in the array.

Example:

Given the array as:

[

  "abcdefgh",

  "aefghijk",

  "abcefgh"
]

The answer would be “a”.

Plan to work on the problem

Blog reading:

1. Talk about CMU computer science - network security course in 2015 - good to know the college - computing teaching
http://article.heron.me/2015/05/cmu-nctu-final.html

course project:
https://github.com/heronyang/youtube_fake_view/blob/master/doc/paper.pdf

2. Four algorithm questions to review
http://codechen.blogspot.ca/search/label/interview

Inspired by the above blog, write code for binary tree path sum - two with same value checking:
https://gist.github.com/jianminchen/b5aa95fb574fcb6f4135f88a4b47d5f8

checklist of code style and design issues:
https://gist.github.com/jianminchen/b5aa95fb574fcb6f4135f88a4b47d5f8
2.1. if statement is minimum - avoid using if statement, tips: let it fall through base case.
2.2. code style:
   Readable code
   Clean code
2.3. use LINQ to code select clause like SQL statement
2.4. Avoid early return when the duplicate path sum is added.
2.5. Let main function to take care of discussion of two path sum with same value

3. Find k most frequent numbers in the array
Problem:
  // nums = [5, 3, 1, 1, 1, 3, 73, 1]
  // k = 1
  // return [1]
 
  // k = 2
  // return [1, 3]
 
  // k = 3

  // return [1, 3, 5]


First, go through the array once, and keep the count for every distinct value:

We can use LINK to call order by and then get Top k values.


But, in the analysis of the top k values in the array -

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/


1. sorting the array   O(nlogn)
2. use selection sort O(nk)
3. use sorting
4. use min heap
5. use max heap
6. use temporary array
7. use order statistics

7A. randomized selection algorithm - a dertministic algorithm that runs in O(n) in the worst case

 http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf
1. the idea is to divide n items into n/5 sets (denoting m sets), each contains 5 items. O(n)
2. Find the median of each of the m sets. O(n)
3. Take those m medians and put them in another array.  Use Dselection() to recurisively calculate the median of these medians. Call this x. T(n/5)
4. ...

7B. Use QuickSort partition algorithm to partition around the kth largest number O(n).

7C. Sort the k-1 elements (elements greater than the kth largest element) O(klogk). This step is needed only if sorted output is required.