有些面试题是够扯蛋的 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 有些面试题是够扯蛋的

相关主题
● 请教个面试题	● LeetCode 的 4 sum 问题如何用hash table做呢？
● 面试题求解：remove first duplicate number from an array	● 4sum o(n^2)超时
● A家面试题	● Java 面试关于map 和set
● 两个Amazon面试题	● HashTable space complexity?
● 分享面试题	● 问个Java的HashSet.contains的问题
● 问道面试题	● 问一个G家面试题
● subset	● Linked电面分享，挺好的题应该已挂
● 问个关于排序的面试题	● Facebook Hacker Cup

相关话题的讨论汇总
话题: int话题: integer话题: used话题: max话题: hashmap

进入JobHunting版参与讨论

(共1页)

P***t
发帖数: 1006

譬如这道LEETCODE上的题：
Longest Consecutive SequenceFeb 14
Given an unsorted array of integers, find the length of the longest
consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length
Your algorithm should run in O(n) complexity.
我是想了半天也想不出O(N)的解法怎么搞。网上一搜，发现原来是用HASHMAP做 Range
Merge. 尼玛，HASHMAP　insert来insert去的效率能有多高？这个表面上O(n)的解法
实际效率其实比简单的SORT差，更不要说CODE的复杂度了。实际解决问题的时候没有人
会这样去写的。

p*****2
发帖数: 21240

用个hashset吧？我觉得O(n)比nlogn要快呀。

P***t
发帖数: 1006

Hashset? 怎么搞？Logn 基本看做常数了，大小不同而已。

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

: 用个hashset吧？我觉得O(n)比nlogn要快呀。

p*****2
发帖数: 21240

http://blog.sina.com.cn/s/blog_b9285de20101iqar.html

【在 P***t 的大作中提到】

: Hashset? 怎么搞？Logn 基本看做常数了，大小不同而已。

P***t
发帖数: 1006

正好写了个Program比较了一下，再加上你的HASHSET:
Sort used time (ms): 1182
HashMap Used time (ms): 2959
HashSet Used time (ms): 3583
import java.io.Console;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
public class LongestConsecSequence {
public int longestConsecutive(int[] a) {
return v1(a);
}
public int v1(int[] in) {
int[] a = new int[in.length];
System.arraycopy(in, 0, a, 0, in.length);
if (a.length == 0)
return 0;
Arrays.sort(a);
int ret = 1;
int start = 0;
int dup = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] == a[i - 1] + 1) {
ret = Math.max(ret, i - start - dup + 1);
} else if (a[i] == a[i - 1]) {
dup += 1;
} else {
start = i;
dup = 0;
}
}
return ret;
}
public int v2(int[] a) {
HashMap map = new HashMap();
int max = 1;
for (int i : a) {
if (map.containsKey(i))
continue;
map.put(i, 1);
if (map.containsKey(i - 1)) {
max = Math.max(max, merge(map, i - 1, i));
}
if (map.containsKey(i + 1)) {
max = Math.max(max, merge(map, i, i + 1));
}
}
return max;
}
private int merge(HashMap map, int left, int right) {
int upper = right + map.get(right) - 1;
int lower = left - map.get(left) + 1;
int len = upper - lower + 1;
map.put(upper, len);
map.put(lower, len);
return len;
}
public int v3(int[] num) {
Set hs = new HashSet();
for (int v : num)
hs.add(v);
int ans = 0;
for (int v : num)
if (hs.contains(v))
ans = Math.max(ans, getCount(hs, v, false) + getCount(hs, v + 1,
true));
return ans;
}
int getCount(Set hs, int v, boolean asc) {
int count = 0;
while (hs.contains(v)) {
hs.remove(v);
count++;
if (asc)
v++;
else
v--;
}
return count;
}
public static void Run() {
LongestConsecSequence sol = new LongestConsecSequence();
int MAX_RANDOM = 327670;
int[][] ar = new int[100][100000];
for (int i = 0; i < ar.length; i++) {
for (int j = 0; j < ar[i].length; j++) {
ar[i][j] = (int) (Math.random() * MAX_RANDOM);
}
}
long milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
sol.v1(ar[i]);
}
long used = System.currentTimeMillis() - milli;
System.out.println("Sort used time (ms): " + used);
milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
sol.v2(ar[i]);
}
used = System.currentTimeMillis() - milli;
System.out.println("HashMap Used time (ms): " + used);
milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
sol.v3(ar[i]);
}
used = System.currentTimeMillis() - milli;
System.out.println("HashSet Used time (ms): " + used);
}
}

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

