google 2018四月onsite面筋

lintao 发表于 2018-4-18 00:05
感谢楼主！写的好详细！ 可以发我一分文档吗？

谢谢！！！

LZ可报下工作经验吗？

楼主，第一轮要考虑重复字符吗？比如 target 是"AA"， 字典里有“A”，“AA”，这时候是返回“A” 还是返回“AA”？
第三轮，不存 query 的内容的话，怎么知道这个query 在10 秒内被call过？ 能不能给个例子？  谢谢楼主!

markpen 发表于 2018-4-18 01:21
楼主，第一轮要考虑重复字符吗？比如 target 是"AA"， 字典里有“A”，“AA”，这时候是返回“A” 还是返回 ...

你好，当时我自己假设的是没有重复的target, 然后和面试官确认，如果有的话可以用hashmap, 第三轮，这个api 是不负责说发出去的query 一定是正确的，或者有没有error被返回，这个api只负责保证rate是正确的

请问 team match 到能拿offer概率多大

凯伦小龙虾 发表于 2018-4-17 22:44
就是说每次出来一个char，我都会从root开始找看有没有符合，如果符合的话，我就把当前这个trienode指针ap ...

我随便写了个，比女神你的空间复杂度少了，但是时间复杂度好像高了。你的面试官有要求是间复杂度么？
class TrieNode():
    def __init__(self):
        self.children = {}
        self.isWord = False
class Trie(object):
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                child = TrieNode()
                node.children[c] = child
            node = node.children[c]
        node.isWord = True


class Solution():
    def printValidWords(self, wordList, charStream):
        trie = Trie()
        for word in wordList:
            trie.insert(word)

        res = []
        for i in range(len(charStream)):
            self.dfs(trie.root, charStream[i:], '', res)

        return res



    def dfs(self, node, charStream, solution, res):
        if not charStream or charStream[0] not in node.children:
            return
        solution += charStream[0]
        if node.children[charStream[0]].isWord:
            res.append(solution)
        node = node.children[charStream[0]]
        self.dfs(node, charStream[1:], solution, res)

wcg 发表于 2018-4-18 01:54
请问 team match 到能拿offer概率多大

不太清楚，不过如果已经有team要和你聊天并且你的hr表示结果很positive应该几率还是挺大的。不知道其他情况怎么样

补充内容 (2018-4-18 02:02):
还是要多和hr交流，看hr的反应吧。如果好的话，hr会直接说的，如果不确定hr可能会比较含糊

凯伦小龙虾 发表于 2018-4-18 01:50
你好，当时我自己假设的是没有重复的target, 然后和面试官确认，如果有的话可以用hashmap, 第三轮，这个a ...

我大概明白楼主的意思了。
举例说，每秒钟有1000 个query 调用这个API，如果 rate 是100 的话，就随机给100 个query 返回 true，其他的返回 false。是这样理解吗？
谢谢楼主回答！

idatascience 发表于 2018-4-18 01:56
我随便写了个，比女神你的空间复杂度少了，但是时间复杂度好像高了。你的面试官有要求是间复杂度么？
cl ...

棒！面试官没有说要求，可以自己提出假设哈，写完了可以分析清楚就好了

markpen 发表于 2018-4-18 02:00
我大概明白楼主的意思了。
举例说，每秒钟有1000 个query 调用这个API，如果 rate 是100 的话，就随机给 ...

是的，我提出说我可以index 所有query然后random n个，但面试官说好像不能存，而且最好不要有延迟。如果有好的做法，请分享哈。谢谢