今天碰到一个面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Java - 爪哇娇娃

今天碰到一个面试题

今天碰到一个面试题# Java - 爪哇娇娃

Y*G2013-05-22 07:05

1 楼

Given an array of integers, array value range from 0 to array.length -1, try
to find duplicate number in O(N) time.
如果没做过，要在面试30分钟写出来还是有难度地

p*n2013-05-22 07:05

2 楼

往hash table里面放呗；发现放不进去就是有duplicte number啊；两分钟就想出来了

try

【在 Y**G 的大作中提到】

: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地

Y*G2013-05-22 07:05

3 楼

打回重写，不及格

来了

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

: 往hash table里面放呗；发现放不进去就是有duplicte number啊；两分钟就想出来了
:
: try

Y*G2013-05-22 07:05

4 楼

另外要求:额外的内存使用是常熟。数组是可写的

来了

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

: 往hash table里面放呗；发现放不进去就是有duplicte number啊；两分钟就想出来了
:
: try

M*r2013-05-22 07:05

5 楼

Too easy. This line tells you everything "array value range from 0 to array.
length -1". Scan the array once and put the number into right position.

x*o2013-05-22 07:05

6 楼

try
ARRAY有序没有?一个重复还是可能存在很多重复?额外内存只能用O(1)?

【在 Y**G 的大作中提到】

: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地

p*n2013-05-22 07:05

7 楼

我说的不对吗？就是个arraylist n啊，往里按数值放数据，满了就表示重复了

【在 Y**G 的大作中提到】

: 打回重写，不及格
:
: 来了

p*n2013-05-22 07:05

8 楼

数组是满的么？

【在 Y**G 的大作中提到】

: 另外要求:额外的内存使用是常熟。数组是可写的
:
: 来了

f*n2013-05-22 07:05

9 楼

Hash table access is O(n) in worst case.

来了

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

: 往hash table里面放呗；发现放不进去就是有duplicte number啊；两分钟就想出来了
:
: try

z*32013-05-22 07:05

10 楼

前面有人说了
就是做一个空的array
然后扫一遍，把每一个取到的值往空的里面放
偏移就是arrya上的integer
这个题其实类似用<>, &, | 用一个整数来判断ascii code重复的情况

try

【在 Y**G 的大作中提到】

: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地

M*r2013-05-22 07:05

11 楼

LZ mentioned the given array can be overwritten, so a new array is
unnecessary. just swap values. when two swapping values equal, you find the
dup.

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

: 前面有人说了
: 就是做一个空的array
: 然后扫一遍，把每一个取到的值往空的里面放
: 偏移就是arrya上的integer
: 这个题其实类似用<>, &, | 用一个整数来判断ascii code重复的情况
:
: try

z*32013-05-22 07:05

12 楼

这个要是我就先不说
估计对方会问有没有更好的方法
然后想一下再告诉对方

the

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

: LZ mentioned the given array can be overwritten, so a new array is
: unnecessary. just swap values. when two swapping values equal, you find the
: dup.

g*e2013-05-22 07:05

13 楼

这种问烂了的题没做过只能说是没好好准备面试

try

【在 Y**G 的大作中提到】

: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地

p*n2013-05-22 07:05

14 楼

ft，那我就对了啊

【在 f*******n 的大作中提到】

: Hash table access is O(n) in worst case.
:
: 来了

p*n2013-05-22 07:05

15 楼

所以我问数组是不是满的，如果不满，就没法swap了

the

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

: LZ mentioned the given array can be overwritten, so a new array is
: unnecessary. just swap values. when two swapping values equal, you find the
: dup.

z*32013-05-22 07:05

16 楼

错了，老大，对比hashtable里面的value时候要重新找一遍
这样就是O(n^2)了

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

: ft，那我就对了啊

p*n2013-05-22 07:05

17 楼

ft，你为啥要找啊，往table里放是1，比较也是1，最多是2n，也即是O(n)，多明白啊

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

: 错了，老大，对比hashtable里面的value时候要重新找一遍
: 这样就是O(n^2)了

z*32013-05-22 07:05

18 楼

它说的是额外找一个来swap
也就是某人说的O(1)空间复杂度

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

: 所以我问数组是不是满的，如果不满，就没法swap了
:
: the

z*32013-05-22 07:05

19 楼

您确定您明白什么是hashtable？

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

: ft，你为啥要找啊，往table里放是1，比较也是1，最多是2n，也即是O(n)，多明白啊

W*o2013-05-22 07:05

20 楼

这方法不对，我这初学的都看出来了

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

z*32013-05-22 07:05

21 楼

我跟这个id说的是一个方法
发信人: Mixer (Mixer), 信区: Java
标题: Re: 今天碰到一个面试题
发信站: BBS 未名空间站 (Wed May 22 16:41:54 2013, 美东)
Too easy. This line tells you everything "array value range from 0 to array.
length -1". Scan the array once and put the number into right position.

【在 W***o 的大作中提到】

: 这方法不对，我这初学的都看出来了

p*n2013-05-22 07:05

22 楼

呵呵... 问题解决了不就完了；要不您给讲讲那儿不对？

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

: 您确定您明白什么是hashtable？

z*32013-05-22 07:05

23 楼

我已经告诉过你了

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

: 呵呵... 问题解决了不就完了；要不您给讲讲那儿不对？

p*n2013-05-22 07:05

24 楼

你这个要用到O(n)的内存，错了

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

p*n2013-05-22 07:05

25 楼

车轱辘话来回说，hash要是O(n^2),那还有人做hash么？

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