:
: http://blog.sina.com.cn/s/blog_b9285de20101iqar.html

p*****2
发帖数: 21240

你用Leetcode的OJ试试

【在 P***t 的大作中提到】

: 正好写了个Program比较了一下，再加上你的HASHSET:
: Sort used time (ms): 1182
: HashMap Used time (ms): 2959
: HashSet Used time (ms): 3583
: import java.io.Console;
: import java.util.Arrays;
: import java.util.HashMap;
: import java.util.HashSet;
: import java.util.Set;
: public class LongestConsecSequence {

P***t
发帖数: 1006

三个都通过。

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

:
: 你用Leetcode的OJ试试

s********x
发帖数: 914

Set hs=new HashSet();
这个initialize 设定size为num.length应该更优化?

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

:
: 你用Leetcode的OJ试试

P***t
发帖数: 1006

好一点：
Sort used time (ms): 1145
HashMap Used time (ms): 2973
HashSet Used time (ms): 3030

【在 s********x 的大作中提到】

: Set hs=new HashSet();
: 这个initialize 设定size为num.length应该更优化?

q****x
发帖数: 7404

大牛来了。

length
Range

【在 P***t 的大作中提到】

: 譬如这道LEETCODE上的题：
: Longest Consecutive SequenceFeb 14
: Given an unsorted array of integers, find the length of the longest
: consecutive elements sequence.
: For example,
: Given [100, 4, 200, 1, 3, 2],
: The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length
: Your algorithm should run in O(n) complexity.
: 我是想了半天也想不出O(N)的解法怎么搞。网上一搜，发现原来是用HASHMAP做 Range
: Merge. 尼玛，HASHMAP　insert来insert去的效率能有多高？这个表面上O(n)的解法

相关主题
● 问道面试题	● LeetCode 的 4 sum 问题如何用hash table做呢？
● subset	● 4sum o(n^2)超时
● 问个关于排序的面试题	● Java 面试关于map 和set
进入JobHunting版参与讨论

s********x
发帖数: 914

可不可以不要sequential run
第三个正好hit garbage collection 不fair啊

【在 P***t 的大作中提到】

s********x
发帖数: 914

你干脆把v2和v3都intialiaze using 2*num.length 试试好了 :)

【在 P***t 的大作中提到】

: 好一点：
: Sort used time (ms): 1145
: HashMap Used time (ms): 2973
: HashSet Used time (ms): 3030

s********x
发帖数: 914

你这样是不fair的
v1 creates a lot of objects
v2 and v3 might hit garbage collection when running.
So you should run each of them standalone

【在 s********x 的大作中提到】

: 可不可以不要sequential run
: 第三个正好hit garbage collection 不fair啊

P***t
发帖数: 1006

It doesn't matter. Trust me. I tried.

【在 s********x 的大作中提到】

: 你这样是不fair的
: v1 creates a lot of objects
: v2 and v3 might hit garbage collection when running.
: So you should run each of them standalone

s********x
发帖数: 914

