谷歌之设计题 - 面经题目整理

1. 设计一个 Map class， 放进去的key value pair 有expiration，也就是ttl。接口是 get(key), put(key, value, ttl)
2. 设计一个 Timer class，这里有多个不同的版本或变种。一个就是schedule 一个 event，给一定的delay 时间，要求在delay 一定时间后trigger 该event，这里要涉及多线程概念。还有提供你一些辅助函数，比如 set_hw_timer 这种，认为调用该函数就会在一定时间后自动trigger event。大概是不断调用自己函数的写法，另外需要存放一个Heap。比如 狗家店面 新题！
3. 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

4. 设计 API Rate Limiter，参考
   https://leetcode.com/discuss/interview-question/124558/Implement-a-Rate-Limiter/

5. 设计系统来查询 Nearby Restaurants/Friends (a proximity server)

6. 设计 Web Crawler，参考
   https://leetcode.com/discuss/interview-question/124657/Design-a-distributed-web-crawler-that-will-crawl-all-the-pages-of-wikipedia/

7. 设计分布式缓存 - 基本就是一致性哈希解释一下

8. 设计 Load Balancer的数据结构，其实就是 leetcode 原题
   https://leetcode.com/problems/insert-delete-getrandom-o1
   https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed

9. 设计 key value store

10. 设计 Search Autocomplete System
    就是 leetcode 原题 https://leetcode.com/problems/design-search-autocomplete-system

11. 设计 TicTacToe
12. 设计 Exam Room， 也可以算是算法题吧，参考
    https://leetcode.com/problems/exam-room/

（持续更新中）

感兴趣的可以看下 谷歌近期面经整理

能不能透露一下Timer这题怎么解？

参考这篇文章

相关文档在这 （搜 Task Scheduler）

类似这个伪代码： set_hw_timer 负责多久后 trigger 这个function，即 run_task

相关帖子 狗家店面 新题！ - #2 by 999999

谢谢分享！

这题的requirement是：
按照startTime打印，但是能打印的条件是startTime在你之前的request都已经结束了

可以用两个数据结构

// processId -> finish time
Map<String, Long> finish = new HashMap<>();

Queue<Request> q = new PriorityQueue<>();

class Request implements Comparable<Request> {
   long startTime;
   String id;
   
   @Override   
   int compareTo(Request o) {
      return Long.compare(this.startTime, o.startTime);
   }
}

如果assume 我们的input是FIFO的，其实不需要PriorityQueue，直接 LinkedList即可（因为List的顺序就是按照startTime排好序的）

void start(String processId, long startTime) {
     q.add(new Request(processId, startTime));
}

void end(String processId, long endTime) {
    finish.put(processId, endTime);
    Request r = q.peek();
    // 如果不在q的开头，说明有其他没finish的request的startTime在前面
    if (!Objects.equals(r.id, processId)) {
        return;
    }
   
    // 这里碰到有没finish的就停止
    while (r != null && finish.get(r.id) != null) {
        print(r);
       finish.remove(r.id);
        r = q.peek();
    }
}

这题onsite 碰到的

There’re various APIs in an application, and for each API, we’re logging the “start-time” , and the “end-time” for that API execution. We’ve to output all “Slow API” or “Incomplete API” , in the application.

Here’re the definition for slow/incomplete api:
Slow API : execution-time is more than MAX_ALLOWED time. (endTime - startTime > MAX_ALLOWED)
Incomplete API : We do not have any end-time information for this API.

Example Input:
timestamp | API | event-type
1 login start
3 feed start
3 login end
5 trending start
6 profile start
6 feed end
11 trending end

and, MAX_ALLOWED execution-time = 5
NOTE: Input list of logs is sorted in increasing order, based on timestamp values.

Output:
Slow API:

1. trending

Incomplete API:

1. profile

** Follow-up:**
Can you write an implementation where, as soon as you find a slow/incomplete API, the program should return the API name?