由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 赞人品,发个L的onsite面经
相关主题
amazon 1st phone interview问一道LinkedIn的设计题
Qualcomm On-site 归发些面经,求blessSQL 面试问题
rejected by facebook after 2nd phone interview有没有人发现pinterest有个bug啊
G家悲剧,发面经即将入职亚麻的小硕求教一下今后发展方向
DP interview questionEmbedded SW Engineer!
FB电面的标准就那么高?大家来讨论一下c++吧
问道题请教HTTP怎么复习
[Job Opening] 3D Engine Developer - Physics and Low Level OptimizationL家onsite悲剧 贡献个面经吧
相关话题的讨论汇总
话题: push话题: design话题: numofbytes话题: sequencno
进入JobHunting版参与讨论
1 (共1页)
d*******r
发帖数: 208
1
名单上列了11个人。见了10个,跟名单上有临时改动,有一个的shadow没来。
1. given such a structure,
id -- list of friend ids (sorted), similar to bi-directional or
undirected graph eg.
1 -- 3 5 6
2 -- 5 8
3 -- 1 8
5 -- 1 2
6 -- 1
8 -- 2 3 9
9 -- 8
find an efficient way to decide if two ids are connected by 1 hop or 2
hop. for instance.
one hop: 1 -> 3 -> 8
two hop: 1 -> 3 -> 8 -> 9
2. design a hashtable, get, put, etc. consider thread-safety and hash
capacity resizing.
3. some introduction of the team. no question since it is short lunch.
4. pair: design question. one key/value store, keys can all be loaded into
memory, while value can't since they are very big. When write values to disk
, we can only apppend, no random seek write is allowed, reading values from
disk can alow random seek. How to design a way to efficiently store and
retrieve the values. Follow up on thread-safety and how to clean-up stale
entries in the file.
5. pair: maximum subsequence. min span window (最短摘要).
6. pair: given a stream of unique key-value pairs. given a window size.
write method to getKey, putKey and getAverage. consider thread-safety and
efficiency. optimize getKey and getAverage, which returns the avearge of the
values within the window size.
7. given a push and pull api call, design the protocal on the wire. also
design the memory management unit to reduce memory allocation and
deallocation.
(After a long day, kind of exhausted, i am having trouble understanding the
intention of his questions. 交流出现严重问题).
when he came in, without self-introduction, draw a figure on the board. say.
two sides: one side push the other side pull
push?sequenceNo=xxx&numOfBytes=yyy pullBatch?sinceSequence=xxx&
numOfBytes=yyy
the side that does the push each time only push one sequence of payload with
different sizes.
say 4 pushes like this.
1. push?sequencNo=1&numberOfBytes=50
2. push?sequencNo=4&numberOfBytes=70
3. push?sequencNo=6&numberOfBytes=100
4. push?sequencNo=7&numberOfBytes=80
sequnenceNos doesn't have to be contiguous.
the pull side is a batch operation. it only pull the payload up to
numOfBytes without cutting the sequence. For instance.
pullBatch?sinceSequence=1&numOfBytes=200. will pull sequneceNo 4 and 6 with
the actual size=70+100=170.
Then he asked me to design the underline layer that supports the specified
pullBatch operation. Can either in application layer (Http) or even in
tranport layer (tcp) if I want to.
I got caught.
Then later, he asks how to design the structure of the central unit, I said
use a queue or boundedqueue. he said the problem is queue will always
allocate and deallocate memories. How to optimize. I start to talk about
maintain your own free memory pool. While I was trying to explain my
thoughts, he start to check his iphone. Seems not what he expected. Then he
say this is a short session. walked me out.
some other thoughts on the interview schedule:
cheap: 租车没保险。野外旅馆不带管饭的
hope this could help you.
B*******1
发帖数: 2454
2
zan
s******n
发帖数: 3946
3
最后一个,用deque?
m**q
发帖数: 189
4
==> 谢谢分享