这个有意思
v1理论上是（nlog(n) + n）* T1 这个constant T1 不需要hash的operation，肯定要
小些
v1完全可以优化更多。
首先把array inplace quick sort，这样就是ordered
然后search的时候完全不用linear time
贴一下哈（不知道v2和v3可否用这种思路）
// find longest increasing continuous sequence, better than O(n). a is
sorted already
public static int findLongestIncreasingContinuousSequence(int[] a) {
if (a == null || a.length == 0)
return 0;
int max = 1;
int end = 0;
// len = j - i + 1
int i = 0, k = 0;
while (i < a.length - max) {
int j = i + max; // a[i] to a[j], length of max+1
// k is where scanner stops, scanner scans from j to k since a[k
] to
// a[j] is increasing
if (j < a.length && a[j] - a[i] >= max) { // potential
increasing array
int scanner = j;
while ((scanner - 1) >= 0 && a[scanner] > a[scanner - 1]) //
** boundary check!
scanner--;
if (scanner == k) {
// found new max
while (((j + 1) < a.length) && a[j + 1] > a[j]) // **
boundary check!
j++;
max = j - i + 1;
end = j;
i = j + 1;
k = i;
} else { // a[scanner] to a[j] is increasing
i = scanner;
k = j;
}
} else {
i = j + 1;
k = i;
}
}
System.out.println("max is " + max + "; end is " + end);
return max;
}

【在 P***t 的大作中提到】

p*****2
发帖数: 21240

这是我的测试结果
Sort used time (ms): 4573
HashMap Used time (ms): 1683
HashSet Used time (ms): 2327

P***t
发帖数: 1006

神了。Did you change MAX_RANDOM and the array length?

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

: 这是我的测试结果
: Sort used time (ms): 4573
: HashMap Used time (ms): 1683
: HashSet Used time (ms): 2327

s********x
发帖数: 914

HashSet Used time (ms): 1994
HashMap Used time (ms): 1577
Sort used time (ms): 1084
我测了

【在 P***t 的大作中提到】

: 神了。Did you change MAX_RANDOM and the array length?

p*****2
发帖数: 21240

你一个用int，其他两个用Integer。int本来就快。

【在 P***t 的大作中提到】

: 神了。Did you change MAX_RANDOM and the array length?

s********x
发帖数: 914

autoboxing 本身就是performance考虑的因素啊。
lz完全说得对，v2和v3在memory space不占优势，running time又是不行。
v1不需要additional memory。
我看是v1胜了

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

:
: 你一个用int，其他两个用Integer。int本来就快。

相关主题
● HashTable space complexity?	● Linked电面分享，挺好的题应该已挂
● 问个Java的HashSet.contains的问题	● Facebook Hacker Cup
● 问一个G家面试题	● a[i] + b[j] = c[k] 的题有靠谱的答案不?
进入JobHunting版参与讨论

p*****2
发帖数: 21240

你没考虑worst case。

【在 s********x 的大作中提到】

: autoboxing 本身就是performance考虑的因素啊。
: lz完全说得对，v2和v3在memory space不占优势，running time又是不行。
: v1不需要additional memory。
: 我看是v1胜了

P***t
发帖数: 1006

差不多。只有在MAX_RANDOM < ARRAY LENGTH，出现很多重复数的话，Hash会消除重复
，所以有可能更快。

【在 s********x 的大作中提到】

: HashSet Used time (ms): 1994
: HashMap Used time (ms): 1577
: Sort used time (ms): 1084
: 我测了

s********x
发帖数: 914

v1的bottle neck是quick sort inplace， worst case 也是nlog(n)
跟average case是一样的

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

:
: 你没考虑worst case。

p*****2
发帖数: 21240

你把int改成Integer试试。

【在 P***t 的大作中提到】

: 差不多。只有在MAX_RANDOM < ARRAY LENGTH，出现很多重复数的话，Hash会消除重复
: ，所以有可能更快。

p*****2
发帖数: 21240

worst case 也是nlog(n)
are you really sure?

【在 s********x 的大作中提到】

: v1的bottle neck是quick sort inplace， worst case 也是nlog(n)
: 跟average case是一样的

s********x
发帖数: 914

你可以create temporary array which kicks out duplicates，然后quick sort吧

【在 P***t 的大作中提到】

: 差不多。只有在MAX_RANDOM < ARRAY LENGTH，出现很多重复数的话，Hash会消除重复
: ，所以有可能更快。

