攒人品，分享Pinterest面经 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 攒人品，分享Pinterest面经

相关主题
● FB面试题一道求解	● 问一道面试设计题
● 问一道题	● design search engine typeahead的问题
● 问一道题	● LeetCode Jump Game [Runtime Error]
● 分享一盗题	● leetcode jump game 用一维DP做
● suffix tree 和 trie	● 问道老题
● 面试的时候用到Trie，要求实现吗？	● Leetcode 上的jump game有人做出来了吗？
● 最近好几个trie的面试题，有人愿意分享一下trie到底怎么implement的吗？	● 问道面试提
● google 电面fast phone book loopup	● 一道变形的Jump题

相关话题的讨论汇总
话题: pinterest话题: jump话题: retprefix话题: 位置话题: curstr

进入JobHunting版参与讨论

(共1页)

r****m
发帖数: 70

HR先介绍流程
1. 接着和一个engineer吃饭，同胞，吃饭同桌的还有好几个其他同胞，用中文聊了一
会天，吃完饭开始面试，讨论了很多distribute的东西，shard, hash, queue之类,
怎么design pinterest homepage.
2. 接下来另engineer，但没口音，问了两道题
a. 给一个数组和一个位置，从该位置起左右jump，检测能否jump到值为0的位置,
canJump(int a[], int pos)
b. 给一组字符串，找最长的公共前缀，至少两个字符串公共
3. Hire Manager, 让我介绍了一下项目，然后问了我能想到的怎么improve pinterest
每次查询，将查询字符串写入日志文件，查找出现次数前十的查询字符串
我用priority queue实现，然后问我怎么实现priority queue, 我给他介绍了堆的
实现: 插入、删除和调整
然后问在不同机器怎么办
4. 非技术, 问了最自豪的项目和好几个behavior的问题
5. 和HR随便聊聊，结束面试
已经被拒，分享出来希望对大家有帮助

l*****a
发帖数: 14598

谢谢分享
改天做作

pinterest

【在 r****m 的大作中提到】

: HR先介绍流程
: 1. 接着和一个engineer吃饭，同胞，吃饭同桌的还有好几个其他同胞，用中文聊了一
: 会天，吃完饭开始面试，讨论了很多distribute的东西，shard, hash, queue之类,
: 怎么design pinterest homepage.
: 2. 接下来另engineer，但没口音，问了两道题
: a. 给一个数组和一个位置，从该位置起左右jump，检测能否jump到值为0的位置,
: canJump(int a[], int pos)
: b. 给一组字符串，找最长的公共前缀，至少两个字符串公共
: 3. Hire Manager, 让我介绍了一下项目，然后问了我能想到的怎么improve pinterest
: 每次查询，将查询字符串写入日志文件，查找出现次数前十的查询字符串

l**h
发帖数: 893

这题可不可以再说仔细点, 一次Jump一个位置，不是任何点都能Jump到吗?
a. 给一个数组和一个位置，从该位置起左右jump，检测能否jump到值为0的位置,
canJump(int a[], int pos)

pinterest

【在 r****m 的大作中提到】

f*****e
发帖数: 2992

为啥悲剧啊？答得挺好的。

pinterest

【在 r****m 的大作中提到】

l**h
发帖数: 893

给一个数组和一个位置，从该位置起左右jump，检测能否jump到值为0的位置, canJump
(int a[], int pos)
这一天是怎么回事? 左右jump不是肯定能到吗

pinterest

【在 r****m 的大作中提到】

c********t
发帖数: 5706

a. 给一个数组和一个位置，从该位置起左右jump，检测能否jump到值为0的位置,
canJump(int a[], int pos)
是可以选择left or right吗？是一旦跳到0就终止吗，还是必须跳完所有数。应该是个
DP题吧。
b. 给一组字符串，找最长的公共前缀，至少两个字符串公共
找的是所有字符的公共前缀，还是任意两个的？看你的意思，好像是任意两个的，还真
没做过。用trie?

pinterest

【在 r****m 的大作中提到】

h***i
发帖数: 1970

BFS
rolling hash应该可以。

【在 c********t 的大作中提到】

: a. 给一个数组和一个位置，从该位置起左右jump，检测能否jump到值为0的位置,
: canJump(int a[], int pos)
: 是可以选择left or right吗？是一旦跳到0就终止吗，还是必须跳完所有数。应该是个
: DP题吧。
: b. 给一组字符串，找最长的公共前缀，至少两个字符串公共
: 找的是所有字符的公共前缀，还是任意两个的？看你的意思，好像是任意两个的，还真
: 没做过。用trie?
:
: pinterest

r*********n
发帖数: 4553

Here is what I can think of:
build a trie such that each node has a pointer to its parent
locate 1st string's node in the trie
from that node, walk upwards to the root and mark visited nodes on the way
for the 2nd string, do the same thing except that when first encounter a
marked node, that is the lowest common ancestor (LCA) for the 1st and 2nd
strings.
repeat for all strings. you then find all LCAs, from the deepest of which
you can easily find the longest common prefix
pinterest

【在 r****m 的大作中提到】

h****n
发帖数: 1093

都是leetcode老题了楼主看来没做leetcode

HR先介绍流程1. 接着和一个engineer吃饭，同胞，吃饭同桌的还有好几个其他同胞，
用中文聊了一会天，吃完饭开始面试，讨论了很多distribute的东西，shard, h......
..

