G家实习电面挂经

wey066 发表于 2016-11-27 11:56
楼主你好！

我跟你同一天实习面试，至今没有hr回复，请问你有后续了吗？

那都已经两个多星期了啊，我前两天面的，听内推的学姐说过节这段时间可能会慢一些

夜皇雪 发表于 2016-11-27 03:36
问一下楼主，第一面第二题，你说给一个list，是指int nums[]这种还是List list 这种啊

没有说明，但是说了这些类似的条件都可以自己假定

wey066 发表于 2016-11-27 11:56
楼主你好！

我跟你同一天实习面试，至今没有hr回复，请问你有后续了吗？

17号已经通知挂了，你这应该是因为感恩节耽搁了，不过没有通知挂的话希望蛮大的

google家电面都是不需要准确跑的吗？？就是在google doc上写然后就是嘴跑大致思路啥没问题就行吗

夜皇雪 发表于 2016-11-27 12:55
google家电面都是不需要准确跑的吗？？就是在google doc上写然后就是嘴跑大致思路啥没问题就行吗

不是，第一面开始code前明确说了要make sure don't crash，第二面写出来的码可以看到小哥全选了，应该是复制粘贴拿去跑了

第一题用linkedlist就只能能找到吧

zzgzzm 发表于 2016-11-9 12:00
第二面：这个题等价于求string s中的最长subsequence found in dictionary（注意是subsequence，不是substr ...

你确定你对题目的理解是对的？

衫衫水水 发表于 2016-11-28 09:12
你确定你对题目的理解是对的？

你是指将题目转化为找最长的s的subsequence in dictionary?因为将s任意删去一些字母的操作和指定s的一个subsequence 是一一对应的（我包括了s本身也为其subsequence 的情况）。这样的等价转化不对吗？请指正。

用了trie合并字典中的prefix
预处理S，把a~z在S中的index按照先后次序存进charList中
idxs表示目前各个char的index
每选一个char需要把其他所有char的index增加使得其他的char index都比所选char index的还大

另外写了brute force的方法，和test的method
跑出来brute force的比较快啊。。。
10 个 case 的数据
trie time: 5.45
brute time: 0.08
trie time: 3.86
brute time: 0.05
trie time: 3.96
brute time: 0.05
trie time: 5.05
brute time: 0.07
trie time: 3.90
brute time: 0.05
trie time: 4.13
brute time: 0.05
trie time: 3.64
brute time: 0.05
trie time: 5.44
brute time: 0.07
trie time: 3.43
brute time: 0.04
trie time: 4.07
brute time: 0.05
单位是秒

1. from random import choice, randint
   
2. import string
   
3. from time import time
   
4. 
   
5. def dictSearch(S, words):
   
6.     global ans
   
7.     trie = Trie()
   
8. 
   
9.     for word in words:
   
10.         trie.insert(word)
    
11. 
    
12.     charList = [list() for _ in range(26)]
    
13.     for i, c in enumerate(S):
    
14.         charList[ord(c) - ord('a')].append(i)
    
15. 
    
16.     idxs = [0] * 26
    
17.     ans = ""
    
18. 
    
19.     def dfs(node, cur_idxs):
    
20.         global ans
    
21.         if node is None:
    
22.             return
    
23.         if node.isword and len(node.word) > len(ans):
    
24.             ans = node.word
    
25.         for i, child in enumerate(node.childs):
    
26.             if child and cur_idxs[i] < len(charList[i]):
    
27.                 idxs = list(cur_idxs)
    
28.                 for j in range(26):
    
29.                     while idxs[j] < len(charList[j]) and charList[j][idxs[j]] < charList[i][idxs[i]]:
    
30.                         idxs[j] += 1
    
31.                 dfs(child, idxs)
    
32.         return
    
33. 
    
34.     dfs(trie.root, idxs)
    
35.     return ans
    
36. 
    
37. class Trie:
    
38.     def __init__(self):
    
39.         self.root = TrieNode()
    
40. 
    
41.     def insert(self, word):
    
42.         i = self.root
    
43.         for c in word:
    
44.             t = ord(c) - ord('a')
    
45.             if i.childs[t] == None:
    
46.                 i.childs[t] = TrieNode()
    
47.             i = i.childs[t]
    
48.         i.isword = True
    
49.         i.word = word
    
50. 
    
51. class TrieNode:
    
52.     def __init__(self):
    
53.         self.isword = False
    
54.         self.childs = [None] * 26
    
55.         self.word = None
    
56. 
    
57. 
    
58. def brute(S, words):
    
59.     ans = ''
    
60.     for word in words:
    
61.         next = 0
    
62.         for c in word:
    
63.             next = S.find(c, next)
    
64.             if next == -1:
    
65.                 break
    
66.         else:
    
67.             if len(word) > len(ans):
    
68.                 ans = word
    
69.     return ans
    
70. 
    
71. def test():
    
72.     for i in range(10):
    
73.         S = ''.join(choice(string.ascii_lowercase) for _ in range(randint(500,1000)))
    
74.         words = [''.join(choice(string.ascii_lowercase) for _ in range(randint(10,20))) for _ in range(randint(10000, 20000))]
    
75.         words.sort()
    
76. 
    
77.         now = time()
    
78. 
    
79.         trie_result = dictSearch(S, words)
    
80.         print('trie time: %.2f' % (time() - now))
    
81. 
    
82.         now = time()
    
83.         brute_result = brute(S, words)
    
84.         print('brute time: %.2f' % (time() - now))
    
85. 
    
86.         assert(trie_result == brute_result)

复制代码

zzgzzm 发表于 2016-11-10 03:41
即使用O(|s|)时间判断字典中每个单词w是否是s的sunsequence，那么总时间O(|s|*|D|)也会有很多浪费的地方 ...

你好 如果是求longest substring应该怎么做