Interview Corner Misc


http://www.mitbbs.com/article_t/JobHunting/32542339.html
Rocket Fuel
网上交简历,当天收到hr回信,过两天和hr电话chat半个小时,主要问问背景和看你是
不是serious applicant。完了发来online test 5hour。我做的auto racer。没有
follow他的hints选了最优算法但是由于编不出balanced avl tree有个test case没过
,还是个给了电面,面试官是三哥,电面是之前有人贴过的ad query题,给出了大家讨
论的最优答案,又拓展到分布式系统。才说了半个小时面试官突然说时间到了问我有没
什么问题,我看他很急就说没问题就bye了。本来以为肯定挂了因为预定要一个小时,
结果过了两天recruiter说feedback very positive让我去onsite有点莫名其妙。

onsite中午和一个cmu毕业的topcoder 2000+的nb phd吃饭闲聊了一下,下午面了四个
人,三个三哥一个asian。两个big data infrastucture(最后端)的, 两个serving 
infrastrucre(中后端)的。所有题目在之前rocket fuel的帖子里或者leetcode都能
找到,除了一道挺有意思的题

给定一个n*n的board里面是0或1.算出里面独立0group的数量。比如

0 0 1 1 1
0 1 1 1 0
1 1 1 1 0
1 0 1 1 1
1 1 1 1 1
onsite时因为很多题都见过经常迅速讲一下思路就开始coding,感觉交流不够
。面试的时候交流还是第一位的,如果跑上来就写代码写的再好面试官对你印象也未必
好(可能还会觉得你是练过的),因为他会把你当成未来的coworker所以交流的融洽是
很重要的。rf家的big data infrastructure全部是三哥,我觉得这也是我挂的一个原
因,建议申请ai optimization那些核心组,那才是他们家的精髓所在。

onsite时因为很多题都见过经常迅速讲一下思路就开始coding,感觉交流不够
。面试的时候交流还是第一位的,如果跑上来就写代码写的再好面试官对你印象也未必
好(可能还会觉得你是练过的),因为他会把你当成未来的coworker所以交流的融洽是
很重要的。
coding不过硬会导致必然的失败。我之前就是觉得自己算法底子不错忽视了
coding,其实本末倒置。工作中coding才是最重要的,而且看了很多牛人的coding之后
才发现这个事情真的不是搬砖那么简单,同一个内容的程序coding好不好能差很多(再
加上clear和readability的考虑)。顶尖it公司要的不是average coder而是top coder
,所以以前仗着算法不错就满足于average的coding水品实在是很幼稚,以后一定会在
这方面加强锻炼。

个人还有些算法和advanced data structure的重点觉得没有在leetcode里面很好体现
的,总结如下:

1. 很多recursive容易的算法也要考虑iterative方法。因为掌握iterative代表你对问
题结构理解上升了一个高度。e.g. reverse linked list, tree traversal

2. i) top k (kth) elements: heap O(n+klogn), quickselect O(n) average O(n^2)
worst, median of medians O(n) worst. cons and pros.
Extension: what if all data can not fit into memory. heap size of k O(nlogk)
for single machine, many machines see 3.
ii) get median in data stream: max heap + min heap

3. kth element in many m machines: binary search, pick a pivot and see how 
many less and larger among all machines, then discard halves accordingly (
distributed quickselect)

if sorted in single machine: find smallest (k/m)th element among all 
machines and discard the less partition.

4. stack support O(1) getMin
   queue support O(1) getMin
e.g. k sliding window, most frequently clicked url in past 12 months.

5. reservoir sampling for infinite stream, generate random(1-7) with random(
1-5), card shuffle, string permute in place

6. data structure with O(1) insert, delete, getRandom, get: hashmap + array

LRU data structure: hashmap + doublelikedlist.

binary search tree with rank() (position of inserted or queried data)
(add treesize attribute for each node)

7. bit operation and bitset.
e.g. find missing number in large data, reverse binary number, 

8. java multi-threading, blocking queue, nonblocking queue, H20, philosophy 
dining, deadlock checking. 现在是个公司都问concurrency,一定要好好准备。

9. OOP: elevator design, parking lot design
distributed: large log file design, social network design, distributed cache
design ....




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