r****m 发帖数: 70 | 1 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 | 2 谢谢分享
改天做作
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | 3 这题可不可以再说仔细点, 一次Jump一个位置,不是任何点都能Jump到吗?
a. 给一个数组和一个位置,从该位置起左右jump,检测能否jump到值为0的位置,
canJump(int a[], int pos)
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| f*****e 发帖数: 2992 | 4 为啥悲剧啊?答得挺好的。
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | 5 给一个数组和一个位置,从该位置起左右jump,检测能否jump到值为0的位置, canJump
(int a[], int pos)
这一天是怎么回事? 左右jump不是肯定能到吗
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| c********t 发帖数: 5706 | 6 a. 给一个数组和一个位置,从该位置起左右jump,检测能否jump到值为0的位置,
canJump(int a[], int pos)
是可以选择left or right吗?是一旦跳到0就终止吗,还是必须跳完所有数。应该是个
DP题吧。
b. 给一组字符串,找最长的公共前缀,至少两个字符串公共
找的是所有字符的公共前缀,还是任意两个的?看你的意思,好像是任意两个的,还真
没做过。用trie?
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| h***i 发帖数: 1970 | 7
BFS
rolling hash应该可以。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a. 给一个数组和一个位置,从该位置起左右jump,检测能否jump到值为0的位置, : canJump(int a[], int pos) : 是可以选择left or right吗?是一旦跳到0就终止吗,还是必须跳完所有数。应该是个 : DP题吧。 : b. 给一组字符串,找最长的公共前缀,至少两个字符串公共 : 找的是所有字符的公共前缀,还是任意两个的?看你的意思,好像是任意两个的,还真 : 没做过。用trie? : : pinterest
| r*********n 发帖数: 4553 | 8
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| h****n 发帖数: 1093 | 9 都是leetcode老题了 楼主看来没做leetcode
HR先介绍流程1. 接着和一个engineer吃饭,同胞,吃饭同桌的还有好几个其他同胞,
用中文聊了一会天,吃完饭开始面试,讨论了很多distribute的东西,shard, h......
..
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| r****m 发帖数: 70 | 10 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 | 11 谢谢分享
改天做作
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | 12 这题可不可以再说仔细点, 一次Jump一个位置,不是任何点都能Jump到吗?
a. 给一个数组和一个位置,从该位置起左右jump,检测能否jump到值为0的位置,
canJump(int a[], int pos)
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| f*****e 发帖数: 2992 | 13 为啥悲剧啊?答得挺好的。
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | 14 给一个数组和一个位置,从该位置起左右jump,检测能否jump到值为0的位置, canJump
(int a[], int pos)
这一天是怎么回事? 左右jump不是肯定能到吗
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| c********t 发帖数: 5706 | 15 a. 给一个数组和一个位置,从该位置起左右jump,检测能否jump到值为0的位置,
canJump(int a[], int pos)
是可以选择left or right吗?是一旦跳到0就终止吗,还是必须跳完所有数。应该是个
DP题吧。
b. 给一组字符串,找最长的公共前缀,至少两个字符串公共
找的是所有字符的公共前缀,还是任意两个的?看你的意思,好像是任意两个的,还真
没做过。用trie?
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| h***i 发帖数: 1970 | 16
BFS
rolling hash应该可以。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a. 给一个数组和一个位置,从该位置起左右jump,检测能否jump到值为0的位置, : canJump(int a[], int pos) : 是可以选择left or right吗?是一旦跳到0就终止吗,还是必须跳完所有数。应该是个 : DP题吧。 : b. 给一组字符串,找最长的公共前缀,至少两个字符串公共 : 找的是所有字符的公共前缀,还是任意两个的?看你的意思,好像是任意两个的,还真 : 没做过。用trie? : : pinterest
| r*********n 发帖数: 4553 | 17
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| h****n 发帖数: 1093 | 18 都是leetcode老题了 楼主看来没做leetcode
HR先介绍流程1. 接着和一个engineer吃饭,同胞,吃饭同桌的还有好几个其他同胞,
用中文聊了一会天,吃完饭开始面试,讨论了很多distribute的东西,shard, h......
..
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| f********a 发帖数: 165 | 19 哪位大牛分析下1和3.
1是不是和设计news feed差不多啊?对图片和文字的news feed处理是不是差
不多?
3怎么improve每次查询,是不是要考虑click Model和类似pag
erank的对图片的Like或者repin做排序?感觉是要和se evalu
ation联系起来,不知道对不对。
pinterest
【在 r****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 : 每次查询,将查询字符串写入日志文件,查找出现次数前十的查询字符串
| g***9 发帖数: 159 | 20 第二题公共前缀并不是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) | | | c******a 发帖数: 789 | 21 最长prefix的确是leetcode原题。sort完第一个和最后一个的prefix就是最长的。
jump那个拓展的很有意思,还是用greedy就可以了。 | x*****0 发帖数: 452 | | s**********r 发帖数: 8153 | | h******u 发帖数: 3 | 24 我觉得第二题 用trie+bfs可以搞定
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a. 给一个数组和一个位置,从该位置起左右jump,检测能否jump到值为0的位置, : canJump(int a[], int pos) : 是可以选择left or right吗?是一旦跳到0就终止吗,还是必须跳完所有数。应该是个 : DP题吧。 : b. 给一组字符串,找最长的公共前缀,至少两个字符串公共 : 找的是所有字符的公共前缀,还是任意两个的?看你的意思,好像是任意两个的,还真 : 没做过。用trie? : : pinterest
| s**********r 发帖数: 8153 | 25 不是吧。这个是变形。
而且也不是sort 完第一个和最后一个前缀吧。。
【在 c******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最长prefix的确是leetcode原题。sort完第一个和最后一个的prefix就是最长的。 : jump那个拓展的很有意思,还是用greedy就可以了。
| y*c 发帖数: 904 | | y*c 发帖数: 904 | |
|