狗狗欧塞特面经

Job Hunting Interview
, , , , ,
1

这周一去了狗狗onsite，发个面经攒人品

  1. 一个中国小姐姐，感觉刚开始面试别人，业务有点不熟练。第一类似于graph里面找从A点出发回到A点的最短loop，要求输出长度以及path，BFS和DFS都说了，BFS更加好，要求我用BFS。要打印path，所以我用了两个queue，小姐姐希望其他更加省memory的做法，没想出来，就按照我的想法写了代码，写完跑了testcase。最后她有讨论一下她觉得可以省memory的做法，用hashmap，但是她好像自己也记不清到底怎么实现了，讲的我感觉不太对，我也没和她继续讨论。第二题类似topological sorting变形，讨论了做法没有实现代码。
  2. 一个白人小哥哥，给你一个source string, 要求找长度为K的字母排序最前面的subsequence，一开始思路不明确，先随便讨论了一下brute force的解法，时间复杂度2^n * K，问能不能提高，想出了N*K的解法，写了代码。继续问对于最差的Corner case怎么提高，用上了heap，继续改了代码。follow-up问如果要top 10 subsequence。. From 1point 3acres bbs
  3. 一个白人小哥哥，给你一个map，知道state和state之间相连的关系，再给你一个dictionary，包含words，让你找出从任意一个state出发，每个state取首字母，可以找到的word。讨论的时候小哥说可以重复visit一个state，我就问他那停止条件是什么，他可能自己都没想过这个问题，我就问那就统计字典里最长单词的长度作为停止条件，他说可以的。先用了最简单的hashset和DFS做了，写完代码，问我能improve吗，我就说用trie，可以剪枝，代码重新改了一遍。follow-up问如果是要你找出anagram呢？
  4. 一个白人大妈，一道graph题目，给你一个graph，要求你根据给定的order，找出最长的path，不能有环，一开始朝graph方向想，最后发现是用slide window做，代码写完以后，跑了testcase, 大妈有问一些基础问题，类似linkedlist和arraylist区别，hashset原理。第二题是一道经典BFS题目，一个board上面有Bacteria，Air以及blank，找出有几团B是可以接触到A的，其实就是number of islands变形，讨论了解法没有实现代码。

补充内容 (2018-11-24 14:44):
对了，题目都不会给你明确的input，output，都要自己讨论

3

已加米，请问楼主在哪里面的？谢谢

4

虾图

5

能问下第二题N*K是怎么做的吗？

6

西雅图可以用chromebook，楼主是用吗？ 还是白板

7

楼主是在fremont还是在kirkland面的？

8

楼主请问第一题最短loop是要遍历图中所有点的path吗？谢谢。

9

楼主，第二题能不能稍微举个栗子？谢谢哈

10

最长的path，不能有环怎麼會用slide window？？求解釋lz

11

第二题：

def findTopSubseuqnce(str, k):. 1point3acres
    def helper(str, k):
        if not str:
            return []
        if len(str) <= k:
            return list(str)
        stack = []
        for i in range(len(str)):
            if not stack:
                stack.append(str[i])
            else:
                while stack and str[i] < stack[-1]:
                    if len(stack) + (len(str) - i) <= k:
                        return stack + list(str[i:])
                    stack.pop()
                stack.append(str[i])
        return stack
    return helper(str, k)