谷歌店面 - New Grad

直接做题

n students [0, …, n-1] participate in a marathon. You are given an int array standings where standings[i] = j means that student j finished just before student i. standings[k] = -1 means that k is the first student. There are no ties. List out the students in the order in which they finished the marathon.

Example:

Input: [-1, 0, 1]
Output: [0, 1, 2]
Follow-up:
There are ties.

Example:

Input: [-1, 0, 0]
Output: [0, 1, 2]

我是内推拿到的

面试官人很nice。一道题45分钟,2个follow up

  1. 输入一个string,一个number代表最大不同字符数,返回最长连续子串,子串内不同字符数目不超过number。双指针O(n)秒-baidu 1point3acres
  2. follow up,如果number很大,子串会很长,是个流式输入,不能存在内存,怎么办。
    up 1:每次记录字符最后更新的坐标。这样如果新进入字符没有出现过,且加入子串后的总字符类型数大于number,把最后更新坐标中最小的字符去掉。更新长度。这个最小实际用最小堆来做。可以保证到nlogk。
    up 2: 面试官问有没有o(1)解法,并且提到了删除插入都是o(1),模拟过程后回复lru cache。用双向裢表存,而不是用堆存,当新的input 字符进入,如果字符存在于裢表中,将它提出,放到裢表尾部,如果不存在且字符类型数目大于number,将裢表头删除。
    讨论了5分钟,第一题用了1分钟,第二题大概用了10分钟写代码,5分钟想,第三题用了10分钟想,10分钟写代码。最后提问环节,我问这个怎么只有一道题,面试官说这是三道题,回答的还不错。感觉应该过了
1 Like

想问下是new grad么

看帖子的tag,是的

也报个店面题目

In this problem we will extend Longest Word in Dictionary by allowing insertion of a new character in any position not only at the end. Return the construction path of the longest word.

Example 1:

Input: words = [“o”, “or”, “ord”, “word”, “world”]
Output: [“o”, “or”, “ord”, “word”, “world”]
Example 2:

Input: [“o”, “or”, “ord”, “word”, “world”, “p”, “ap”, “ape”, “appe”, “apple”, “apples”]
Output: [“p”, “ap”, “ape”, “appe”, “apple”, “apples”]