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 | | s******n
发帖数: 3946 | | 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或者资料看吗，网上找了一圈，要么太浅显，要么太深入。
谢谢。 | | | 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
|
|
