- G: a vector of strings, find a pair with max of strlen(a) * strlen(b)
1. O(n*k): get std::bitset() of each string
2. O(nlgn): sort strings by length
3. O(n^2): loop from longest. Pruning: record current max strlen(a)*strlen(b), will not check any strlen(c) * strlen(d) < strlen(a) * strlen(b)
http://www.quora.com/Given-a-dictionary-of-words-how-can-we-efficiently-find-a-pair-words-s-t-they-dont-have-characters-in-common-and-sum-of-their-length-is-maximum
- G: count reversed pairs in an unsorted array
Count it when conducting Merge Sort. O(nlgn)
- G: a 0-1 valued map, filled by a rectangle or a triangle, find which one it fills..
If not about computer vision... from[0,0] scan left->right op->down, you will find 1st vertex; rotate 90' do another scan from [width-1, 0] to find 2nd. Just to see how many vertices you find... not quite sure about this solution though.
- G: several boxes for each can be put to another or not, find minimum area to contain all boxes
Greedy.
??DP
- GEPI: find celebrity
O(n). Stand in a row, query pair by pair using know(i, j). Then pick the survivor.
- FB: int array, find continuous elements with sum of k, provided.
s[i] = sum(0..i), and hash each. for each i, check if (k - i) is in the hash