- 设计一个 Map class， 放进去的key value pair 有expiration，也就是ttl。接口是 get(key), put(key, value, ttl)
- 设计一个 Timer class，这里有多个不同的版本或变种。一个就是schedule 一个 event，给一定的delay 时间，要求在delay 一定时间后trigger 该event，这里要涉及多线程概念。还有提供你一些辅助函数，比如 set_hw_timer 这种，认为调用该函数就会在一定时间后自动trigger event。大概是不断调用自己函数的写法，另外需要存放一个Heap。比如 狗家店面 新题！
- Interface logger 需要 implement两个方法，start和stop，并提供 helper 函数 log 方法。输入是一堆请求。先是对同一个request，当stop被调用，就log这个request的开始时间和结束时间。按格式输出：请求的开始时间和结束时间和请求id。followup是要求按请求开始时间升序。某个请求未结束时不能输出，不考虑多线程。followup需要用heap或priorityqueue来做。
interface Logger {
/**
* When a process starts, it calls 'start' with processId and startTime.
*/
void start(String processId, long startTime);
/**
* When the same process ends, it calls 'end' with processId and endTime.
*/
void end(String processId, long endTime);
/**
* Prints the logs of this system sorted by the start time of processes in the below format
* {processId} started at {startTime} and ended at {endTime}
*/
void print();
}
Example:
Logger log = new MyLogger();
log.start("1", 100);
log.start("2", 101);
log.end("2", 102);
log.start("3", 103);
log.end("1", 104);
log.end("3", 105);
log.print();
Output:
1 started at 100 and ended at 104
2 started at 101 and ended at 102
3 started at 103 and ended at 105
-
设计 API Rate Limiter，参考
https://leetcode.com/discuss/interview-question/124558/Implement-a-Rate-Limiter/ -
设计系统来查询 Nearby Restaurants/Friends (a proximity server)
-
设计 Web Crawler，参考
https://leetcode.com/discuss/interview-question/124657/Design-a-distributed-web-crawler-that-will-crawl-all-the-pages-of-wikipedia/ -
设计分布式缓存 - 基本就是一致性哈希解释一下
-
设计 Load Balancer的数据结构，其实就是 leetcode 原题
https://leetcode.com/problems/insert-delete-getrandom-o1
https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed -
设计 key value store
-
设计 Search Autocomplete System
就是 leetcode 原题 https://leetcode.com/problems/design-search-autocomplete-system
🔎详情点击展开
Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#' ). For each character they type except ‘#’ , you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:
- The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
- The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
- If less than 3 hot sentences exist, then just return as many as you can.
- When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.
Your job is to implement the following functions:
The constructor function:
AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical data . Sentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data.
Now, the user wants to input a new sentence. The following function will provide the next character the user types:
List<String> input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ( 'a' to 'z' ), blank space ( ' ' ) or a special character ( '#' ). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.
Example:
Operation: AutocompleteSystem([“i love you”, “island”,“ironman”, “i love leetcode”], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
"i love you" : 5 times
"island" : 3 times
"ironman" : 2 times
"i love leetcode" : 2 times
Now, the user begins another search:
Operation: input(‘i’)
Output: [“i love you”, “island”,“i love leetcode”]
Explanation:
There are four sentences that have prefix "i" . Among them, “ironman” and “i love leetcode” have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, “i love leetcode” should be in front of “ironman”. Also we only need to output top 3 hot sentences, so “ironman” will be ignored.
Operation: input(’ ')
Output: [“i love you”,“i love leetcode”]
Explanation:
There are only two sentences that have prefix "i " .
Operation: input(‘a’)
Output: []
Explanation:
There are no sentences that have prefix "i a" .
Operation: input(’#’)
Output: []
Explanation:
The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.
Note:
- The input sentence will always start with a letter and end with ‘#’, and only one blank space will exist between two words.
- The number of complete sentences that to be searched won’t exceed 100. The length of each sentence including those in the historical data won’t exceed 100.
- Please use double-quote instead of single-quote when you write test cases even for a character input.
- Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases . Please see here for more details.
- 设计 TicTacToe
- 设计 Exam Room， 也可以算是算法题吧，参考
https://leetcode.com/problems/exam-room/
（持续更新中）
感兴趣的可以看下 谷歌近期面经整理