s********x
发帖数: 914

median of three 我记得是可以avoid 一边倒的把

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

:
: worst case 也是nlog(n)
: are you really sure?

p*****2
发帖数: 21240

这个不知道。但是Java比赛经常quicksort 碰到worst case fail掉。至少Java的
implementation是N^2的worst

【在 s********x 的大作中提到】

: median of three 我记得是可以avoid 一边倒的把

P***t
发帖数: 1006

Good point. If I had to do this in V1:
Integer[] a = new Integer[in.length];
for (int i = 0; i < in.length; i++) {
a[i] = in[i];
}
Then including the copying time, performance is similar:
Sort used time (ms): 2818
HashMap Used time (ms): 2929
HashSet Used time (ms): 3134
But then again, if input is int[], why would I even bother converting it to
Integer[]? :)

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

:
: 这个不知道。但是Java比赛经常quicksort 碰到worst case fail掉。至少Java的
: implementation是N^2的worst

s********x
发帖数: 914

N^2是因为pivot的选错，median of three已经solve这个问题了，我无法想象如何还能
到N^2 in any case using median of three

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

:
: 这个不知道。但是Java比赛经常quicksort 碰到worst case fail掉。至少Java的
: implementation是N^2的worst

相关主题
● 贡献一道面试题	● 面试题求解：remove first duplicate number from an array
● 请教一个常见的面试题的答案	● A家面试题
● 请教个面试题	● 两个Amazon面试题
进入JobHunting版参与讨论

p*****2
发帖数: 21240

to
因为我们应该是做算法的比较。要公平的比较才对。

【在 P***t 的大作中提到】

: Good point. If I had to do this in V1:
: Integer[] a = new Integer[in.length];
: for (int i = 0; i < in.length; i++) {
: a[i] = in[i];
: }
: Then including the copying time, performance is similar:
: Sort used time (ms): 2818
: HashMap Used time (ms): 2929
: HashSet Used time (ms): 3134
: But then again, if input is int[], why would I even bother converting it to

p*****2
发帖数: 21240

我觉得下边的代码更公平一些。
Sort used time (ms): 4657
HashMap Used time (ms): 1696
HashSet Used time (ms): 2433
public class test {
public int v1(Integer[] in) {
Integer[] a = new Integer[in.length];
System.arraycopy(in, 0, a, 0, in.length);
if (a.length == 0)
return 0;
Arrays.sort(a);
int ret = 1;
int start = 0;
int dup = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] == a[i - 1] + 1) {
ret = Math.max(ret, i - start - dup + 1);
} else if (a[i] == a[i - 1]) {
dup += 1;
} else {
start = i;
dup = 0;
}
}
return ret;
}
public int v2(Integer[] a) {
HashMap map = new HashMap();
int max = 1;
for (int i : a) {
if (map.containsKey(i))
continue;
map.put(i, 1);
if (map.containsKey(i - 1)) {
max = Math.max(max, merge(map, i - 1, i));
}
if (map.containsKey(i + 1)) {
max = Math.max(max, merge(map, i, i + 1));
}
}
return max;
}
private int merge(HashMap map, int left, int right) {
int upper = right + map.get(right) - 1;
int lower = left - map.get(left) + 1;
int len = upper - lower + 1;
map.put(upper, len);
map.put(lower, len);
return len;
}
public int v3(Integer[] num) {
Set hs = new HashSet(Arrays.asList(num));
int ans = 0;
for (int v : num)
if (hs.contains(v))
ans = Math.max(ans, getCount(hs, v, false) + getCount(hs, v + 1,
true));
return ans;
}
int getCount(Set hs, int v, boolean asc) {
int count = 0;
while (hs.contains(v)) {
hs.remove(v);
count++;
if (asc)
v++;
else
v--;
}
return count;
}
public void run() {
Integer MAX_RANDOM = 327670;
Integer[][] ar = new Integer[1][10000000];
Random rand=new Random();
for (int i = 0; i < ar.length; i++) {
for (int j = 0; j < ar[i].length; j++) {
ar[i][j] = rand.nextInt()%MAX_RANDOM;
}
}
long milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
v1(ar[i]);
}
long used = System.currentTimeMillis() - milli;
System.out.println("Sort used time (ms): " + used);
milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
v2(ar[i]);
}
used = System.currentTimeMillis() - milli;
System.out.println("HashMap Used time (ms): " + used);
milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
v3(ar[i]);
}
used = System.currentTimeMillis() - milli;
System.out.println("HashSet Used time (ms): " + used);
}