名单上列了11个人。见了10个,跟名单上有临时改动,有一个的shadow没来。
1. given such a structure,
id -- list of friend ids (sorted), similar to bi-directional or
undirected graph eg.
1 -- 3 5 6
2 -- 5 8
3 -- 1 8
5 -- 1 2
6 -- 1
8 -- 2 3 9
9 -- 8
find an efficient way to decide if two ids are connected by 1 hop or 2
hop. for instance.
one hop: 1 -> 3 -> 8
two hop: 1 -> 3 -> 8 -> 9
==> BFS
2. design a hashtable, get, put, etc. consider thread-safety and hash
capacity resizing.
==> hashtable的每个entry用一个lock保护引出的link list,或者用
lock free algorithm
3. some introduction of the team. no question since it is short lunch.
4. pair: design question. one key/value store, keys can all be loaded into
memory, while value can't since they are very big. When write values to disk
, we can only apppend, no random seek write is allowed, reading values from
disk can alow random seek. How to design a way to efficiently store and
retrieve the values. Follow up on thread-safety and how to clean-up stale
entries in the file.
==> 类似于hash table,key就是题目中的key,value是真正的value在磁盘
上的位置。read就直接从hash table中查找磁盘位置再从对应的位置读取。
write把数据append到磁盘,然后用新的位置overwrite hash table中
对应entry
5. pair: maximum subsequence. min span window (最短摘要).
==> 经典题了
6. pair: given a stream of unique key-value pairs. given a window size.
write method to getKey, putKey and getAverage. consider thread-safety and
efficiency. optimize getKey and getAverage, which returns the avearge of the
values within the window size.
==> 没看懂window的意思...
7. given a push and pull api call, design the protocal on the wire. also
design the memory management unit to reduce memory allocation and
deallocation.
(After a long day, kind of exhausted, i am having trouble understanding the
intention of his questions. 交流出现严重问题).
when he came in, without self-introduction, draw a figure on the board. say.
two sides: one side push the other side pull
push?sequenceNo=xxx&numOfBytes=yyy pullBatch?sinceSequence=xxx&
numOfBytes=yyy
the side that does the push each time only push one sequence of payload with
different sizes.
say 4 pushes like this.
1. push?sequencNo=1&numberOfBytes=50
2. push?sequencNo=4&numberOfBytes=70
3. push?sequencNo=6&numberOfBytes=100
4. push?sequencNo=7&numberOfBytes=80
sequnenceNos doesn't have to be contiguous.
the pull side is a batch operation. it only pull the payload up to
numOfBytes without cutting the sequence. For instance.
pullBatch?sinceSequence=1&numOfBytes=200. will pull sequneceNo 4 and 6 with
the actual size=70+100=170.
==> 如果pull可以从中间取走payload的话,那就需要一个数据结构能动态
维护每个元素的index,能想到的是顺序统计树,每次push O(logn),
pull O(klogn),k是pull的元素个数
Then he asked me to design the underline layer that supports the specified
pullBatch operation. Can either in application layer (Http) or even in
tranport layer (tcp) if I want to.
I got caught.
Then later, he asks how to design the structure of the central unit, I said
use a queue or boundedqueue. he said the problem is queue will always
allocate and deallocate memories. How to optimize. I start to talk about
maintain your own free memory pool. While I was trying to explain my
thoughts, he start to check his iphone. Seems not what he expected. Then he
say this is a short session. walked me out.
some other thoughts on the interview schedule:
cheap: 租车没保险。野外旅馆不带管饭的
hope this could help you.

【在 d*******r 的大作中提到】
: 名单上列了11个人。见了10个,跟名单上有临时改动,有一个的shadow没来。
: 1. given such a structure,
: id -- list of friend ids (sorted), similar to bi-directional or
: undirected graph eg.
: 1 -- 3 5 6
: 2 -- 5 8
: 3 -- 1 8
: 5 -- 1 2
: 6 -- 1
: 8 -- 2 3 9

p*****2
发帖数: 21240
5
第5题好像见人讨论过。谁能给把题贴全或者给个link呀?
多谢分享。Good Luck。最后一题我跟你思路差不多。
p*****2
发帖数: 21240
6
==> 类似于hash table,key就是题目中的key,value是真正的value在磁盘
上的位置。read就直接从hash table中查找磁盘位置再从对应的位置读取。
write把数据append到磁盘,然后用新的位置overwrite hash table中
对应entry
how to clean-up stale
entriesn the file.
同意。关于how to cleanup, 我的想法是用两块磁盘,或者两个分区,或者两个文件了
。隔一段时间就把所有的values备份到另一块磁盘,然后转到这个磁盘。这样就可以清
了,两个磁盘轮番换。
p*****2
发帖数: 21240
7
6. pair: given a stream of unique key-value pairs. given a window size.
write method to getKey, putKey and getAverage. consider thread-safety and
efficiency. optimize getKey and getAverage, which returns the avearge of the
values within the window size.
==> 没看懂window的意思...
一个sliding windows记录key。一个hashtable记录key-value。并且计算sum,并保存。
sliding overwrite的时候,把hashtable中的记录删除,同时更新sum.
这样的话,getKey, putKey, getAverage 都是O(1)。
m**q
发帖数: 189
8
我想的是标记对应磁盘位置为invalid,可能需要另外一个数据结构去track,
当发现连续的invalid满足一定条件时集中cleanup

【在 p*****2 的大作中提到】
: ==> 类似于hash table,key就是题目中的key,value是真正的value在磁盘
: 上的位置。read就直接从hash table中查找磁盘位置再从对应的位置读取。
: write把数据append到磁盘,然后用新的位置overwrite hash table中
: 对应entry
: how to clean-up stale
: entriesn the file.
: 同意。关于how to cleanup, 我的想法是用两块磁盘,或者两个分区,或者两个文件了
: 。隔一段时间就把所有的values备份到另一块磁盘,然后转到这个磁盘。这样就可以清
: 了,两个磁盘轮番换。

