Google Zenefits Nvidia

[align="left"]Google [/align][align="left"]一面：Longest Consecutive Path in a Tree[/align][align="left"]二面：有一大坨candidate，每个人有一个ID integer，从中随机选择500个人参加Google的party，保证公平[/align]
[align="left"]Nvidia[/align][align="left"]一面：Search in rotated array，问了data mining的两个水问题，问了overfitting是什么，用线性的cost函数和quadratic的cost函数有什么trade off，一个收敛快，但容易有overfitting[/align][align="left"]二面：Seralize and Deseralize Binary Tree，问了奇葩的安卓问题，有一个安卓平板，你一直在往上面烧一个程序，这个程序让这个平板reboot，烧了一夜，第二天早上起来黑屏了，你怎么debug，除了看log你还怎么debug[/align][align="left"]三面：thread和process区别，不保护线程的后果是啥（deadlock），如何预防deadlock，java的多线程有哪些方式，写一个code把string abc变成abbccc，给了两段C代码改错，分别是防止buffer溢出和数组溢出[/align]
[align="left"]Zenefits[/align][align="left"]一面：有个vector，里面装了m个iterator，每个iterator是一个vector的iterator，假设有next和hasNext接口，让你实现一个Zigzag traversal iterator[/align][align="left"][ [/align][align="left"] [1,2,3][/align][align="left"] [5,4][/align][align="left"] [6,7,8,9][/align][align="left"]一直调用next会返回1,5,6,2,4,7,3,8,9，先用了O(mn)的方法，m是最长的iterator的数组的长度，又改成queue或者cycle linkedlist，复杂度是O(k), k是总元素个数[/align][align="left"]Follow Up是，如果iterator有prev和hasPrev接口，实现Zigzag iterator的prev和hasPrev，用C++的deque和stack[/align][align="left"]二面：打印公司manager结构，要indent，follow up按字母序排序，聊了data mining project[/align]