勾勾店面

上来直接就做题了
给一个start number, 这时候系统会时不时的call一个generateNumber()函数，产生一个整数，要求Implement N

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

GenerateNumber() generate 5
Next() -> 7

djewssw 发表于 2020-7-25 02:50
没必要用map存interval，只要把当前的startNum和比startNum大的数存到一个set里面就行了。每次执行Next的时 ...

从startNum开始，如果startNum+1也在set里面，就把startNum删掉，并且startNum++。
这个地方startNum++一次就够了吗？要一直加到startnum + 1不在set里面才行把？举个例子，假设你现在的set里面是{4，6，7，8，9，10，。。。。10000}， 这时候startnum = 4，然后add的进了5， 你必须要把startNum一直调整到10000，然后才能输出10001. 这个调整的过程明显不是O(1)

建一个HashMap，key是startNumber和generateNumber()生成的数，value是以这个key为start/end point interval的长度。Everytime you get a new number by calling generateNumber()，check if number+1 and number-1 exist in the map，if not exist，map.put(number, 1)，otherwise this number connects neighboring intervals whose end points are number+1/number-1, you need to update the length of those intervals in the map. Always return startNumber + map.get(startNumber)。O(1) operation。


Example：

time 0: put start number 4 in the map, value is 1.
we have one interval [4,4] with length 1.
HashMap: [4 ->1]
return: 4+1

time 1: generateNumber() -> 2
Ignore 2 since it's smaller than start number 4.
HashMap: [4 ->1]
return: 4+1

time 2: generateNumber() -> 6
we have two intervals [4,4] and [6,6], both with length 1.
HashMap: [4 ->1, 6 ->1]
return: 4+1

time 3: generateNumber() -> 5
we need to insert 5 and update 4 and 6 since 5 connects intervals [4,4] and [6,6], we now have only one interval [4,5,6]
HashMap: [4 ->3, 5->1, 6 ->3]
return: 4+3

time 4: generateNumber() -> 7
we need to insert 7 and update 4 since 7 extends current interval [4,5,6] to [4,5,6,7]. No need to update 6 as it's no longer an end point of any interval.
HashMap: [4 ->4, 5->1, 6 ->3, 7->4]
return: 4+4

弟兄们，thoughts？

不就是union find吗，每次有新数字n，让n和n+1/n - 1 union起来， 然后看size[start number]

没看懂，有朋友帮忙解释下吗 地里之前没看过这题

同没看懂，隐藏部分还看不到。。。

感谢楼主分享题目。
我的想法是，用区间的形式把generate出现过的数字记录下来，存储在一个平衡搜索树的结构的map里（例如c++的map, Java的treemap）。（可以用key表示区间左端点，value表示右端点，要保证这些区间互相不overlap，也没有端点相邻）初始时只向map里存入[start number, start number]这个区间。然后每一次next都只要找最小键值的<key, value>，这样value+1就是要返回的数。这种做法的关键在于每一generate()之后要维护这个map，合并可能受到影响的区间，但总是能在log(Size)的时间里完成的。

coronaking2020 发表于 2020-7-24 22:08
建一个HashMap，key是startNumber和generateNumber()生成的数，value是以这个key为start/end point interva ...

hashmap 从 状态[4 ->1, 6 ->1]因为新来了5变成状态[4 ->3, 5->1, 6 ->3]这个过程, 前后两个key(4,6)对应的value具体是怎么更新的呀？这里有点没太看懂
in general, k加入， k-1 & k+1 分别存在，同时存在的三种情况下，怎么update 前后key的value，以及startNumber的value？

AlbertZhong 发表于 2020-7-24 19:11
感谢楼主分享题目。
我的想法是，用区间的形式把generate出现过的数字记录下来，存储在一个平衡搜索树的结 ...

我一开始也是这么想的，但是面试官说要O(1)

没必要用map存interval，只要把当前的startNum和比startNum大的数存到一个set里面就行了。每次执行Next的时候根据generatedNum去更新set和startNum，然后返回startNum+1。
例子：
startNum = 4, set = [4], next = 5
add: 2, can be igored, next = 5
add 6, startNum = 4, set = [4, 6], next = 5
add 5, startNum = 6, set = [6], next = 7。从startNum开始，如果startNum+1也在set里面，就把startNum删掉，并且startNum++。

操作都是O(1)，因为每个元素只进/出set 1次

djewssw 发表于 2020-7-25 02:50
没必要用map存interval，只要把当前的startNum和比startNum大的数存到一个set里面就行了。每次执行Next的时 ...

这个时间复杂度主要在处理startNum上，可能也不是O（1）？worst case可能要是O（size）size=setSize