m**q
发帖数: 189
9
就是说key-value pair stream的顺序是固定好的,sliding window
就是按固定的顺序调用delete-key和add-key实现的?
如果这样的话确实可以O(1)

the

【在 p*****2 的大作中提到】
: 6. pair: given a stream of unique key-value pairs. given a window size.
: write method to getKey, putKey and getAverage. consider thread-safety and
: efficiency. optimize getKey and getAverage, which returns the avearge of the
: values within the window size.
: ==> 没看懂window的意思...
: 一个sliding windows记录key。一个hashtable记录key-value。并且计算sum,并保存。
: sliding overwrite的时候,把hashtable中的记录删除,同时更新sum.
: 这样的话,getKey, putKey, getAverage 都是O(1)。

l*********y
发帖数: 142
10
2. design a hashtable, get, put, etc. consider thread-safety and hash
capacity resizing.
请问这个有好的sample code或者资料看吗,网上找了一圈,要么太浅显,要么太深入。
谢谢。
相关主题
FB电面的标准就那么高?问一道LinkedIn的设计题
问道题SQL 面试问题
[Job Opening] 3D Engine Developer - Physics and Low Level Optimization有没有人发现pinterest有个bug啊
进入JobHunting版参与讨论
d*******r
发帖数: 208
11
今天收到recruiter email
Hi xxx
I hope you had a great holiday we are all trying to catch up. I wanted ask
your interest level in Lxxx after your interviews. What were your thoughts?
不知道是什么意思。

【在 d*******r 的大作中提到】
: 名单上列了11个人。见了10个,跟名单上有临时改动,有一个的shadow没来。
: 1. given such a structure,
: id -- list of friend ids (sorted), similar to bi-directional or
: undirected graph eg.
: 1 -- 3 5 6
: 2 -- 5 8
: 3 -- 1 8
: 5 -- 1 2
: 6 -- 1
: 8 -- 2 3 9

p*****2
发帖数: 21240
12
就是说如果你感兴趣就给你offer吧?赶紧表忠心吧。
d*******r
发帖数: 208
13
多谢,或者说不敢兴趣我就不用麻烦看review了?回信把他们吹了一把,没有收到下文
了,估计在看reivew。感觉上最后一个老印肯定是据我的,估计前面的面试官有力挺的
。有几个聊的相当好。可能他们不是取决于一个人的评价吧。

【在 p*****2 的大作中提到】
: 就是说如果你感兴趣就给你offer吧?赶紧表忠心吧。
p*****2
发帖数: 21240
14

Cong了。

【在 d*******r 的大作中提到】
: 多谢,或者说不敢兴趣我就不用麻烦看review了?回信把他们吹了一把,没有收到下文
: 了,估计在看reivew。感觉上最后一个老印肯定是据我的,估计前面的面试官有力挺的
: 。有几个聊的相当好。可能他们不是取决于一个人的评价吧。

H***e
发帖数: 476
15
赞。 楼主其实答的挺好的。

【在 d*******r 的大作中提到】
: 名单上列了11个人。见了10个,跟名单上有临时改动,有一个的shadow没来。
: 1. given such a structure,
: id -- list of friend ids (sorted), similar to bi-directional or
: undirected graph eg.
: 1 -- 3 5 6
: 2 -- 5 8
: 3 -- 1 8
: 5 -- 1 2
: 6 -- 1
: 8 -- 2 3 9

H***e
发帖数: 476
16

BFS的话,不太可能就一题。而切说是sorted.是不是要求很多优化了?

【在 m**q 的大作中提到】
: ==> 谢谢分享
:
: 名单上列了11个人。见了10个,跟名单上有临时改动,有一个的shadow没来。
: 1. given such a structure,
: id -- list of friend ids (sorted), similar to bi-directional or
: undirected graph eg.
: 1 -- 3 5 6
: 2 -- 5 8
: 3 -- 1 8
: 5 -- 1 2

1 (共1页)
进入JobHunting版参与讨论
相关主题
L家onsite悲剧 贡献个面经吧DP interview question
哪儿有设计题的总结?就是那种大规模系统设计方面的。FB电面的标准就那么高?
有做video streaming的前辈吗问道题
【求教】面试fail掉,问题如何最佳回答?[Job Opening] 3D Engine Developer - Physics and Low Level Optimization
amazon 1st phone interview问一道LinkedIn的设计题
Qualcomm On-site 归发些面经,求blessSQL 面试问题
rejected by facebook after 2nd phone interview有没有人发现pinterest有个bug啊
G家悲剧,发面经即将入职亚麻的小硕求教一下今后发展方向
相关话题的讨论汇总
话题: push话题: design话题: numofbytes话题: sequencno