【在 r****m 的大作中提到】

r****m
发帖数: 70

相关主题
● 面试的时候用到Trie，要求实现吗？	● 问一道面试设计题
● 最近好几个trie的面试题，有人愿意分享一下trie到底怎么implement的吗？	● design search engine typeahead的问题
● google 电面fast phone book loopup	● LeetCode Jump Game [Runtime Error]
进入JobHunting版参与讨论

l*****a
发帖数: 14598

谢谢分享
改天做作

pinterest

【在 r****m 的大作中提到】

l**h
发帖数: 893

f*****e
发帖数: 2992

为啥悲剧啊？答得挺好的。

pinterest

【在 r****m 的大作中提到】

l**h
发帖数: 893

c********t
发帖数: 5706

h***i
发帖数: 1970

BFS
rolling hash应该可以。

【在 c********t 的大作中提到】

r*********n
发帖数: 4553

h****n
发帖数: 1093

f********a
发帖数: 165

哪位大牛分析下1和3.
1是不是和设计news feed差不多啊？对图片和文字的ｎｅｗｓ　ｆｅｅｄ处理是不是差
不多？
３怎么ｉｍｐｒｏｖｅ每次查询，是不是要考虑ｃｌｉｃｋ　Ｍｏｄｅｌ和类似ｐａｇ
ｅｒａｎｋ的对图片的Ｌｉｋｅ或者ｒｅｐｉｎ做排序？感觉是要和ｓｅ　ｅｖａｌｕ
ａｔｉｏｎ联系起来，不知道对不对。

pinterest

【在 r****m 的大作中提到】

g***9
发帖数: 159

第二题公共前缀并不是leetcode原题吧...
请教大牛 rolling hash 的解法 .. ?
自己写了一个Trie的python版本:
import sys
CHAR_COUNT = 26
class Entry(object):
def __init__(self, count=0, next=None):
self.cnt = count
self.nxt = next
#def
#class
class TrieNode(object):
def __init__(self):
self.entrylist = []
for i in xrange(CHAR_COUNT):
self.entrylist.append(Entry())
#for
#def
#class

root = TrieNode()
def InsertTrieNodes(root, curstr):
n = len(curstr)
prefix = []

curnode = root
valid = True
cnt = 0

for i in xrange(n):
index = int(ord(curstr[i]) - ord('a'))
entry = curnode.entrylist[index]
if entry.nxt:
if valid:
prefix.append(curstr[i])
#if
entry.cnt += 1
cnt = entry.cnt
else:
valid = False
entry.nxt = TrieNode()
entry.cnt = 1
#else
curnode = curnode.entrylist[index].nxt
#for

return (''.join(prefix), cnt)
#def
def FindCommonPrefix(strlist):
retprefix = ''
maxcnt = 0
n = len(strlist)
if n < 2:
return retprefix
#if
for curstr in strlist:
(curprefix, cnt) = InsertTrieNodes(root, curstr)
if len(curprefix) >= len(retprefix):
retprefix = curprefix
maxcnt = cnt
#if
#for
return (retprefix, maxcnt)
#def
strlist = ['a', 'abc', 'bcd', 'abcd', 'bbb', 'bcbc', 'abcce', 'abc']
(retprefix, maxcnt) = FindCommonPrefix(strlist)
print (retprefix, maxcnt)

相关主题
● leetcode jump game 用一维DP做	● 问道面试提
● 问道老题	● 一道变形的Jump题
● Leetcode 上的jump game有人做出来了吗？	● 面试设计题，设计电话簿, 除了用trie?
进入JobHunting版参与讨论

c******a
发帖数: 789

最长prefix的确是leetcode原题。sort完第一个和最后一个的prefix就是最长的。
jump那个拓展的很有意思，还是用greedy就可以了。

x*****0
发帖数: 452

mark

s**********r
发帖数: 8153

Mark

h******u
发帖数: 3

我觉得第二题用trie+bfs可以搞定

【在 c********t 的大作中提到】

s**********r
发帖数: 8153

不是吧。这个是变形。
而且也不是sort 完第一个和最后一个前缀吧。。

【在 c******a 的大作中提到】

: 最长prefix的确是leetcode原题。sort完第一个和最后一个的prefix就是最长的。
: jump那个拓展的很有意思，还是用greedy就可以了。

y*c
发帖数: 904

mark
pinterest这个公司如何啊？

y*c
发帖数: 904

mark

(共1页)

进入JobHunting版参与讨论

相关主题
● 一道变形的Jump题	● suffix tree 和 trie
● 面试设计题，设计电话簿, 除了用trie?	● 面试的时候用到Trie，要求实现吗？
● 一道MS题	● 最近好几个trie的面试题，有人愿意分享一下trie到底怎么implement的吗？
● rejected by facebook after 2nd phone interview	● google 电面fast phone book loopup
● FB面试题一道求解	● 问一道面试设计题
● 问一道题	● design search engine typeahead的问题
● 问一道题	● LeetCode Jump Game [Runtime Error]
● 分享一盗题	● leetcode jump game 用一维DP做

相关话题的讨论汇总
话题: pinterest话题: jump话题: retprefix话题: 位置话题: curstr

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天