回馈本版 众小公司面经# JobHunting - 待字闺中
w*n
1 楼
骑驴找马告一段落 从了某preipo的 在此献上 面经
这次感觉coding题都不难 主要是design 甚至flag preipo的coding题比很多小的公司
都简单 但是design更难
flag 和 preipo的面经不能放上来 主要是不敢得罪这些签了NDA的
很多题目没有正确答案 在于想法 以及tradeoff
sift science (offer):
1 given a nxn chessboard, there are only pawns (white and black) on it. Say
one side is the start and its opposite side is the end. There is one white
pawn on the start row, what are the cells that could be reached on the end
side.
2 given a binary tree, implement sibling (each nodes sibling is the next
node of the same depth). Each node has a point called sibling initialized to
null, implement a function such that all nodes' sibling pointer should have
proper value.
3. Given 1 billion data point (key, value with 15 bytes of string and 8 byte
of double value); store this in the memory that supports fast lookup.
4. Given 100 TB files, each line is a url and a timestamp. Find the top 10
urls hit in some time range. You have 100 machines.
5. Fraudulent user detection, find weakly connected component in large graph
(100k nodes, single machine). This question needs to be compiled and run on
a mac.
6. Given a string, check if it could be decomposed into substring, which is
each an element symbol. physics => P H Y Si C S
7. Given a binary search tree, find least common ancestor.
origami logic (offer):
1 Find median in 100 TB files distributed on 100 machine
2 Design talk; cycle detection in graph (small) = > million nodes on one
machine => billion nodes on multiple machine
3 Flatten dictionary {a:{b:c, e:f}, e: {a:c}, r:f} => [[a,b,c], [a,e,f], [e,
a,c], [r,f]]
4 Data cleaning technique / operator/ functional
5 game of life: one node max size of grid; make it even more scalable;
distributed solution: complexity; fault tolerance; performance, persistence
6 common substring of two strings
7 print english for number: 2 -> two; 3144 -> three thousand one hundred
forty four; 12395113 -> twelve million three hundred ninety five thousand
one hundred thirteen; my english was brutalized through this questions
chartboost (offer):
1 mapreduce join:
input A: tx_id, campaign_id (HUGE)
input B: campaign_id, country_id, campaign_type (could be big or small)
output should be: country_id, campaign_type, count
discuss how to design mr job when 1) B is very small 2) large enough, but
small enough to be on disk on one machine 3) very large (100+tb)
2 design a realtime counter
3 design a single machine database for fixed key value data (10+tb) variable
key size and variable value size (could be thousand bytes)
4 describe the component I am responsible for and what could I have done
better to design today
vessel (rej)
1) ood design + implementation an option library to support 1) short version
and long version (cmd -v and cmd --version) 2) supports boolean and string
value for options 3) customizable value
2) implement tree http://en.wikipedia.org/wiki/Tree_(Unix)
affirm (rej)
1) design a money transfer system between banks (implement venmo); need both
high level architecture and low level implementation details around data
passing and data store
2) implement a interpreter that evaluates polish notation (+ 3 4) or (- (+
4 5) 2); improve the evaluator to support variables and assignment (let a 2
(+ a 2)) should give 4, (let a 2 (+ a let b 3 (* b 3))) should give 11
3) constant memory traversal of a tree (mutable)
4) oop / system design a data ingestion system which supports multiple
ingestion protocal (ftp, SOAP, rest, streaming); go into details about
runtime and data storage.
这次感觉coding题都不难 主要是design 甚至flag preipo的coding题比很多小的公司
都简单 但是design更难
flag 和 preipo的面经不能放上来 主要是不敢得罪这些签了NDA的
很多题目没有正确答案 在于想法 以及tradeoff
sift science (offer):
1 given a nxn chessboard, there are only pawns (white and black) on it. Say
one side is the start and its opposite side is the end. There is one white
pawn on the start row, what are the cells that could be reached on the end
side.
2 given a binary tree, implement sibling (each nodes sibling is the next
node of the same depth). Each node has a point called sibling initialized to
null, implement a function such that all nodes' sibling pointer should have
proper value.
3. Given 1 billion data point (key, value with 15 bytes of string and 8 byte
of double value); store this in the memory that supports fast lookup.
4. Given 100 TB files, each line is a url and a timestamp. Find the top 10
urls hit in some time range. You have 100 machines.
5. Fraudulent user detection, find weakly connected component in large graph
(100k nodes, single machine). This question needs to be compiled and run on
a mac.
6. Given a string, check if it could be decomposed into substring, which is
each an element symbol. physics => P H Y Si C S
7. Given a binary search tree, find least common ancestor.
origami logic (offer):
1 Find median in 100 TB files distributed on 100 machine
2 Design talk; cycle detection in graph (small) = > million nodes on one
machine => billion nodes on multiple machine
3 Flatten dictionary {a:{b:c, e:f}, e: {a:c}, r:f} => [[a,b,c], [a,e,f], [e,
a,c], [r,f]]
4 Data cleaning technique / operator/ functional
5 game of life: one node max size of grid; make it even more scalable;
distributed solution: complexity; fault tolerance; performance, persistence
6 common substring of two strings
7 print english for number: 2 -> two; 3144 -> three thousand one hundred
forty four; 12395113 -> twelve million three hundred ninety five thousand
one hundred thirteen; my english was brutalized through this questions
chartboost (offer):
1 mapreduce join:
input A: tx_id, campaign_id (HUGE)
input B: campaign_id, country_id, campaign_type (could be big or small)
output should be: country_id, campaign_type, count
discuss how to design mr job when 1) B is very small 2) large enough, but
small enough to be on disk on one machine 3) very large (100+tb)
2 design a realtime counter
3 design a single machine database for fixed key value data (10+tb) variable
key size and variable value size (could be thousand bytes)
4 describe the component I am responsible for and what could I have done
better to design today
vessel (rej)
1) ood design + implementation an option library to support 1) short version
and long version (cmd -v and cmd --version) 2) supports boolean and string
value for options 3) customizable value
2) implement tree http://en.wikipedia.org/wiki/Tree_(Unix)
affirm (rej)
1) design a money transfer system between banks (implement venmo); need both
high level architecture and low level implementation details around data
passing and data store
2) implement a interpreter that evaluates polish notation (+ 3 4) or (- (+
4 5) 2); improve the evaluator to support variables and assignment (let a 2
(+ a 2)) should give 4, (let a 2 (+ a let b 3 (* b 3))) should give 11
3) constant memory traversal of a tree (mutable)
4) oop / system design a data ingestion system which supports multiple
ingestion protocal (ftp, SOAP, rest, streaming); go into details about
runtime and data storage.
