来报个uber的onsite面经回报地里【一亩三分地论坛面经版】 - Powered by Discuz!


来报个uber的onsite面经回报地里【一亩三分地论坛面经版】 - Powered by Discuz!
第一轮,2 on 1,白板写valid sudoku,lc原题,lz紧张了一下,仔细test,结果怎么查怎么对,面试官也不出声。。还以为有bug,结果果然是bug free。面试官满意之后,仔细讨论这段代码在memory中的变化,在for循环之外和之内建立对象在底层的区别,和被大量调用时时间的区别。然后考android的listview的design。其中设计10gb的item如果想显示在特定屏幕的view上面,底层怎么优化,因为太大没办法一下load在memory里。然后考了object pool。然后还考了一些细节的概念和处理,记不太清楚了,总之被问了很多。然后提问题,临走时表示很满意,后几轮加油。
http://blog.csdn.net/it_man/article/details/8225477
  (6)。 避免在循环体中声明创建对象,即使该对象占用内存空间不大。
  这种情况在我们的实际应用中经常遇到,而且我们很容易犯类似的错误,例如下面的代码:

  Java代码

  for (int i = 0; i < 10000; ++i) {

  Object obj = new Object();

  System.out.println("obj= " + obj);

  }

  上面的做法会浪费较大的内存空间。正确的做法如下所示:

  Java代码

  Object obj = null;

  for (int i = 0; i < 10000; ++i) {

  obj = new Object();

  System.out.println("obj= "+ obj);

  }

  采用上面的第二种编写方式,仅在内存中保存一份对该对象的引用,而不像上面的第一种编写方式中代码会在内存中产生大量的对象引用,浪费大量的内存空间,而且增大了垃圾回收的负荷。因此在循环体中声明创建对象的编写方式应该尽量避免。

第二轮,1 on 1, 用电脑coding,本以为eclipse,没想到却是hacker啥的一个网页编译器,用java。题目还是一道valid sudoku,lz上一轮做过,所以瞬间写完,但要求各种unit test,大概折腾了20多分钟后,就开始跟我讨论android应用的design,问我一些app的设计思路,感觉就是考design pattern,然后我还把我之前的android app跟他说了下,结果要看我代码,然后我就跟他demo一下app,说了些我当时app的优缺点。然后时间到了。很满意的走了
http://massivealgorithms.blogspot.com/2014/06/leetcode-valid-sudoku-darrens-blog.html

第三轮,2 on 1,上来先自我介绍。然后又是白板coding,考了2道题,但许许多多的follow up。第一题自己写一个hashtable。分别实现open addressing和separate chaining,大概讲讲加上伪代码就行。hashfunction怎么实现,string的hashcode怎么实现的。等等follow up我现在都不记得了,还问了好多细节。然后问如果我想记录insert的顺序怎么办,怎么设计这个hashtable。然后又问了链表的删除等细节的问题,双链表啊单链表啊。。。面试官俩人都很满意。lz掌握细节还可以,所以都是秒答,秒写代码,所以到这时间还有15分钟左右.

JDK String.hashCode()
   public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;

    }

JDK 8 Hashmap.hash
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
JDK 7 Hashmap.hash
    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);

    }

LinkedHashMap
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }

    }



然后又出了一道design的题,竟然还要写代码的。题目就是类似google搜索引擎里面输入时候,关于你输入开头的所有内容在你的搜索记录里的要都显示在下面。例如:你输入u,会显示uber, unique, unbelieve。你输入ub时候只会显示uber了。我先说了用hashmap,然后自己分析了一下tradeoff,因为太占空间了嘛,然后又想了想,我就说可以用trie tree,面试官此时表现的很兴奋,然后让我说说trie的思路。我当时就感觉是不是从来没有面试者回答过trie的方法啊。。。不至于啊。。。然后就只让我实现search部分的代码。我用的hashmap,写个类就好了。不难。然后俩人很满意,说very good job。然后又问我why uber。然后让我问问题了。

第四轮,1 on 1 manager轮,linkedin过来的,这轮出乎意料没有写一行代码,纯聊天,和设计思路。因为lz两年前有创业经历,所以主要聊当时我们的app的设计思路,tradeoff和改进地方之类的。然后就让我demo我在研究生期间上课做的那个app,说design pattern和算法,因为里面涉及machine learning的部分。然后我跟他说了些uber不足的地方,看起来他很有兴趣,然后问我我觉得如果改进,说完他貌似比较满意。然后就聊些有的没的。
Read full article from 来报个uber的onsite面经回报地里【一亩三分地论坛面经版】 - Powered by Discuz!

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts