Zillow计算机科学面试真题

 Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the HitCounter class:

HitCounter() Initializes the object of the hit counter system.

void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.

int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

 

Example 1:

Input ["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"] [[], [1], [2], [3], [4], [300], [300], [301]] 

Output [null, null, null, null, 3, null, 4, 3] 

Explanation 
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1); // hit at timestamp 1. 
hitCounter.hit(2); // hit at timestamp 2. 
hitCounter.hit(3); // hit at timestamp 3. 
hitCounter.getHits(4); // get hits at timestamp 4, return 3. 
hitCounter.hit(300); // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3. 

 

Constraints:

1 <= timestamp <= 2 * 109

All the calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).

At most 300 calls will be made to hit and getHits.


Follow up: What if the number of hits per second could be huge? Does your design scale?

 We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined).  Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

 

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] 
Output: [[3,4]] 
Explanation: There are a total of three employees, and all common free time intervals would be [-inf, 1], [3, 4], [10, inf]. We discard any intervals that contain inf as they aren't finite. 

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] 
Output: [[5,6],[7,9]] 

 

Constraints:

1 <= schedule.length , schedule[i].length <= 50

0 <= schedule[i].start < schedule[i].end <= 10^8

Given API getRandChar, that will return a random char

 

Given target, write code to call getRandChar until you get exactly the order of characters in target.

 

Write your test case, how do you test?

 

/*

 

char getRandChar() = > 'x' 'd' 'o' 'l' 'c' 'k' 'd' 'o' 'c' 'k'

 

String target "dock"

 

*/

设计一个房屋推荐系统。 当用户登陆zillow主页后，需要在主页上显示 Top K Hot House, 这个Hot House的定义是你的Zillow好友收藏量。 比如你有5个好友: a,b,c,d,e。 它们都收藏了房子alpha, 那alpha就是这个用户第一个推荐的房子。

 

Follow Up: 朋友的朋友也算吗？ 权重是一样吗？

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

 

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.