c*******r
发帖数: 309 | 1 Given an array of random numbers. Find the longest consecutive sequence.
For ex
Array 100 3 200 1 2 4
Ans 1 2 3 4
Array 101 2 3 104 5 103 9 102
Ans 101 102 103 104
Can we do it in one go on array using extra space??
我想到的方式是先sort， 然后用index来存,然后记录max长度. 不断更新新的index指
针.
不过据说复杂度要控制在o(n).
没什么好的想法啊 | c*****e
发帖数: 3226 | 2 版内问过了。翻翻 ，关键是-1
【在 c*******r 的大作中提到】
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 我想到的方式是先sort， 然后用index来存,然后记录max长度. 不断更新新的index指
: 针.
: 不过据说复杂度要控制在o(n).
| B*******1
发帖数: 2454 | 3 搜火鸡的帖子，还有code，用 disjoint set. | c**j
发帖数: 103 | 4 ding! Can we do it without sorting??
请问Bayesian1， 还有link没？
加个条件： 这个题如果还要要求 答案是*连续位置的*的subarray呢？
e.g.:
input: 4,5,1,5,7,4,3,6,3,1,9
sort以后1，1，3，3，4，4，5，5，6，7，9
output{5,7,4,3,6}
check careercup:
http://www.careercup.com/question?id=11256218
Microsoft Interview Question about Algorithm asm on October 19, 2011
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
39
http://www.careercup.com/question?id=11070934
http://www.careercup.com/question?id=11066909
Google Interview Question for SDE in tests about Arrays learner on October
06, 2011
Given an int array which might contain duplicates, find the largest subset
of it which form a sequence.
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time
32
[Full Interview Report]
Country: -
Interview Type: Phone Interview
Tags: Google » Arrays » SDE in test Question #11070934 (Report Dup) | Edit
| History | n*******w
发帖数: 687 | 5 Java写过disjoint set + 1个hashtable的版本。
发现hashtable没想象的快。理论上O（n）实际上慢。
【在 B*******1 的大作中提到】
: 搜火鸡的帖子，还有code，用 disjoint set.
| c**j
发帖数: 103 | 6 这是不是有点太复杂了。。。。
disjoint set 怎么实现啊？ 弄个linked list of set？
【在 n*******w 的大作中提到】
: Java写过disjoint set + 1个hashtable的版本。
: 发现hashtable没想象的快。理论上O（n）实际上慢。
| n*******w
发帖数: 687 | 7 O（n）的解，而且只扫一遍，不算复杂。
火鸡的代码比较短，容易懂。
http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid
【在 c**j 的大作中提到】
: 这是不是有点太复杂了。。。。
: disjoint set 怎么实现啊？ 弄个linked list of set？
| s********7
发帖数: 4681 | |
|
