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]

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

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”]