来自mittbs 面经 http://www.mitbbs.com/article_t/JobHunting/32923781.html

留下重点＝＝＝＝＝》
http://www.mitbbs.com/article/JobHunting/32899043_0.html
https://www.evernote.com/shard/s576/sh/%207e58b450-1abe-43a8-bf82-
fbf07f1db13c/049802174415b418a2e65f75b744ab72
http://www.mitbbs.com/article/JobHunting/32777529_0.html




面经
各位久等了。
1.
/**
Implement stairs(N) that prints all the ways to climb up a N-step-stairs    
                                                                     where 
one can either take a single step or double step.                           
                                                                        We'
ll use 1 to represent a single step, and 2 to represent a double step.

stairs(3)
111
12
21

There might be two requirements:
1. print
2. collect solutions in a list
**/




3. First non repeated character in string. Follow up is one pass solution.
http://www.geeksforgeeks.org/given-a-string-find-its-first-non-


5. Letter combination of phone book
https://leetcode.com/problems/letter-combinations-of-a-phone-number/

6.
public interface PointsOnAPlane {

    /**
     * Stores a given point in an internal data structure
     */
    void addPoint(Point point);

    /**
     * For given 'center' (which isn't necessarily the origin)
     * point returns a subset of stored points that are closer
     * to the center than others.
     *
     * E.g.
     * Stored:
     * (0, 1)
     * (0, 2)
     * (0, 3)
     * (0, 4)
     * (0, 5)
     *
     * findNearest(new Point(7, 3), 3) -> (0, 2), (0, 3), (0, 4)
     */
    Collection<Point> findNearest(Point center, int n);

    class Point {
        final int x;
        final int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

7. 3Sum
https://leetcode.com/problems/3sum/

8..
/**
* Given two words as Strings, determine if they are isomorphic. Two words 
are called isomorphic
* if the letters in one word can be remapped to get the second word. 
Remapping a letter means replacing all
* occurrences of it with another letter while the ordering of the letters 
remains unchanged. No two letters
* may map to the same letter, but a letter may map to itself.
*
* Example:
*   given "foo", "app"; returns true
*     we can map 'f' -> 'a' and 'o' -> 'p'
*
*   given "foo", "boa"; returns false
*     we can map 'f' -> 'b', 'o' -> 'o', we can't map 'o' -> 'a'
*
*   given "bar", "foo"; returns false
*     we can't map both 'a' and 'r' to 'o'
*
*   given "turtle", "tletur"; returns true
*     we can map 't' -> 't', 'u' -> 'l', 'r' -> 'e', 'l' -> 'u', 'e' ->'r'
*
*   given "ab", "ca"; returns true
*     we can map 'a' -> 'c', 'b' -> 'a'
*/

9. Lowest common ancestor of binary tree
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree

10. Given array containing 3 repeated and unsorted letters m, l, h, do in 
place sort so that l's are on the left, m's in the middle and h's on the 
right.

11. Max points on a line
https://leetcode.com/problems/max-points-on-a-line/

12. A simple DP problem that I haven't seen. Really straight forward like a 
sequence alignment. 

13. Given positive integer n, return the list of squares that sum up to n. 
Note that length of the returned list should be the shorted of all such 
lists.
E.g. 5 => 4, 1
6 => 4, 1, 1
8 => 4, 4
11 => 1, 1, 9
12 -> 4, 4, 4

14. Binary tree in order traversal into a doubly circular linked list (
return is a list that represents in order traversal)

15. Given binary tree tell if it is binary search tree. O(lgn) space 
complexity preferred (average case)

16. Design rate limiter

17. Design Tiny URL API

18. Design news Feed API

Other design problems I couldn't recall clearly but topics involved: 
inverted index, consistent hashing, consistency level and partitioning (CAP)
, and map-reduce.