public static void main(String[] args) throws Exception
{
new test().run();
}
}

s********x
发帖数: 914

另外说一下quicksort本身能handle duplicate，用three way partition就可以了。
另外可以用temporary array 去踢掉duplicate。
我还是觉得lz是对的，v1不管怎么看都更好。

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

: 我觉得下边的代码更公平一些。
: Sort used time (ms): 4657
: HashMap Used time (ms): 1696
: HashSet Used time (ms): 2433
: public class test {
: public int v1(Integer[] in) {
: Integer[] a = new Integer[in.length];
: System.arraycopy(in, 0, a, 0, in.length);
: if (a.length == 0)
: return 0;

p*****2
发帖数: 21240

关键不是O(n)呀。面试就是面试，不是工作，不是做OJ。面试就要按照面试的要求去做
。这题一点也不过分。更过分的题目多了去了

【在 s********x 的大作中提到】

: 另外说一下quicksort本身能handle duplicate，用three way partition就可以了。
: 另外可以用temporary array 去踢掉duplicate。
: 我还是觉得lz是对的，v1不管怎么看都更好。

s********x
发帖数: 914

可能java自带的quicksort不够强？
怎么说也该考虑median of three，已经three way partition来handle duplicate吧
如果你指的是Array.Sort,可能都不是implemented in quicksort。因为quicksort不
是stable的。
http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html
(For example, the algorithm used by sort(Object[]) does not have to be a
mergesort, but it does have to be stable.)

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

:
: 关键不是O(n)呀。面试就是面试，不是工作，不是做OJ。面试就要按照面试的要求去做
: 。这题一点也不过分。更过分的题目多了去了

s********x
发帖数: 914

但这个感觉是面试官纸上谈兵，自己搞错了。
莫名其妙的优化，其实make it worse
感觉这个面试题就是面试官自己没想明白而已

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

:
: 关键不是O(n)呀。面试就是面试，不是工作，不是做OJ。面试就要按照面试的要求去做
: 。这题一点也不过分。更过分的题目多了去了

p*****2
发帖数: 21240

The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and
M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and
Experience, Vol. 23(11) P. 1249-1265 (November 1993).

【在 s********x 的大作中提到】

: 可能java自带的quicksort不够强？
: 怎么说也该考虑median of three，已经three way partition来handle duplicate吧
: 如果你指的是Array.Sort,可能都不是implemented in quicksort。因为quicksort不
: 是stable的。
: http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html
: (For example, the algorithm used by sort(Object[]) does not have to be a
: mergesort, but it does have to be stable.)

p*****2
发帖数: 21240

这个难说。面试本来复杂度就是做理论上的分析。人家要求O(n)你就得按照O(n)想吧？

【在 s********x 的大作中提到】

: 但这个感觉是面试官纸上谈兵，自己搞错了。
: 莫名其妙的优化，其实make it worse
: 感觉这个面试题就是面试官自己没想明白而已

s********x
发帖数: 914

其实想想用merge sort不是更简单，然后merge的时候直接把duplicate 给去掉呵呵

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

:
: 这个难说。面试本来复杂度就是做理论上的分析。人家要求O(n)你就得按照O(n)想吧？

p*****2
发帖数: 21240

也不是O(n)吧？

【在 s********x 的大作中提到】

: 其实想想用merge sort不是更简单，然后merge的时候直接把duplicate 给去掉呵呵

相关主题
● 两个Amazon面试题	● subset
● 分享面试题	● 问个关于排序的面试题
● 问道面试题	● LeetCode 的 4 sum 问题如何用hash table做呢？
进入JobHunting版参与讨论

p*****2
发帖数: 21240

我又试了一下，就算直接操作输入数组不copy，也没见solution1快呀
Sort used time (ms): 4580
HashMap Used time (ms): 851
HashSet Used time (ms): 1598

s********x
发帖数: 914

哦，当然不是。
偶最开始没看到要handle duplicate，后来才意识到。现在再想想既然这样要sort还不
如merge sort，呵呵。
这题确实说明要考虑constant time，那个hashtable和autoboxing都是make constant
time worse的。所以overrall 谁更快还不一定，let alone space。

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

: 我又试了一下，就算直接操作输入数组不copy，也没见solution1快呀
: Sort used time (ms): 4580
: HashMap Used time (ms): 851
: HashSet Used time (ms): 1598

s********x
发帖数: 914

你的电脑也太神了吧，连你的算法都无偿支持啊：）
我觉得别人测大部分都是v1快的，呵呵

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

: 我又试了一下，就算直接操作输入数组不copy，也没见solution1快呀
: Sort used time (ms): 4580
: HashMap Used time (ms): 851
: HashSet Used time (ms): 1598

p*****2
发帖数: 21240

constant
如果输入本身就是Integer呢？
很多语言并没有int Integer之分其实。
我们现在比较算法就应该用同样的data type。不然你一个用primitive一个用class那
算咋回事呢？

【在 s********x 的大作中提到】

: 哦，当然不是。
: 偶最开始没看到要handle duplicate，后来才意识到。现在再想想既然这样要sort还不
: 如merge sort，呵呵。
: 这题确实说明要考虑constant time，那个hashtable和autoboxing都是make constant
: time worse的。所以overrall 谁更快还不一定，let alone space。

p*****2
发帖数: 21240

代码都给你。你跑一个看看。
import java.io.Console;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class test {
public int v1(Integer[] in) {
Integer[] a = in;
//System.arraycopy(in, 0, a, 0, in.length);
if (a.length == 0)
return 0;
Arrays.sort(a);
int ret = 1;
int start = 0;
int dup = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] == a[i - 1] + 1) {
ret = Math.max(ret, i - start - dup + 1);
} else if (a[i] == a[i - 1]) {
dup += 1;
} else {
start = i;
dup = 0;
}
}
return ret;
}
public int v2(Integer[] a) {
HashMap map = new HashMap();
int max = 1;
for (int i : a) {
if (map.containsKey(i))
continue;
map.put(i, 1);
if (map.containsKey(i - 1)) {
max = Math.max(max, merge(map, i - 1, i));
}
if (map.containsKey(i + 1)) {
max = Math.max(max, merge(map, i, i + 1));
}
}
return max;
}
private int merge(HashMap map, int left, int right) {
int upper = right + map.get(right) - 1;
int lower = left - map.get(left) + 1;
int len = upper - lower + 1;
map.put(upper, len);
map.put(lower, len);
return len;
}
public int v3(Integer[] num) {
Set hs = new HashSet(Arrays.asList(num));
int ans = 0;
for (int v : num)
if (hs.contains(v))
ans = Math.max(ans, getCount(hs, v, false) + getCount(hs, v + 1,
true));
return ans;
}
int getCount(Set hs, int v, boolean asc) {
int count = 0;
while (hs.contains(v)) {
hs.remove(v);
count++;
if (asc)
v++;
else
v--;
}
return count;
}
public void run() {
Integer MAX_RANDOM = 327670;
Integer[][] ar = new Integer[1][10000000];
Random rand=new Random();
for (int i = 0; i < ar.length; i++) {
for (int j = 0; j < ar[i].length; j++) {
ar[i][j] = rand.nextInt()%MAX_RANDOM;
}
}
long milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
v1(ar[i]);
}
long used = System.currentTimeMillis() - milli;
System.out.println("Sort used time (ms): " + used);
milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
v2(ar[i]);
}
used = System.currentTimeMillis() - milli;
System.out.println("HashMap Used time (ms): " + used);
milli = System.currentTimeMillis();
for (int i = 0; i < ar.length; i++) {
v3(ar[i]);
}
used = System.currentTimeMillis() - milli;
System.out.println("HashSet Used time (ms): " + used);
}