: 我已经告诉过你了

z*32013-05-22 07:05

26 楼

针对楼主的原文，楼主主贴倒是没有说要控制空间复杂度
对于空间复杂度是O(1)的方法，别人也说了，我表示同意

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

: 你这个要用到O(n)的内存，错了

z*32013-05-22 07:05

27 楼

我放弃了，你赢了

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

: 车轱辘话来回说，hash要是O(n^2),那还有人做hash么？

p*n2013-05-22 07:05

28 楼

hash 是O(1),n个数，就是O(n)，不过我这个也错了，因为也用了O(n)的内存

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

: 我已经告诉过你了

p*n2013-05-22 07:05

29 楼

真没意思你赢了

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

: 我放弃了，你赢了

o*i2013-05-22 07:05

30 楼

O(N)空间：
public void findDup2(int[] numbers) {
int l = numbers.length;
int[] n2 = new int[l];

for (int i = 0; i < l; i++) {

n2[numbers[i]] ++;
}

//print results:
for (int i = 0; i < n2.length; i++) {
if (n2[i] > 1) {
System.out.print(i + ",");
}
}
System.out.println();
}
O(1)空间：
public void findDup(int[] numbers) {
int l = numbers.length;

for (int i = 0; i < l; i++) {
while (i != numbers[i]) {
if (numbers[i] == numbers[numbers[i]]) {
break;
} else {
int m = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = m;
}
}
}

//print results:
for (int i = 0; i < l; i++) {
if (i != numbers[i]) {
System.out.print(numbers[i] + ",");
}
}
System.out.println();
}

try

【在 Y**G 的大作中提到】

: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地

Y*G2013-05-22 07:05

31 楼

这是正解

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

: O(N)空间：
: public void findDup2(int[] numbers) {
: int l = numbers.length;
: int[] n2 = new int[l];
:
: for (int i = 0; i < l; i++) {
:
: n2[numbers[i]] ++;
: }
:

T*g2013-05-22 07:05

32 楼

.... pls consider bitset

try

【在 Y**G 的大作中提到】

: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地

b*a2013-05-22 07:05

33 楼

package com.bruce.test;
public class TestApp {
public static void main(String[] args) {
int[] arr = { 2, 1, 3, 4, 11, 2, 6, 1, 12, 4, 11, 2, 12, 11, 11 };
System.out.println("O(n) space");
OnFindDuplicate(arr);
System.out
.println("\nO(1) space, but duplicated output sometimes like
11");
OoneFindDuplicate(arr);
System.out.println("\nO(1) space, no duplicated output ");
OoneFindDuplicate2(arr);
}
// need a new array as a counter
public static void OnFindDuplicate(int[] arr) {
int[] counter = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
counter[arr[i]]++;
if (counter[arr[i]] == 2) {
System.out.print(arr[i] + ",");
}
}
}
// when you are trying to exchange a number to the right place and find
// already one there, the number is duplicate
public static void OoneFindDuplicate(int[] arr) {
int temp = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != i && arr[arr[i]] != arr[i]) {
temp = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = temp;
} else if (arr[i] != i && arr[arr[i]] == arr[i]) {
System.out.print(arr[i] + ",");
}
}
}
// input array itself can be used as a counter
public static void OoneFindDuplicate2(int[] arr) {
int temp = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == i) {
arr[i] = -1;
} else if (arr[i] >= 0 && arr[arr[i]] == arr[i]) {
System.out.print(arr[i] + ",");
arr[arr[i]] = -2;
} else if (arr[i] >= 0 && arr[arr[i]] >= 0) {
temp = arr[arr[i]];
arr[arr[i]] = -1;
arr[i] = temp;
} else if (arr[i] >= 0 && arr[arr[i]] < 0) {
if (arr[arr[i]] == -1)
System.out.print(arr[i] + ",");
arr[arr[i]] = arr[arr[i]] - 1;
}
}
}
}

s*o2013-05-22 07:05

34 楼

while inside for，第一感觉不是o(n)

【在 Y**G 的大作中提到】

: 这是正解
:
:

k*i2013-05-22 07:05

35 楼

public static int solveDuplicateElement(Integer[] ar) {
int pos = 0, len = ar.length, bigO = 0;
while (pos < len) {
int slot = ar[pos];
if (slot == pos || slot == len) {
// being in place or invalidated
++pos;
} else {
int next = ar[slot];
if (next == slot) {
// to invalidate duplicate
ar[pos] = len;
++pos;
} else {
// to reshuffle postion
int temp = slot;
ar[pos] = next;
ar[slot] = temp;
}
}
++bigO;
}
return bigO;
}
@Test
public void testSolveDuplicateElement() {
int len = 1000;
Integer[] ar = new Integer[len];
Random rand = new Random();
for (int i = 0; i < len; i++) {
ar[i] = rand.nextInt(len);
}
List before = new ArrayList(
new HashSet(Arrays.asList(ar)));
Collections.sort(before);
int bigO = solveDuplicateElement(ar);
List after = new ArrayList();
for (int el : ar) {
if (el != len) {
after.add(el);
}
}
Collections.sort(after);
assertEquals(before, after);
assertTrue(bigO < len * 2);
}

【在 Y**G 的大作中提到】

: 另外要求:额外的内存使用是常熟。数组是可写的
:
: 来了

B*r2013-05-22 07:05

36 楼

Super easy, in ruby:
arr.select{|e| arr.count(e) > 1}.uniq
Or a more verbose version:
arr.each_with_index do |e, i|
t = arr[e-1]
arr[e-1] = e
arr[i] = t
end