求教一道软家面试题的最优解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求教一道软家面试题的最优解

求教一道软家面试题的最优解# JobHunting - 待字闺中

O*i2012-12-19 08:12

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*22012-12-19 08:12

2 楼

感觉数组就可以了。

l*a2012-12-19 08:12

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*i2012-12-19 08:12

4 楼

能给具体的方法么？
感觉我的Bitmap(bit vector)解法，只能保证最坏情形(也就是几乎所有的数都插入数
据结构中)的空间复杂度比普通Hash表更小，但查找下一个数还是O(N), 或许他想要二
分查找的O(logN), 或者还有更巧妙的空间换时间达到O(1), 类似那个栈O(1)找最小元
素？
可能线段或者区间的方法更好，这样连续区段，只需要保存两个端点就可以了，能够省
很多空间，类似合并区间题的思路。

p*22012-12-19 08:12

5 楼

感觉你的方法不能scale。用TreeMap应该就可以了。interval tree我也不知道面试好
不好写。

【在 O******i 的大作中提到】

: 能给具体的方法么？
: 感觉我的Bitmap(bit vector)解法，只能保证最坏情形(也就是几乎所有的数都插入数
: 据结构中)的空间复杂度比普通Hash表更小，但查找下一个数还是O(N), 或许他想要二
: 分查找的O(logN), 或者还有更巧妙的空间换时间达到O(1), 类似那个栈O(1)找最小元
: 素？
: 可能线段或者区间的方法更好，这样连续区段，只需要保存两个端点就可以了，能够省
: 很多空间，类似合并区间题的思路。

O*i2012-12-19 08:12

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*22012-12-19 08:12

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*i2012-12-19 08:12

8 楼

二爷的意思是用平衡的二叉排序树，比如AVL或者红黑，然后每个节点是一个线段(可以
用两个端点表示)么？

【在 p*****2 的大作中提到】

:
: 97)
: 用TreeMap就可以了。每种语言基本都有响应的数据结构。

p*22012-12-19 08:12

9 楼

对，就是这个意思。

【在 O******i 的大作中提到】

: 二爷的意思是用平衡的二叉排序树，比如AVL或者红黑，然后每个节点是一个线段(可以
: 用两个端点表示)么？

O*i2012-12-19 08:12

10 楼

多谢，不过这题我之前没见过，未能在规定时间内想到，他也没有给太多提示。
其实Bitmap之前我就向面试官提到用BST, 不过我每个节点是一个数，所以查找是要O(N
* logN), 比Bitmap的O(N)还差，就自己轻易否决了。
有序数组要插入删除一个元素，操作是O(N), 但是对应的平衡BST, 插入删除一个元素
是O(logN)，那么什么场合下有序数组比对应的平衡BST要好？

【在 p*****2 的大作中提到】

:
: 对，就是这个意思。

l*82012-12-19 08:12

11 楼

不需要在中间插入删除的时候。

(N

【在 O******i 的大作中提到】

: 多谢，不过这题我之前没见过，未能在规定时间内想到，他也没有给太多提示。
: 其实Bitmap之前我就向面试官提到用BST, 不过我每个节点是一个数，所以查找是要O(N
: * logN), 比Bitmap的O(N)还差，就自己轻易否决了。
: 有序数组要插入删除一个元素，操作是O(N), 但是对应的平衡BST, 插入删除一个元素
: 是O(logN)，那么什么场合下有序数组比对应的平衡BST要好？

e*e2012-12-19 08:12

12 楼

可以用ArrayList吧。
class Pair{
int low;
int high;
}

O*i2012-12-19 08:12

13 楼

ArrayList如果用数组实现，中间插入删除困难
反之，如果用链表实现，无法二分查找

【在 e****e 的大作中提到】

: 可以用ArrayList吧。
: class Pair{
: int low;
: int high;
: }

e*e2012-12-19 08:12

14 楼

明白了，谢谢解释。这个题里面主要是删除吧。

【在 O******i 的大作中提到】

: ArrayList如果用数组实现，中间插入删除困难
: 反之，如果用链表实现，无法二分查找

O*i2012-12-19 08:12

15 楼

确实是只有删除了。
现在才知道这题应该这样分析才有冷静的思路
1) 读入初始数据后，就是正数轴上以非负整数为端点的一系列排序好且不相交的线段
，有些线段退化为单个的离散点
2) 给定的x, 必须位于某条线段上
3) 下一个数，就是扩展x所在线段(长度增加1）后新的右端点
4) 线段扩展后，填补了gap,可能导致两条相邻的线段合并为一条更长的线段
5) 如果我们用有序数组(每个元素是一个区间)表示这些线段，就是经典的合并区间那
道题，但是考虑到删除两个区间为一个区间会引起其他元素的O(N)移动，改用平衡BST,
可以把这个操作降为O(logN)
这道题的核心，一个是“以线代点", 另外一个是“以树代替数组”
可惜我明白的太晚了，虽然区间合并题和BST都知道，就是没有想到把这两个结合起来。