public static void main(String[] args) throws Exception
{
new test().run();
}
}

【在 s********x 的大作中提到】

: 你的电脑也太神了吧，连你的算法都无偿支持啊：）
: 我觉得别人测大部分都是v1快的，呵呵

s********x
发帖数: 914

我找到proof啦 - quick sort worst case is nlog(n)
Data Structures
& Algorithms
in Java
Second Edition
Robert Lafore
page 725
TABLE 15.3 Comparison of Sorting Algorithms
Sort Average Worst Comparison Extra Memory
Bubble O(N2) O(N2) Poor No
Selection O(N2) O(N2) Fair No
Insertion O(N2) O(N2) Good No
Shellsort O(N3/2) O(N3/2) — No
Quicksort O(N*logN) O(N2) Good No
Mergesort O(N*logN) O(N*logN) Fair Yes
Heapsort O(N*logN) O(N*logN) Fair No

p*****2
发帖数: 21240

prove什么了？

【在 s********x 的大作中提到】

: 我找到proof啦 - quick sort worst case is nlog(n)
: Data Structures
: & Algorithms
: in Java
: Second Edition
: Robert Lafore
: page 725
: TABLE 15.3 Comparison of Sorting Algorithms
: Sort Average Worst Comparison Extra Memory
: Bubble O(N2) O(N2) Poor No

