由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Random Array number, Find longest consecutive sequence
相关主题
longest subarray with numbers arranged as a seq请教一道题
find longest subarray with the equal number of 0's, 1's讨论个subarray sum的变种问题
这个怎么弄?stable rearrange an integer array with + and -
liverampOA题目一道算法题,N*N array里最大的subarray
谁有兴趣做道题?[算法] unsorted array
G题讨论刚电面完,分享两个题目
one amazon interview problem问一个给定的array 和一个sum value,找最小sub-array,谢谢
一朋友被Google的电面干掉了 (转载)这题怎么做?
相关话题的讨论汇总
话题: array话题: find话题: sequence话题: interview话题: random
进入JobHunting版参与讨论
1 (共1页)
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
8
bless.
1 (共1页)
进入JobHunting版参与讨论
相关主题
这题怎么做?谁有兴趣做道题?
问几道算法题G题讨论
Question:Given a array,find out if there exist a subarray such its sum is zeroone amazon interview problem
问一道老题一朋友被Google的电面干掉了 (转载)
longest subarray with numbers arranged as a seq请教一道题
find longest subarray with the equal number of 0's, 1's讨论个subarray sum的变种问题
这个怎么弄?stable rearrange an integer array with + and -
liverampOA题目一道算法题,N*N array里最大的subarray
相关话题的讨论汇总
话题: array话题: find话题: sequence话题: interview话题: random