【在 e****e 的大作中提到】

: 明白了，谢谢解释。这个题里面主要是删除吧。

J*92012-12-19 08:12

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*i2012-12-19 08:12

17 楼

这题究竟有没有一种巧妙的空间换时间的方法，使得FindNext(int x)的操作是O(1),
包括返回符合要求的x之后的一个数，以及把这个数插入？

O*i2012-12-19 08:12

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*e2012-12-19 08:12

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*i2012-12-19 08:12

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*82012-12-19 08:12

21 楼

"从这个node开始，找数值不连续的node"
-- 这不是O(1)吧

-

【在 e****e 的大作中提到】

e*e2012-12-19 08:12

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*22012-12-19 08:12

23 楼

-
这种方法还是太浪费空间了吧？

【在 e****e 的大作中提到】

p*22012-12-19 08:12

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*22012-12-19 08:12

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*s2012-12-19 08:12

26 楼

插入8时应该merge吧。。。
可以做到O(n)空间O(logn)时间，其中n是当前线段数<=N/2

【在 O******i 的大作中提到】

: 从这个node开始，找数值不连续的node。找的时候有一个Prev指针，这个我怎么觉得是
: O(N)？
:
: -

O*i2012-12-19 08:12

27 楼

面官反馈说，the best O(1) solution I know so far is to use a trie
真的能用trie达到O(1)么？如何实现？

p*22012-12-19 08:12

28 楼

哪个操作是O(1)?

【在 O******i 的大作中提到】

: 面官反馈说，the best O(1) solution I know so far is to use a trie
: 真的能用trie达到O(1)么？如何实现？

O*i2012-12-19 08:12

29 楼

因为FindNextNumber(int x)方法要首先查找输入的x是否已经在数据结构中存在，如果
存在的话再去找到下一个不存在的值y,再把原先不存在的y值插入数据结构。
他说用trie可以让FindNextNumber(int x)达到O(1), 不清楚是真的可行还是他个人的
观点。

【在 p*****2 的大作中提到】

:
: 哪个操作是O(1)?

e*r2012-12-19 08:12

30 楼

从存在的最底层节点开始找右非空子树（不存在的节点也被认为是非空子树）时间复
杂度是该数数位可以被认为是常数但其实是log_10(N) 渐进复杂度还是O(logN)

【在 O******i 的大作中提到】

: 因为FindNextNumber(int x)方法要首先查找输入的x是否已经在数据结构中存在，如果
: 存在的话再去找到下一个不存在的值y,再把原先不存在的y值插入数据结构。
: 他说用trie可以让FindNextNumber(int x)达到O(1), 不清楚是真的可行还是他个人的
: 观点。

p*22012-12-19 08:12

31 楼

一般来说tree都是logn的复杂度。

【在 e*****r 的大作中提到】

: 从存在的最底层节点开始找右非空子树（不存在的节点也被认为是非空子树）时间复
: 杂度是该数数位可以被认为是常数但其实是log_10(N) 渐进复杂度还是O(logN)

d*92012-12-19 08:12

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*92012-12-19 08:12

33 楼

不知道这是不是 O(1) 的解法