s********x
发帖数: 914

quick sort worst case is nlog(n)

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

:
: prove什么了？

p*****2
发帖数: 21240

Quicksort O(N*logN) O(N2) Good No

【在 s********x 的大作中提到】

: quick sort worst case is nlog(n)

s********x
发帖数: 914

还真是俺看错了哎，啊呀

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

:
: Quicksort O(N*logN) O(N2) Good No

相关主题
● 4sum o(n^2)超时	● 问个Java的HashSet.contains的问题
● Java 面试关于map 和set	● 问一个G家面试题
● HashTable space complexity?	● Linked电面分享，挺好的题应该已挂
进入JobHunting版参与讨论

s********x
发帖数: 914

Sort used time (ms): 5182
HashMap Used time (ms): 900
HashSet Used time (ms): 7137

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

:
: Quicksort O(N*logN) O(N2) Good No

p*****2
发帖数: 21240

你现在是不是在F太爽了？

【在 s********x 的大作中提到】

: 还真是俺看错了哎，啊呀

p*****2
发帖数: 21240

这个估计真是hit GC了。

【在 s********x 的大作中提到】

: Sort used time (ms): 5182
: HashMap Used time (ms): 900
: HashSet Used time (ms): 7137

s********x
发帖数: 914

不在F，去年试了，店面碰到阿三，俺心就凉了，呵呵
不过俺也没打算真的要去，只是怕老板不给promotion就想给点颜色，不过老板给了

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

:
: 这个估计真是hit GC了。

p*****2
发帖数: 21240

太牛了。你在哪里组呢？刚进去就被promote了？

【在 s********x 的大作中提到】

: 不在F，去年试了，店面碰到阿三，俺心就凉了，呵呵
: 不过俺也没打算真的要去，只是怕老板不给promotion就想给点颜色，不过老板给了

s********x
发帖数: 914

这个俺再爆料都可以被人肉出来了吧，呵呵，俺要睡了，二爷good night

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

:
: 太牛了。你在哪里组呢？刚进去就被promote了？

P***t
发帖数: 1006

