LCPython/google.md at master · VincentUCLA/LCPython
第一轮：给两个字母串 str1 = "ABABZ", str2 = "ABZ", 判断str1能否用str2中的字符拼成，如果能，最少的步数是多少？例子，从str2中取"A"，"B"，"A"，"B"，"Z"一共五步，但如果取"AB"，"ABZ"只需要两步。follow up，如果str2中有duplicate，BFS shortest path问题
第一个题的解释，换一种说法，就是从str2里每次可以取出一个substring，需要取多少次才能拼成str1.在没有duplicate的情况下，直接比较下一个字符串是否相同。
先要判断能不能成。如果str1里有字符不在str2，就不能成。 能成的情况下最多len(strt1)肯定可以嘛，所以要求的是最少需要几次。
问了大神，第一题比较好的思路是 记录每个字符在str2里的位置，再把str1里的字符过一遍，如果在str2的位置不连续就要增加步数
第二轮：in-order traversal, 给N，能否print出in order顺序第N个数。follow up，若已知每个node下面有多少个descendent，如何更快print出第N个数，binary search。具体实现的时候和面试官讨论了比较多的细节，也要了提示。
第三轮：同义词，给出很多pair的同义词，判断两个词是否为同义词，dfs，union find
第四轮：这一轮就是LC新出的920，如果能提前看过思路会清晰很多。中间讨论的时间花了太多，code没能写完，只实现了random play（我一开始写了O（N）的，如果之前看过类似的题，可以轻松给出O（1）解决方案），follow up的问题也没问到（组合数）。中途发现面试官的脸色也不太好，最后催着把code补充完
第四轮的complexity，题目的要求是写一个class，比如说Player，实现playNextSong这个method的复杂度是O（1）。
Read full article from LCPython/google.md at master · VincentUCLA/LCPython
No comments:
Post a Comment