l****i
发帖数: 230 | 1 这周周二的onsite，一共五轮面试。安排比较混乱，其中一个interviewer，我干等了
半个小时，no show。联系HR，才知道这个interviewer已经休假5个月。所以后来又加
了一个interviewer。
感觉google的面试根本不考虑candidate的背景和经历，只考coding。我有朋友做到了
CS Top-4的正教授，去google面试仍然是一样的流程。这个确实让人非常frustrated。
1. Thesis discussion：老印，data base出身，鸡同鸭讲，面得很费劲，互相感觉都
不是很好。
2. 老中，coding：给一个N个node的BST，给一个Key，返回与key最接近的m个node(m
).
我开始说可以做inorder traverse，用一个priority queue保存跟key最近的m个value
，复杂度O(n)；存在average O(log n)的算法，但不好写。结果还是被要求写O(log n)
的code。
这个算法不是很难(不确定是不是最优)，但是在30分钟写出来确实不容易。
我的基本思路还是用priority queue,现在BST中查找key，返回指向value=key的node(
如果存在)或者应该插入该key的node(key不在BST中)，然后从该node开始向前向后各m
次判断前驱或者后继是不是应该插入priority queue.
主要函数code最后虽然写出来了，不过lookUp、successor和predecessor这三个子函数
没来得及写。
3. 白人。问了一个随机采样方面的问题，比较简单。
3.5 lunch。以前实验室的一个哥们带我lunch然后骑着自行车在g campus逛了一圈
4.0 老中，no show
4.1 老白，讨论了一些research问题。然后最后5分钟的时候考了一个coding：给一个
很大的数组(比如全世界每个人的salary)，找median
5.两个老印(其中一个负责观察):设计一个集合数据结构(set,只存unique的value)要求
能在O(1)时间内insert，delete，random query(比如目前set中有n个元素，给一个介
于1到n的随机数k，可以在O(1)时间内返回第k个value)
总体感觉面得非常不顺。不过自己尽力了，也没什么遗憾。希望对即将去面试的朋友有
所帮助。 |
j********e
发帖数: 1192 | 2 Bless. 比我还惨，我虽然遇到2个迟到20分钟的，不过最终还是都来了。
value
【在 l****i 的大作中提到】
: 这周周二的onsite，一共五轮面试。安排比较混乱，其中一个interviewer，我干等了
: 半个小时，no show。联系HR，才知道这个interviewer已经休假5个月。所以后来又加
: 了一个interviewer。
: 感觉google的面试根本不考虑candidate的背景和经历，只考coding。我有朋友做到了
: CS Top-4的正教授，去google面试仍然是一样的流程。这个确实让人非常frustrated。
: 1. Thesis discussion：老印，data base出身，鸡同鸭讲，面得很费劲，互相感觉都
: 不是很好。
: 2. 老中，coding：给一个N个node的BST，给一个Key，返回与key最接近的m个node(m: ).
: 我开始说可以做inorder traverse，用一个priority queue保存跟key最近的m个value
|
K*****u
发帖数: 241 | |
p*****2
发帖数: 21240 | 4 然后从该node开始向前向后各m
次判断前驱或者后继是不是应该插入priority queue.
这个复杂度是多少？ |
a***o
发帖数: 1182 | 5 最后一题怎么弄？
value
【在 l****i 的大作中提到】
: 这周周二的onsite，一共五轮面试。安排比较混乱，其中一个interviewer，我干等了
: 半个小时，no show。联系HR，才知道这个interviewer已经休假5个月。所以后来又加
: 了一个interviewer。
: 感觉google的面试根本不考虑candidate的背景和经历，只考coding。我有朋友做到了
: CS Top-4的正教授，去google面试仍然是一样的流程。这个确实让人非常frustrated。
: 1. Thesis discussion：老印，data base出身，鸡同鸭讲，面得很费劲，互相感觉都
: 不是很好。
: 2. 老中，coding：给一个N个node的BST，给一个Key，返回与key最接近的m个node(m: ).
: 我开始说可以做inorder traverse，用一个priority queue保存跟key最近的m个value
|
p*****2
发帖数: 21240 | 6 可以在O(1)时间内返回第k个value
第k个value是指按插入的顺序a吗？ |
w****m
发帖数: 235 | 7 Thesis discussion
这是针对phd的吧？
看到lz的题目，都不敢去面了，
怎么都考些那么复杂的数据结构啊 |
l****i
发帖数: 230 | 8 不是大牛，还没决定去哪里呢
【在 K*****u 的大作中提到】
: 大牛不是已经去A家了么？
|
a***o
发帖数: 1182 | 9 是不是现在面试有点晚了？好像g家招人变政策了，和1-2月份比起来？
【在 l****i 的大作中提到】
: 不是大牛，还没决定去哪里呢
|
t*********7
发帖数: 255 | |
|
|
j*****o
发帖数: 394 | 11 这个题有朋友面过
K差不多算是第K次插入的数吧
class mystruct
{
public:
int a[100];
int b[100]; //numbers should be in [0, 99]
int count; //count of valid numbers in a[]
mystruct()
{
count=0;
for (int i=0; i<100; i++) { a[i]=0; b[i]=-1;}
}
void insert(int x) { a[count]=x; b[x]=count; count++;}
void remove(int x) { int tmp=b[x]; b[x]=-1; a[tmp]=a[count-1]; b[a[tmp]]
=tmp; count--;}
int getrandom() { srand(time(0)); return a[rand()%count];}
};
【在 a***o 的大作中提到】
: 最后一题怎么弄？
:
: : value
|
e****e
发帖数: 418 | 12 hashtable
【在 a***o 的大作中提到】
: 最后一题怎么弄？
:
: : value
|
l****i
发帖数: 230 | 13 不是，不能返回已经删除的元素
比如：+表示插入，-表示删除
+1+1+3+3+5-3-1+8+1+4
最后的set是{5814}
k=2，返回8
【在 j*****o 的大作中提到】
: 这个题有朋友面过
: K差不多算是第K次插入的数吧
: class mystruct
: {
: public:
: int a[100];
: int b[100]; //numbers should be in [0, 99]
: int count; //count of valid numbers in a[]
: mystruct()
: {
|
e****e
发帖数: 418 | 14 For Q2, implement 2 methods, goToNextNode(Node node), goToPrevNode(Node node
). Mehtod goToNextNode(Node curNode) returns the node on the right subTree
of curNode and this node has the closest key to the curKey among the subTree
. It's like the next node in inorder traversal.
Then go to the node containing the input key, from there, call goToNextNode(
)/goToPrevNode recursively and compare its key the input key. You can think
of those two methods as two pointers in between which input key node.
Whenever you find the key qualifying the 'm个node, then move to the next
node. In the right subtree, always use goToNextNode(). 复杂度 is O(m). |
w****x
发帖数: 2483 | |
w****x
发帖数: 2483 | 16 N个node的search tree, 想不出来时什么样子啊， 那你说父节点到底比这n个子节点的
哪个大， 比哪个小？？（BST是比左节点大，右节点小） |
t***t
发帖数: 6066 | 17 说我的解法，看如何。
1. 找到pivot点。pivot点就是最接近key的node.
2. 保持俩指针，一个从pivot往前走一个往后走。
3. 每次每个指针看下一步，哪个abs(node.data-Key)小，那个指针前进一步。
4. 记住总步数，到了m步就停。
总时间复杂度log(n)+m
|
S*******w
发帖数: 24236 | 18 cs top4的正教授还去Google面试。。
value
【在 l****i 的大作中提到】
: 这周周二的onsite，一共五轮面试。安排比较混乱，其中一个interviewer，我干等了
: 半个小时，no show。联系HR，才知道这个interviewer已经休假5个月。所以后来又加
: 了一个interviewer。
: 感觉google的面试根本不考虑candidate的背景和经历，只考coding。我有朋友做到了
: CS Top-4的正教授，去google面试仍然是一样的流程。这个确实让人非常frustrated。
: 1. Thesis discussion：老印，data base出身，鸡同鸭讲，面得很费劲，互相感觉都
: 不是很好。
: 2. 老中，coding：给一个N个node的BST，给一个Key，返回与key最接近的m个node(m: ).
: 我开始说可以做inorder traverse，用一个priority queue保存跟key最近的m个value
|
w****x
发帖数: 2483 | 19
N个节点的search tree到底是什么玩意啊，是B+吗？
还有找Median那题也不好做啊，谁那题给个解法
【在 t***t 的大作中提到】
: 说我的解法，看如何。
: 1. 找到pivot点。pivot点就是最接近key的node.
: 2. 保持俩指针，一个从pivot往前走一个往后走。
: 3. 每次每个指针看下一步，哪个abs(node.data-Key)小，那个指针前进一步。
: 4. 记住总步数，到了m步就停。
: 总时间复杂度log(n)+m
:
|
t***t
发帖数: 6066 | 20 就是二叉search tree. n是总节点数吧。
【在 w****x 的大作中提到】
:
: N个节点的search tree到底是什么玩意啊，是B+吗？
: 还有找Median那题也不好做啊，谁那题给个解法
|
|
|
t***t
发帖数: 6066 | 21 两个堆，一个min-heap一个max-heap。keep a count for each heap.
每读进一个数，哪个heap count少插到哪个heap。如果count等，median是俩heap根平
均。count不等，多的那个heap根是median.
【在 w****x 的大作中提到】
:
: N个节点的search tree到底是什么玩意啊，是B+吗？
: 还有找Median那题也不好做啊，谁那题给个解法
|
l****i
发帖数: 230 | 22 就是BST，总结点数已知为N
【在 w****x 的大作中提到】
: N个node的search tree, 想不出来时什么样子啊， 那你说父节点到底比这n个子节点的
: 哪个大， 比哪个小？？（BST是比左节点大，右节点小）
|
t***t
发帖数: 6066 | 23 有点错。要保持min-heap根比max-heap根大。新的数先看进哪个heap，再看count，把
一个堆中多出的删掉放到另一个堆你里。
【在 t***t 的大作中提到】
: 两个堆，一个min-heap一个max-heap。keep a count for each heap.
: 每读进一个数，哪个heap count少插到哪个heap。如果count等，median是俩heap根平
: 均。count不等，多的那个heap根是median.
|
w****x
发帖数: 2483 | 24
不是，这题的考点是内存放不下
【在 t***t 的大作中提到】
: 有点错。要保持min-heap根比max-heap根大。新的数先看进哪个heap，再看count，把
: 一个堆中多出的删掉放到另一个堆你里。
|
t***t
发帖数: 6066 | 25 不需要放下。只要放下俩堆，保持计数就行。比如，一个堆放最大100个数，另一个放
最小的100个。
【在 w****x 的大作中提到】
:
: 不是，这题的考点是内存放不下
|
w****x
发帖数: 2483 | 26
不对吧。。。。
【在 t***t 的大作中提到】
: 不需要放下。只要放下俩堆，保持计数就行。比如，一个堆放最大100个数，另一个放
: 最小的100个。
|
t***t
发帖数: 6066 | 27 好像我想复杂了。不需要堆。
只需要俩数和俩count。
【在 w****x 的大作中提到】
:
: 不对吧。。。。
|
w****x
发帖数: 2483 | 28
不对不对
【在 t***t 的大作中提到】
: 好像我想复杂了。不需要堆。
: 只需要俩数和俩count。
|
t***t
发帖数: 6066 | 29 对，我想法不对。
那只好排序了。外排序。有好办法么？
【在 w****x 的大作中提到】
:
: 不对不对
|
l****i
发帖数: 230 | 30 我就是这么做的
但是worst complexity不可能是O(log n +m)，因为找前驱和后继不可能在O(1)时间内
完成
【在 t***t 的大作中提到】
: 说我的解法，看如何。
: 1. 找到pivot点。pivot点就是最接近key的node.
: 2. 保持俩指针，一个从pivot往前走一个往后走。
: 3. 每次每个指针看下一步，哪个abs(node.data-Key)小，那个指针前进一步。
: 4. 记住总步数，到了m步就停。
: 总时间复杂度log(n)+m
:
|
|
|
l****i
发帖数: 230 | 31 第一题不是找median
【在 t***t 的大作中提到】
: 两个堆，一个min-heap一个max-heap。keep a count for each heap.
: 每读进一个数，哪个heap count少插到哪个heap。如果count等，median是俩heap根平
: 均。count不等，多的那个heap根是median.
|
l****i
发帖数: 230 | 32 这个题其实可以做得很简单，因为不需要找到精确的median。
一种简单的做法就是把income range分成M个bin，统计histogram
然后scan一遍，既可以找到approximate median，精度是 range/M,假设range是0到
100000，4G内存，精度可以做到0.0001.
【在 t***t 的大作中提到】
: 不需要放下。只要放下俩堆，保持计数就行。比如，一个堆放最大100个数，另一个放
: 最小的100个。
|
c****m
发帖数: 11 | 33 re，感觉给任意一个节点找前驱和后继都是lgN的操作啊，感觉应该lgN * m的复杂度
【在 l****i 的大作中提到】
: 我就是这么做的
: 但是worst complexity不可能是O(log n +m)，因为找前驱和后继不可能在O(1)时间内
: 完成
|
q****x
发帖数: 7404 | 34 我有朋友做到了CS Top-4的正教授，去google面试仍然是一样的流程。
我不信。谁？
value
【在 l****i 的大作中提到】
: 这周周二的onsite，一共五轮面试。安排比较混乱，其中一个interviewer，我干等了
: 半个小时，no show。联系HR，才知道这个interviewer已经休假5个月。所以后来又加
: 了一个interviewer。
: 感觉google的面试根本不考虑candidate的背景和经历，只考coding。我有朋友做到了
: CS Top-4的正教授，去google面试仍然是一样的流程。这个确实让人非常frustrated。
: 1. Thesis discussion：老印，data base出身，鸡同鸭讲，面得很费劲，互相感觉都
: 不是很好。
: 2. 老中，coding：给一个N个node的BST，给一个Key，返回与key最接近的m个node(m: ).
: 我开始说可以做inorder traverse，用一个priority queue保存跟key最近的m个value
|
y*******g
发帖数: 6599 | 35 强烈表示不信
cs top4 正教授总共才几个？
value
【在 l****i 的大作中提到】
: 这周周二的onsite，一共五轮面试。安排比较混乱，其中一个interviewer，我干等了
: 半个小时，no show。联系HR，才知道这个interviewer已经休假5个月。所以后来又加
: 了一个interviewer。
: 感觉google的面试根本不考虑candidate的背景和经历，只考coding。我有朋友做到了
: CS Top-4的正教授，去google面试仍然是一样的流程。这个确实让人非常frustrated。
: 1. Thesis discussion：老印，data base出身，鸡同鸭讲，面得很费劲，互相感觉都
: 不是很好。
: 2. 老中，coding：给一个N个node的BST，给一个Key，返回与key最接近的m个node(m: ).
: 我开始说可以做inorder traverse，用一个priority queue保存跟key最近的m个value
|
S*****B
发帖数: 404 | 36 CMU MIT之类的教授都是个google一起开实验室的
哪有去面试考算法的
【在 y*******g 的大作中提到】
: 强烈表示不信
: cs top4 正教授总共才几个？
:
: : value
|
l****i
发帖数: 230 | 37 是真事，刚刚发生的。不过为了不暴露隐私，还是不便透露名字
【在 y*******g 的大作中提到】
: 强烈表示不信
: cs top4 正教授总共才几个？
:
: : value
|
w**z
发帖数: 8232 | 38 过了吗?
【在 l****i 的大作中提到】
: 是真事，刚刚发生的。不过为了不暴露隐私，还是不便透露名字
|
l****i
发帖数: 230 | 39 过了。不过，一般对这些非常senior的，coding的bar要低很多，但是面试中还是要问。
据说当年另外一个CMU的正教授去面试一个director，被问coding，直接扔笔愤愤地摔
门而出
【在 w**z 的大作中提到】
: 过了吗?
|
v****c
发帖数: 29 | 40 这个就是O(log n + m)，虽然worst case每一步都是log n
但是你算算看amortized cost，多出来的那部分被log n absorb掉了
【在 l****i 的大作中提到】
: 我就是这么做的
: 但是worst complexity不可能是O(log n +m)，因为找前驱和后继不可能在O(1)时间内
: 完成
|
|
|
l****p
发帖数: 397 | 41 确实想不出比mlg(N)更快的算法。这题要在30分钟内做完确实很难，我看了楼主的思路
后还用了近50分钟才写完的……
顺便贴上我的实现(Ruby)：
def nearest_nodes root, m, key
node = find_insert root, key
prev = node.prev_node
nex = node.next_node
results = []
m.times do
nearest = nil
if prev and nex
if m-prev.value
nearest = prev
prev = prev.next_node
else
nearest = nex
nex = nex.next_node
end
elsif prev
nearest = prev
prev = prev.prev_node
elsif nex
nearest = nex
nex = nex.next_node
else
break
end
end
results
end
class BSTNode
attr_accessor :left
attr_accessor :right
attr_accessor :parent
attr_accessor :value
def initialize value
@value = value
end
def prev_node
prev = nil
if @left
prev = @left
prev = prev.right while prev.right
elsif @parent and self == @parent.right
prev = @parent
end
prev
end
def next_node
nex = nil
if @right
nex = @right
nex = nex.right while nex.right
elsif @parent and self == @parent.left
nex = @parent
end
nex
end
end
def find_insert root, value
if root.value > value
if root.left
return find_insert root.left, value
else
node = BSTNode.new value
root.left = node
node.parent = root
return node
end
elsif root.value < value
if root.right
return find_insert root.right, value
else
node = BSTNode.new value
root.right = node
node.parent = root
return node
end
else
return root
end
end
【在 c****m 的大作中提到】
: re，感觉给任意一个节点找前驱和后继都是lgN的操作啊，感觉应该lgN * m的复杂度
|
S*******e
发帖数: 379 | 42 这题这么做的确巧妙.不过数组b和value space一样大,很有局限性.
而且没法保持插入的顺序.有其他解法吗?
【在 j*****o 的大作中提到】
: 这个题有朋友面过
: K差不多算是第K次插入的数吧
: class mystruct
: {
: public:
: int a[100];
: int b[100]; //numbers should be in [0, 99]
: int count; //count of valid numbers in a[]
: mystruct()
: {
|
f*****i
发帖数: 835 | 43 To find median, can we use those two step?
1. Partition to two equal sized part, this should be o(n).
2. Find min or max, this is o(n). |
t********3
发帖数: 567 | 44 我也想说，是去面scientist职位的话还可以理解。但是scientist职位不会这么要求
coding的吧
【在 S*******w 的大作中提到】
: cs top4的正教授还去Google面试。。
:
: : value
|
s*********e
发帖数: 197 | 45 感觉如果只有BST这个条件的话，很难有好于O(n)的算法。
【在 t********3 的大作中提到】
: 我也想说，是去面scientist职位的话还可以理解。但是scientist职位不会这么要求
: coding的吧
|
j********2
发帖数: 82 | 46 how to divide the buckets? Say, 1G integers of all 1s, and 1k memory?
Also, what is 精度 here?
【在 l****i 的大作中提到】
: 这个题其实可以做得很简单，因为不需要找到精确的median。
: 一种简单的做法就是把income range分成M个bin，统计histogram
: 然后scan一遍，既可以找到approximate median，精度是 range/M,假设range是0到
: 100000，4G内存，精度可以做到0.0001.
|
i*******e
发帖数: 240 | |
b*******y
发帖数: 2048 | |
j********x
发帖数: 2330 | 49 其实director要求会点coding不过分
但是面试的时候还要求去写就过分了，这种级别大概聊一聊感觉就行了
问。
【在 l****i 的大作中提到】
: 过了。不过，一般对这些非常senior的，coding的bar要低很多，但是面试中还是要问。
: 据说当年另外一个CMU的正教授去面试一个director，被问coding，直接扔笔愤愤地摔
: 门而出
|
r*****e
发帖数: 264 | 50 第5题是否可以用bit array
insertion, deletion, membership明显是O(1)
再给一个operator [], O(1)返回kth value |
|
|
r*****e
发帖数: 264 | 51 hashtable不行吧
【在 e****e 的大作中提到】
: hashtable
|
s***u
发帖数: 101 | 52 如果像 面试官 说的 里面的数据都是人的薪水的话， 可以按照薪水做bucket sort 一
百万以上的 可以放在一组 这样 entry 不会超过100万 精度为一块钱
【在 r*****e 的大作中提到】
: hashtable不行吧
|
T*U
发帖数: 22634 | 53 当个vp？
【在 S*******w 的大作中提到】
: cs top4的正教授还去Google面试。。
:
: : value
|
e***s
发帖数: 799 | 54 不懂，bit array 里的值不是true 和 false 吗？
【在 r*****e 的大作中提到】
: 第5题是否可以用bit array
: insertion, deletion, membership明显是O(1)
: 再给一个operator [], O(1)返回kth value
|
h******0
发帖数: 427 | |
l****c
发帖数: 782 | 56 我只能想到这种方法。。。。
我想问下，可不可以在node的struct里面set一个parent指针啊，不然找前一个数，和
后一个数有点麻烦啊。。。。。
【在 t***t 的大作中提到】
: 说我的解法，看如何。
: 1. 找到pivot点。pivot点就是最接近key的node.
: 2. 保持俩指针，一个从pivot往前走一个往后走。
: 3. 每次每个指针看下一步，哪个abs(node.data-Key)小，那个指针前进一步。
: 4. 记住总步数，到了m步就停。
: 总时间复杂度log(n)+m
:
|
