O******i 发帖数: 269 | 1 面官后来反馈说,the best O(1) solution I know so far is to use a trie
真的能用trie达到O(1)么?如何实现?
*******************************************************************
给定一个大整数N,比如N = 100, 有如下的初始有序序列位于[0, N - 1]之间
[0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99]
请设计一个数据结构保存这个初始序列,然后写一个函数,接受一个input参数x, 满足
0 <= x <= N - 1
1) 假如x在该结构中不存在,出错处理
2) 假如x在该结构中存在,返回x之后第一个不存在的数,并把该数写入结构中
例如
x = 8, 出错,初始序列中没有8
x = 5, 返回7, 序列变为
[0 1] [4 5 6 7] [9 10 11] [20] [50] [90] [95 96] [98 99]
x = 4, 返回8, 序列变为
[0 1] [4 5 6 7 8] [9 10 11] [20] [50] [90] [95 96] [98 99]
x = 0, 返回2, 序列变为
[0 1 2] [4 5 6 7 8] [9 10 11] [20] [50] [90] [95 96] [98 99]
x = 95, 返回97,序列变为
[0 1 2] [4 5 6 7 8] [9 10 11] [20] [50] [90] [95 96 97 98 99]
x = 96, 出错,找不到合适的数
******************************
我当时用了bitmap (bit vector),说开一个保存0到N - 1的bt[N],每个bit初始化为0
, 读入初始序列,设置相应bit为1
假如bt[x]为0, 出错
假如bt[x]为1, 考察x + 1, x + 2, x + 3,..., 直到找到第一个不存在的数y,满足
bt[y] = 0, 然后返回y并且设置bt[y] = 1
面试完才发现这样效率不高,比如对原始序列,x = 4, 我要考察x = 5, x = 6, x = 7
, 直到返回7再次输入x = 4, 我又考察x = 5, x = 6, x = 7, x = 8, 返回8。其中x =
5, x = 6, x = 7 上次都考察过了,重复劳动
所以不幸被拒了,请大家帮忙想一个时间空间都最优的解法,神马线段树,skip list,
链表,hash + 链表, 区间合并都往上砸,直到砸出让面试官最满意的解法为止,多
谢。 | p*****2 发帖数: 21240 | | l*****a 发帖数: 14598 | 3 1)传说中的interval tree
2) ArrayList,binary search then insert/merge
【在 O******i 的大作中提到】 : 面官后来反馈说,the best O(1) solution I know so far is to use a trie : 真的能用trie达到O(1)么?如何实现? : ******************************************************************* : 给定一个大整数N,比如N = 100, 有如下的初始有序序列位于[0, N - 1]之间 : [0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99] : 请设计一个数据结构保存这个初始序列,然后写一个函数,接受一个input参数x, 满足 : 0 <= x <= N - 1 : 1) 假如x在该结构中不存在,出错处理 : 2) 假如x在该结构中存在,返回x之后第一个不存在的数,并把该数写入结构中 : 例如
| O******i 发帖数: 269 | 4 能给具体的方法么?
感觉我的Bitmap(bit vector)解法,只能保证最坏情形(也就是几乎所有的数都插入数
据结构中)的空间复杂度比普通Hash表更小,但查找下一个数还是O(N), 或许他想要二
分查找的O(logN), 或者还有更巧妙的空间换时间达到O(1), 类似那个栈O(1)找最小元
素?
可能线段或者区间的方法更好,这样连续区段,只需要保存两个端点就可以了,能够省
很多空间,类似合并区间题的思路。 | p*****2 发帖数: 21240 | 5
感觉你的方法不能scale。用TreeMap应该就可以了。interval tree我也不知道面试好
不好写。
【在 O******i 的大作中提到】 : 能给具体的方法么? : 感觉我的Bitmap(bit vector)解法,只能保证最坏情形(也就是几乎所有的数都插入数 : 据结构中)的空间复杂度比普通Hash表更小,但查找下一个数还是O(N), 或许他想要二 : 分查找的O(logN), 或者还有更巧妙的空间换时间达到O(1), 类似那个栈O(1)找最小元 : 素? : 可能线段或者区间的方法更好,这样连续区段,只需要保存两个端点就可以了,能够省 : 很多空间,类似合并区间题的思路。
| O******i 发帖数: 269 | 6 本来想可以化归到区间合并和二分查找的题
比如最初的数据
[0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99]
用区间表示就是
(0, 1) U (4, 6) U (9, 11) U (20, 20) U (50, 50) U (90, 90) U (95, 96) U
(98, 99)
输入x为12, 二分查找12,找不到在任何一个区间内,算出错
输入x为95, 二分查找在区间(95, 96), 返回97, 97使得区间(95, 96)扩展到(95, 97)
, 然后要和(98, 99)合并为大区间(95, 99)
问题在:
如果要支持二分查找,区间必须连续存放,不能用链表
假如用链表存放区间,又不能二分查找
比如用std::vector存区间,数据不断插入会导致区间扩展和合并,导致区间增加或者
减少,可在vector中间插入和删除一个区间是O(N)的呀,因为要移动别的元素。 | p*****2 发帖数: 21240 | 7
97)
用TreeMap就可以了。每种语言基本都有响应的数据结构。
【在 O******i 的大作中提到】 : 本来想可以化归到区间合并和二分查找的题 : 比如最初的数据 : [0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99] : 用区间表示就是 : (0, 1) U (4, 6) U (9, 11) U (20, 20) U (50, 50) U (90, 90) U (95, 96) U : (98, 99) : 输入x为12, 二分查找12,找不到在任何一个区间内,算出错 : 输入x为95, 二分查找在区间(95, 96), 返回97, 97使得区间(95, 96)扩展到(95, 97) : , 然后要和(98, 99)合并为大区间(95, 99) : 问题在:
| O******i 发帖数: 269 | 8 二爷的意思是用平衡的二叉排序树,比如AVL或者红黑,然后每个节点是一个线段(可以
用两个端点表示)么?
【在 p*****2 的大作中提到】 : : 97) : 用TreeMap就可以了。每种语言基本都有响应的数据结构。
| p*****2 发帖数: 21240 | 9
对,就是这个意思。
【在 O******i 的大作中提到】 : 二爷的意思是用平衡的二叉排序树,比如AVL或者红黑,然后每个节点是一个线段(可以 : 用两个端点表示)么?
| O******i 发帖数: 269 | 10 多谢,不过这题我之前没见过,未能在规定时间内想到,他也没有给太多提示。
其实Bitmap之前我就向面试官提到用BST, 不过我每个节点是一个数,所以查找是要O(N
* logN), 比Bitmap的O(N)还差,就自己轻易否决了。
有序数组要插入删除一个元素,操作是O(N), 但是对应的平衡BST, 插入删除一个元素
是O(logN),那么什么场合下有序数组比对应的平衡BST要好?
【在 p*****2 的大作中提到】 : : 对,就是这个意思。
| | | l*********8 发帖数: 4642 | 11 不需要在中间插入删除的时候。
(N
【在 O******i 的大作中提到】 : 多谢,不过这题我之前没见过,未能在规定时间内想到,他也没有给太多提示。 : 其实Bitmap之前我就向面试官提到用BST, 不过我每个节点是一个数,所以查找是要O(N : * logN), 比Bitmap的O(N)还差,就自己轻易否决了。 : 有序数组要插入删除一个元素,操作是O(N), 但是对应的平衡BST, 插入删除一个元素 : 是O(logN),那么什么场合下有序数组比对应的平衡BST要好?
| e****e 发帖数: 418 | 12 可以用ArrayList吧。
class Pair{
int low;
int high;
} | O******i 发帖数: 269 | 13 ArrayList如果用数组实现,中间插入删除困难
反之,如果用链表实现,无法二分查找
【在 e****e 的大作中提到】 : 可以用ArrayList吧。 : class Pair{ : int low; : int high; : }
| e****e 发帖数: 418 | 14 明白了,谢谢解释。这个题里面主要是删除吧。
【在 O******i 的大作中提到】 : ArrayList如果用数组实现,中间插入删除困难 : 反之,如果用链表实现,无法二分查找
| O******i 发帖数: 269 | 15 确实是只有删除了。
现在才知道这题应该这样分析才有冷静的思路
1) 读入初始数据后,就是正数轴上以非负整数为端点的一系列排序好且不相交的线段
,有些线段退化为单个的离散点
2) 给定的x, 必须位于某条线段上
3) 下一个数,就是扩展x所在线段(长度增加1)后新的右端点
4) 线段扩展后,填补了gap,可能导致两条相邻的线段合并为一条更长的线段
5) 如果我们用有序数组(每个元素是一个区间)表示这些线段,就是经典的合并区间那
道题,但是考虑到删除两个区间为一个区间会引起其他元素的O(N)移动,改用平衡BST,
可以把这个操作降为O(logN)
这道题的核心,一个是“以线代点", 另外一个是“以树代替数组”
可惜我明白的太晚了,虽然区间合并题和BST都知道,就是没有想到把这两个结合起来。
【在 e****e 的大作中提到】 : 明白了,谢谢解释。这个题里面主要是删除吧。
| J**9 发帖数: 835 | 16 Array of list?
Index DataPair-in-Array List
0 (0,1) ----------------> 0 -->1
1 (4,6) ----------------> 4 -->6
2 (9,11) ---------------> 9-->10-->11
Search: binary search to array, then traverse at most two lists
insert: update pair, insert into list.
【在 O******i 的大作中提到】 : 确实是只有删除了。 : 现在才知道这题应该这样分析才有冷静的思路 : 1) 读入初始数据后,就是正数轴上以非负整数为端点的一系列排序好且不相交的线段 : ,有些线段退化为单个的离散点 : 2) 给定的x, 必须位于某条线段上 : 3) 下一个数,就是扩展x所在线段(长度增加1)后新的右端点 : 4) 线段扩展后,填补了gap,可能导致两条相邻的线段合并为一条更长的线段 : 5) 如果我们用有序数组(每个元素是一个区间)表示这些线段,就是经典的合并区间那 : 道题,但是考虑到删除两个区间为一个区间会引起其他元素的O(N)移动,改用平衡BST, : 可以把这个操作降为O(logN)
| O******i 发帖数: 269 | 17 这题究竟有没有一种巧妙的空间换时间的方法,使得FindNext(int x)的操作是O(1),
包括返回符合要求的x之后的一个数,以及把这个数插入? | O******i 发帖数: 269 | 18 How to handle merge?
【在 J**9 的大作中提到】 : Array of list? : Index DataPair-in-Array List : 0 (0,1) ----------------> 0 -->1 : 1 (4,6) ----------------> 4 -->6 : 2 (9,11) ---------------> 9-->10-->11 : Search: binary search to array, then traverse at most two lists : insert: update pair, insert into list.
| e****e 发帖数: 418 | 19 我有一个用空间换时间的想法: hashtable + linked list
没有interval的东西,首先用Linked List存放所有的数,与此同时,用hashtable存储
所有的数,key是一个个的数,value是指向同一个数所在linked list的指针。
i.e [0 1] [4 5 6]
linked list: 0 ---> 1 ---> 4 ---> 5 ---> 6
/|\ /|\
| |
| |
hash table: 0, 1, ....
这样对于FindNext(int x)的操作,O(1)时间内通过hashtable可以知道x是否在[0, N -
1], 如果存在,就可以通过hashtable.getValue(int key)取得其指向在linked list
里的node, 从这个node开始,不断用node.next, 去找数值不是连续递增的node。找的
时候维护一个Prev指针,找到了
,通过Prev指针把新node加入linkd list.再把新增加的数和node放入hashtable. 整个
FindNext(int x)的操作,O(1)的时间。
【在 O******i 的大作中提到】 : 这题究竟有没有一种巧妙的空间换时间的方法,使得FindNext(int x)的操作是O(1), : 包括返回符合要求的x之后的一个数,以及把这个数插入?
| O******i 发帖数: 269 | 20 从这个node开始,找数值不连续的node。找的时候有一个Prev指针,这个我怎么觉得是
O(N)?
-
【在 e****e 的大作中提到】 : 我有一个用空间换时间的想法: hashtable + linked list : 没有interval的东西,首先用Linked List存放所有的数,与此同时,用hashtable存储 : 所有的数,key是一个个的数,value是指向同一个数所在linked list的指针。 : i.e [0 1] [4 5 6] : linked list: 0 ---> 1 ---> 4 ---> 5 ---> 6 : /|\ /|\ : | | : | | : hash table: 0, 1, .... : 这样对于FindNext(int x)的操作,O(1)时间内通过hashtable可以知道x是否在[0, N -
| | | l*********8 发帖数: 4642 | 21 "从这个node开始,找数值不连续的node"
-- 这不是O(1)吧
-
【在 e****e 的大作中提到】 : 我有一个用空间换时间的想法: hashtable + linked list : 没有interval的东西,首先用Linked List存放所有的数,与此同时,用hashtable存储 : 所有的数,key是一个个的数,value是指向同一个数所在linked list的指针。 : i.e [0 1] [4 5 6] : linked list: 0 ---> 1 ---> 4 ---> 5 ---> 6 : /|\ /|\ : | | : | | : hash table: 0, 1, .... : 这样对于FindNext(int x)的操作,O(1)时间内通过hashtable可以知道x是否在[0, N -
| e****e 发帖数: 418 | 22 Not sure. Looks like it should be sorted and the lower bound is O(lg(n))?
【在 O******i 的大作中提到】 : 从这个node开始,找数值不连续的node。找的时候有一个Prev指针,这个我怎么觉得是 : O(N)? : : -
| p*****2 发帖数: 21240 | 23
-
这种方法还是太浪费空间了吧?
【在 e****e 的大作中提到】 : 我有一个用空间换时间的想法: hashtable + linked list : 没有interval的东西,首先用Linked List存放所有的数,与此同时,用hashtable存储 : 所有的数,key是一个个的数,value是指向同一个数所在linked list的指针。 : i.e [0 1] [4 5 6] : linked list: 0 ---> 1 ---> 4 ---> 5 ---> 6 : /|\ /|\ : | | : | | : hash table: 0, 1, .... : 这样对于FindNext(int x)的操作,O(1)时间内通过hashtable可以知道x是否在[0, N -
| p*****2 发帖数: 21240 | 24
有人知道TreeMap higherKey的复杂度吗?如果是log(n)的话,那 TreeMap查找log(n),
合并就要n(logn)的复杂度了。那还不如ArrayList了。
ArrayList: search logn, insert n
LinkedList: search n, insert n
貌似ArrayList复杂度最好了。当然写起来更费劲些。今天有时间练练。
【在 O******i 的大作中提到】 : 这题究竟有没有一种巧妙的空间换时间的方法,使得FindNext(int x)的操作是O(1), : 包括返回符合要求的x之后的一个数,以及把这个数插入?
| p*****2 发帖数: 21240 | 25
),
我刚才想的是insert interval。LZ的题就一个数字的话TreeMap查找,合并就都是log(
n)了。这题的变化还可以很多呀。
【在 p*****2 的大作中提到】 : : 有人知道TreeMap higherKey的复杂度吗?如果是log(n)的话,那 TreeMap查找log(n), : 合并就要n(logn)的复杂度了。那还不如ArrayList了。 : ArrayList: search logn, insert n : LinkedList: search n, insert n : 貌似ArrayList复杂度最好了。当然写起来更费劲些。今天有时间练练。
| m******s 发帖数: 165 | 26 插入8时应该merge吧。。。
可以做到O(n)空间O(logn)时间,其中n是当前线段数<=N/2
【在 O******i 的大作中提到】 : 从这个node开始,找数值不连续的node。找的时候有一个Prev指针,这个我怎么觉得是 : O(N)? : : -
| O******i 发帖数: 269 | 27 面官反馈说,the best O(1) solution I know so far is to use a trie
真的能用trie达到O(1)么?如何实现? | p*****2 发帖数: 21240 | 28
哪个操作是O(1)?
【在 O******i 的大作中提到】 : 面官反馈说,the best O(1) solution I know so far is to use a trie : 真的能用trie达到O(1)么?如何实现?
| O******i 发帖数: 269 | 29 因为FindNextNumber(int x)方法要首先查找输入的x是否已经在数据结构中存在,如果
存在的话再去找到下一个不存在的值y,再把原先不存在的y值插入数据结构。
他说用trie可以让FindNextNumber(int x)达到O(1), 不清楚是真的可行还是他个人的
观点。
【在 p*****2 的大作中提到】 : : 哪个操作是O(1)?
| e*****r 发帖数: 93 | 30 从存在的最底层节点开始找右非空子树(不存在的节点也被认为是非空子树) 时间复
杂度是该数数位 可以被认为是常数 但其实是log_10(N) 渐进复杂度还是O(logN)
【在 O******i 的大作中提到】 : 因为FindNextNumber(int x)方法要首先查找输入的x是否已经在数据结构中存在,如果 : 存在的话再去找到下一个不存在的值y,再把原先不存在的y值插入数据结构。 : 他说用trie可以让FindNextNumber(int x)达到O(1), 不清楚是真的可行还是他个人的 : 观点。
| | | p*****2 发帖数: 21240 | 31
一般来说tree都是logn的复杂度。
【在 e*****r 的大作中提到】 : 从存在的最底层节点开始找右非空子树(不存在的节点也被认为是非空子树) 时间复 : 杂度是该数数位 可以被认为是常数 但其实是log_10(N) 渐进复杂度还是O(logN)
| d*****9 发帖数: 90 | 32 class TrieTable
{
private List lastNodes = new List();
private Node[] table = new Node[100];
public TrieTable( List input )
{
foreach (int[] array in input)
{
LastNode lastNode = new LastNode(array[array.Length - 1] + 1
);
lastNodes.Add(lastNode);
foreach (int i in array)
{
table[array[i]] = new Node(lastNode);
}
}
}
public int? insert(int val)
{
if (table[val] != null)
{
LastNode lastNode = table[val].Node;
int lastVal = lastNode.Value;
lastNode.Value++;
table[lastVal] = new Node(lastNode);
if (table[lastVal + 1] != null)
{
lastNode = table[lastVal + 1].Node;
}
return lastVal;
}
return null;
}
}
class Node
{
public Node ( LastNode lastNode )
{
this.Node = lastNode;
}
public LastNode Node { get; set; }
}
class LastNode
{
public LastNode ( int val )
{
this.Value = val;
}
public int Value { get; set; }
} | d*****9 发帖数: 90 | | c**x 发帖数: 492 | 34 有一点不太明白,既然合并后
[0 1 2] [4 5 6 7 8] [9 10 11] [20] [50] [90] [95 96 97 98 99]
最后的查询
x = 96, 出错,找不到合适的数
x=96 不是在最后一个区域里吗?
也许我想的不对
【在 O******i 的大作中提到】 : 面官后来反馈说,the best O(1) solution I know so far is to use a trie : 真的能用trie达到O(1)么?如何实现? : ******************************************************************* : 给定一个大整数N,比如N = 100, 有如下的初始有序序列位于[0, N - 1]之间 : [0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99] : 请设计一个数据结构保存这个初始序列,然后写一个函数,接受一个input参数x, 满足 : 0 <= x <= N - 1 : 1) 假如x在该结构中不存在,出错处理 : 2) 假如x在该结构中存在,返回x之后第一个不存在的数,并把该数写入结构中 : 例如
| z****c 发帖数: 602 | 35 可以用长度为N的数组来存吧。对于某区间[k...k+t]
N[k]=k+t, N[k+1]=k, N[k+2]=k...N[k+t]=k,其他都存-1。不过这个要求区间连续,题
里是要求连续吧? |
|