g*******r
发帖数: 44 | 1 google 店面
就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
spanner那篇论文.
twitter 店面
第一轮.
1.如何判断一棵树是BST.
2.用2个栈实现队列。
第二轮
1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
2. 关于图的简单BFS的一道题。
然后就是onsite了，这个我真的是是准备有问题，第一天面的google, 第二天面
twitter, 去google面试第一天坐了8个小时飞机，到了都晚上8点了，搞得第二天不在
状态了。
google onsite
第一轮，一个front end的人就问了一道题，写个程序，接收客户端的请求，如何保证
每秒钟只发送10个请求给服务器。这题他的意思我现在都不明白，他的意思是用平均速
度，看当前请求的时间和上个请求的时间相差多少，如果大于0.1秒就转发，否则就丢
弃。我觉得有问题啊，然后就郁闷了
。。
第二轮，一个印度哥们问如何用mutex和condition variable实现读写锁。这个好久没
碰了，答得也不好。
... 阅读全帖 |
|
d**e
发帖数: 6098 | 2 ☆─────────────────────────────────────☆
HorseKing (二逼青年思路广) 于 (Mon Apr 23 21:49:20 2012, 美东) 提到:
我感觉版上有无数学院派的，说白了就是整天盯着算法看的，背题目的。
版上还有几个牛人显然是实用派的，也就是已经在IT领域内工作并有小成/大成的
俺也算是个实用派，每次看到版上发的那些算法题俺就特惭愧，因为完全不懂哇。。。
我既没找过什么KTH，也没用过NLOG，但这似乎并不能阻碍我成为框架师。所以我也不
懂了，一方面吧，我觉得懂算法的都很牛，另一方面有觉得搞算法的似乎理论性都太强
了点。
我很困惑为什么版上就没几个愿意进入我们应用领域的呢？俺承认，这个帖子灰常的无
厘头。
☆─────────────────────────────────────☆
StevenLow (CrossLayer) 于 (Mon Apr 23 21:49:55 2012, 美东) 提到:
马哥牛逼。
☆─────────────────────────────────────☆
yangc... 阅读全帖 |
|
s********l
发帖数: 998 | 3 不是找最大的kth吗？
你怎么先跑到左边去了呢？
inorder traversal 反过来就可以了把~ |
|
b*****n
发帖数: 482 | 4 我其实最近才开始做leetcode，一周时间，到现在刚好50题。我先来抛块砖吧，讲讲自
己的体会：
1. 先看思路领会透不透。譬如说peranthese matching, largest rectangle, maximum
rectangle 这些题。还有kth largest, median of two sorted arrays。特别是
median of two sorted arrays，思路和细节吃透了， 再要写一遍的话，bug free并不
算特别难。当然我是指“再写一遍”。我知道peking2的目标可能是没见过面的5分题一
次写对:)，那可真得下功夫。
2. 再看固定模式熟不熟。tree的recursive，string matching的dp，math里用的移位
和二分法，数组的左右指针，单链表的双指针traverse/delete。这些基本的东西要有
敏感度。
3. corner case要cover够。空指针，0长度，integer记住有负数，unsigned包括0，
duplicate怎么处理，会不会overflow，out of range，loop能不能... 阅读全帖 |
|
b*****n
发帖数: 482 | 5 我其实最近才开始做leetcode，一周时间，到现在刚好50题。我先来抛块砖吧，讲讲自
己的体会：
1. 先看思路领会透不透。譬如说peranthese matching, largest rectangle, maximum
rectangle 这些题。还有kth largest, median of two sorted arrays。特别是
median of two sorted arrays，思路和细节吃透了， 再要写一遍的话，bug free并不
算特别难。当然我是指“再写一遍”。我知道peking2的目标可能是没见过面的5分题一
次写对:)，那可真得下功夫。
2. 再看固定模式熟不熟。tree的recursive，string matching的dp，math里用的移位
和二分法，数组的左右指针，单链表的双指针traverse/delete。这些基本的东西要有
敏感度。
3. corner case要cover够。空指针，0长度，integer记住有负数，unsigned包括0，
duplicate怎么处理，会不会overflow，out of range，loop能不能... 阅读全帖 |
|
h*********o
发帖数: 230 | 6 看了好久没明白问题，为啥C++可以呢
public static void findKthNode(TreeNode root, int k){
if (root == null)
return ;
findKthNode(root.left, k);
k--;
System.out.println(k);
if (k == 0)
System.out.println(root.val);
findKthNode(root.right, k);
} |
|
|
c*****a
发帖数: 808 | 8 make k static, or global scope to the function |
|
c*****a
发帖数: 808 | 9 or
i think this will work
public static void findKthNode(TreeNode root, int k){
if (root == null)
return ;
findKthNode(root.left, k-1);
System.out.println(k);
if (k == 0)
System.out.println(root.val);
findKthNode(root.right, k-1);
} |
|
|
|
h*********o
发帖数: 230 | 12 嗯， 应该是的， 那在java中这个参数应该怎么传？ |
|
|
h*********o
发帖数: 230 | 14 这么麻烦啊.....
那类似鱼这种方法中的参数，都需要重新定义class啊。。 |
|
|
d*********g
发帖数: 154 | 16 要传递引用的话貌似可以用int[] k = new int[1]：
public void findKthNode(TreeNode root, int[] k){
if (root == null) return ;
findKthNode(root.left, k);
k[0]--;
if (k[0] == 0)
System.out.println(root.val);
findKthNode(root.right, k);
}
或者可以加一个返回值（现写的，没测过，大家看看对不对）：
public int findKthNode(TreeNode root, int k)
{
if(root == null) return k;
int leftK = findKthNode(root.left, k);
--leftK;
if(leftK == 0)
System.out.println(root.val);
int rightK = findKthNo... 阅读全帖 |
|
|
c*******i
发帖数: 30 | 18 c++可以， 应该是用了reference吧~
java里可以写个wrapper class， 包上一个int 变量~~ |
|
b****g
发帖数: 192 | 19 很多树里面遍历、查找、比较的题都能用这个思路
大意就是递归里面传引用
至于具体传的参数，可是是本题一样的一个用于计数的int，也可以是一个指向tree/
node的指针（例如在binary tree里找最大BST）
总之要传引用才行
如果传的是int，那一定要有该参数的数值的改变操作：
可以在函数里加一句i++之类的
也可以在函数递归调用时把i++当做参数传进去 |
|
a**********e
发帖数: 157 | 20 就是说不断有新数据输入，而且数据量很大，分布在多个机器上，（新的data push到
哪个机器上是随机的)。
怎样做效率比较高？谢谢。 |
|
c********t
发帖数: 5706 | 21 maintain a k size min-heap on each machine. Then merge-sort them to a master
machine. |
|
j*****y
发帖数: 1071 | 22 每台机器用一个 max queue of size k 保留 k个最小的数
然后再 merge 这些不同机器上的 queque |
|
P******r
发帖数: 842 | 23 max heap of the smallest k numbers？如果有个新数，小于max, delete max,
heapify。
master |
|
|
e***s
发帖数: 799 | 25 delete max 应该是 replace max with new value吧？ |
|
a**********e
发帖数: 157 | 26 谢谢。
既然涉及master machine，可不可以每次有data进来，（在store在各个机器上的同时
），直接
把data也push一份到master machine上，这样只要在master machine上维持max heap就
可以了。
这样有什么问题呢？
master |
|
c********t
发帖数: 5706 | 27 我觉得，选择push还是poll要看requirement，如果这k个数据很常用，时时刻刻都会被
调用，那就push吧，如果只是偶尔查，那就要用的时候再从各个机器上poll.无论哪种
，都要在每台机器上存这个heap,否则传输出什么问题怎么办？ |
|
d**********x
发帖数: 4083 | 28 median of medians并不实用，常数过大无比缓慢，只是作为一种理论上的kth element
可被worst-case O(n)找到的实例。
quick selection的worst case是O(n^2)，但是ramdomized之后效果很好，唯一问题是
它不是online算法，而且还要改原数组
所以在特定情形下heap也很好用，如果k相对于n是个很小的数 |
|
M******e
发帖数: 103 | 29 大概一个多月之前面的，期间多次Email问结果及报销的情况，HR均置之不理。这种情
况，知道自己肯定没戏。但不告诉我如何报销，让我非常郁闷。今天终于收到HR的据信
，也就放心了。
他家的面试一点不难，5个人有4个拿着简历问你以前做的项目，一副心不在焉的样子。
这也让我怀疑自己是被拉去做分母了。
一个三哥算是问了几个coding的问题。这位三哥毕业于阿三国烂校，拿了一个UC学校的
master. 在我以前面试遇到的面试官中，有的是看着聪明，交流起来觉得确实聪明；有
的是看着就不聪明，自己却非要装出一种聪明样。这位三哥就是后面这种情况。
整个面试出了三道编程题。对每一道题，要么作出咄咄逼人装，要么作出高深莫测装，
让人很不舒服。
第1道是2维平面有多个点，求出能给最多colinear的点的个数。CC150上有，hash
table解决。
第2道是在一个rotated array中找一个数，easy.
第3道是求kth number. 我说了两种方法， 1）heap O(nlongN) 和2）quick select O
(N)。他说写2）吧。Code很快写完了。他不停地问我time co... 阅读全帖 |
|
p****e
发帖数: 3548 | 30 details of the question? |
|
s*****1
发帖数: 134 | 31 我在想，如果不追求很快的话
这个好像也就是 M个sorted的序列，然后merge一下
和Leetcode 上 Merge k Sorted Lists 是不是差不多？ |
|
w****x
发帖数: 2483 | 32
那个解法最差复杂度还不如全部selection sort |
|
s*****1
发帖数: 134 | 33 复杂度是 K lg(M) 或 K lg(N) 看谁小,为什么比selection sort慢？
大牛请明示~ |
|
w****x
发帖数: 2483 | 34
假如k是M*N,那么merge的复杂度就是M*N*logM
Selection sort是M*N |
|
s*****1
发帖数: 134 | 35 恩，我看懂了，你说的是quick select~
我觉得你说的是有道理的~ |
|
w****x
发帖数: 2483 | 36 做了一个QuadTree
struct PT
{
int x;
int y;
};
struct REC
{
POINT topLft;
POINT bottomRgt;
REC(int a, int b, int c, int d)
{
topLft.x = a;
topLft.y = b;
bottomRgt.x = c;
bottomRgt.y = d;
}
bool inRect(PT pt)
{
return pt.x >= topLft.x && pt.x <= bottomRgt.x
&& pt.y >= topLft.y && pt.y <= bottomRgt.y;
}
bool intersect(REC rect)
{
return min(bottomRgt.x, rect.bottomRgt.x) >= max(topLft.x, rect.
to... 阅读全帖 |
|
c***s
发帖数: 192 | 37 这个就是跟 kth of two sorted array一样的吗？
我刚被面到过，然后我告诉面试官我做过这道题，
他先让我讲了一下思路，然后写了特殊情况就过了。
折半比较就可以了啊。 |
|
d**********x
发帖数: 4083 | 38 那题目貌似就没卡复杂度。。。枉我昨天下班后还捏着鼻子写了个treap。。。结果证
明是输出格式错了，只过了两三个case的可以考虑检查一下输出格式
思路大致就是用order statistics tree。每次查询都是O(logn)。手写最大问题在于没
法定制容器的行为。。。
好吧，然后想了一下，如果用两个heap加一个map的话也是可以的，因为只是查询
median，没有要求随机查询kth元素，所以还是写复杂了
附上代码，treap是个随机平衡树，可以拿去用。
#include
#include
#include
#include
using namespace std;
template
class Treap {
public:
class Node {
public:
Node(const T& value)
: value_(value),
left_(NULL),
right_(NULL),... 阅读全帖 |
|
r**h
发帖数: 1288 | 39 先用partition找到前k大的k个元素，O(n)
再在前k大的里找最大的，O(k) |
|
|
c*****a
发帖数: 808 | 41 quicksort partition 到k时，找左边最大，或者右边最小 |
|
m*****P
发帖数: 1331 | 42 CLRS里面找
大概就是利用quick sort的patition方法
一个是平均o(n)
要做到worst case o(n) 需要找特别的pivot 大概就是median的median
不过要写出来 估计面试不需要吧 |
|
|
y***5
发帖数: 21 | 44 结果：面试7家，5 onsite，3 offer。
面经：
Amazon：2轮电面，5轮onsite。2天后offer，最后decline，非常nice的manager（拿到
A offer时还在面其它公司，比较大度地祝我good luck），拒绝的时候感情上比较难受。
电面1，设计parking lot
2， intersection of sorted int array; design data structure for a phone
contact book
onsite 1: find biggest int in array,
find K biggest int in array(tradeoff between many methods),
implement using heap
2: print modification path from "head" to "tail", given isWord()
api and every time can modify 1 word in the strin... 阅读全帖 |
|
k*****5
发帖数: 25 | 45 思路类似于寻找Kth smallest element in an array, median of X*Y个数也是寻找X*Y
/2th smallest element. 选一个数，把它叫做pivot, 用pivot 来partition 所有机器
上的数，并统计有多少个数小于等于pivot， 根据这个信息缩小查找的范围 (divide
and conquer)。
extra |
|
i******t
发帖数: 22541 | 46 好象是 kth of two sorted arrays
容易些
median of two sorted arrays 剧难 具难。。。。。。。。 |
|
H**M
发帖数: 128 | 47 只碰到了一个见过的题：2D array, 行递增，列递增，找一个数。我没想好是不是应该
告诉他我知道这题，就没说，装装地想了一会，就告诉他答案了。但是他也没让我写
code，然后直接问了下一题：两个sorted arrays, 找kth element, 我上来就说了
merge sort, 但他要更好效率的。 |
|
|
p*****2
发帖数: 21240 | 49 很多人都说把这150题做了一遍或几遍，但是我感觉算法题才是重点，其他的很多题面
试基本碰不上，没看出来有必要全做。这里总结一下自己认为重要的题。
第一章 ：
全部重要 (1.6, 1.7 Leetcode上有）。
1.5 面A碰到 (string compression)
1.7面Z碰到 (set 0)
1.8面Bigfish碰到 (string rotation)
第二章 (2.4, 2.5 Leetcode上有）：
全部重要。
2.2面Bigfish碰到 (find kth)
第三章 ：
感觉就是3.2 (min stack), 3.5 (two stack queue) 重要。两道题面M被问到过。3.6
(sort stack)感觉也有可能被考到。
第四章 （4.1， 4.3， 4.5 Leetcode上有）：
感觉4.2, 4.3, 4.5，4.6， 4.7 重要。4.5 (valid BST)面E，Q碰到过
第五章：5.4 (n & (n-1))
第六章：6.5 (drop egg)
第七章：7.3 (line intersection)，7.6 (line passes m... 阅读全帖 |
|
m**r
发帖数: 574 | 50 G家的：Describe an algorithm to find the largest 1 million numbers in 1
billion numbers. Assume that the computer memory can hold all one billion
numbers.
find the Kth number.
能不能给我讲讲这种题应该怎么写？ |
|