Your code:
Integer MAX_RANDOM = 327670;
Integer[][] ar = new Integer[1][10000000];
Random rand=new Random();
for (int i = 0; i < ar.length; i++) {
for (int j = 0; j < ar[i].length; j++) {
ar[i][j] = rand.nextInt()%MAX_RANDOM;
}
}
A long array 10000000 with member only ranging from 0 - 327669. That means
there are on average 30 duplicates per number. 当然是HASH完胜。

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

:
: 太牛了。你在哪里组呢？刚进去就被promote了？

M**u
发帖数: 10158

Java的hashset效率的确不高

length
Range

【在 P***t 的大作中提到】

p*****2
发帖数: 21240

这个确实是，试了一下这个。HashMap最快。
Integer MAX_RANDOM = 32767000;
Sort used time (ms): 4666
HashMap Used time (ms): 3648
HashSet Used time (ms): 7194

【在 P***t 的大作中提到】

: Your code:
: Integer MAX_RANDOM = 327670;
: Integer[][] ar = new Integer[1][10000000];
: Random rand=new Random();
: for (int i = 0; i < ar.length; i++) {
: for (int j = 0; j < ar[i].length; j++) {
: ar[i][j] = rand.nextInt()%MAX_RANDOM;
: }
: }
: A long array 10000000 with member only ranging from 0 - 327669. That means

p*****2
发帖数: 21240

Integer MAX_RANDOM = 3276700;
Integer[][] ar = new Integer[1][1000000];
Sort used time (ms): 498
HashMap Used time (ms): 709
HashSet Used time (ms): 214
这个又是hashset快。

相关主题
● Facebook Hacker Cup	● 请教一个常见的面试题的答案
● a[i] + b[j] = c[k] 的题有靠谱的答案不?	● 请教个面试题
● 贡献一道面试题	● 面试题求解：remove first duplicate number from an array
进入JobHunting版参与讨论

a*******3
发帖数: 27

不知道楼主在哪里跑出来的结果竟然需要1+秒，leetcode上我两种方法都是70ms左右，
hash略快（C++)。不过看上面大数据测试集，也就10000，logn约为13，很小。所以说
，这个测试跟测试数据也有很大关系。如果测试数据更大一些，你自己可以算，hash的
常数和logn的大小到底哪个大。

s********x
发帖数: 914

真的是那么多duplicate的话干脆用bitvector 做bitset好了。
用sort的话也应该先去掉duplicate再sort，performance未必比hashset差

【在 a*******3 的大作中提到】

: 不知道楼主在哪里跑出来的结果竟然需要1+秒，leetcode上我两种方法都是70ms左右，
: hash略快（C++)。不过看上面大数据测试集，也就10000，logn约为13，很小。所以说
: ，这个测试跟测试数据也有很大关系。如果测试数据更大一些，你自己可以算，hash的
: 常数和logn的大小到底哪个大。

i******t
发帖数: 52

why not use counting sort in O(N)?

length
Range

【在 P***t 的大作中提到】

l*********8
发帖数: 4642

如何“先去掉duplicate再sort”？

【在 s********x 的大作中提到】

: 真的是那么多duplicate的话干脆用bitvector 做bitset好了。
: 用sort的话也应该先去掉duplicate再sort，performance未必比hashset差

s********x
发帖数: 914

就是counting sort with bitvector
大不了先生成hashset，然后convert成array

【在 l*********8 的大作中提到】

: 如何“先去掉duplicate再sort”？

(共1页)

进入JobHunting版参与讨论

相关主题
● Facebook Hacker Cup	● 分享面试题
● a[i] + b[j] = c[k] 的题有靠谱的答案不?	● 问道面试题
● 贡献一道面试题	● subset
● 请教一个常见的面试题的答案	● 问个关于排序的面试题
● 请教个面试题	● LeetCode 的 4 sum 问题如何用hash table做呢？
● 面试题求解：remove first duplicate number from an array	● 4sum o(n^2)超时
● A家面试题	● Java 面试关于map 和set
● 两个Amazon面试题	● HashTable space complexity?

相关话题的讨论汇总
话题: int话题: integer话题: used话题: max话题: hashmap

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天