一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1671|回复: 40
收起左侧

hedvig电面 至今不知怎么解。。

[复制链接] |试试Instant~ |关注本帖
starriver 发表于 2015-8-15 12:54:02 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 全职@hedvig - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
上来就问题目,一道简单的秒过。然后问了一道到现在我都没想到解法的。。

题目:有n+1个1到n的数字,找出重复的字符。
可能有多个字符重复,找出其中任意一个就可以。每个字符可能重复2遍以上。
read only,O(1) extra space.
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我回答了O(n^2)的brute force解法。然后实在想不到更快的方法了。
要hint他问最快解法是多少,我说O(n),他说中间的呢,我说O(n log n), 他说那就找个O(n log n) 的解法出来。。。

当时想到的解法:
  • sort,不行,因为是read only
  • hash,不行,因为O(1) space
  • 用linked list find cycle的方式,也不行,可以找到有重复,可是不知道怎么找具体重复的数值。
  • O(n log n) 就想到了mergesort,每次分一半,然后分别找重复,如果两边都没有重复,merge一步不知道怎么做。
开始怀疑自己智商了。。


面试期间还能听到对面有人在讲话在笑,面试官还离开了一会>.< 现在想到电面都腿抽筋=。=. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

2

查看全部评分

zwcelesta 发表于 2015-8-16 09:48:10 | 显示全部楼层
回复 支持 2 反对 0

使用道具 举报

stellari 发表于 2015-8-16 12:37:34 | 显示全部楼层
mingycool 发表于 2015-8-16 11:56
他家就是奇葩啊,之前电面问我怎么压缩空间存储一个sorted array,既不是算法,也不是数据结构,而且就剩20 ...

这种题没有标准答案,给你1年有1年的答法,20分钟有20分钟的答法。20分钟的话,就是看你能不能在短时间内发散思维,把以前学的东西瞬间应用在新场合上。
假设数组是32位int型数据,我能马上想到的方法有这些: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1.是用一个hashmap: {value->occurrence}来表示这个数组,相当于Run-length压缩法。这最适用于数组有大量重复数据的情况。如果没有重复数据,反而所用内存会变为原来的2倍。
2.是范围表示:比如[1 2 3 4 5 7 8 9 11 13]可以表示为[{1 5}, {7 9}, {11}, {13}],这适用于数据没有重复,但有大量连续的情况。
3.是类似于1和2的综合。先假设我们有一个大小是INT_MAX-INT_MIN的数组M,其中M表示数字i在原数组A中出现的次数。比如当A = [1 2 2 3 4 5 5 7 8 9 11 11 13]时,M = [0 0 0 ..... 0 0 0 1 2 1 1 2 0 1 1 1 0 1 0 1 0 0 0 ... ],然后用Run-length法再压缩一次M。这个方法比1的好处是当大部分数字都不重复的话,也能获得较高的压缩率。
4. 比3再进一步。如果M中大部分值都是0或1。可以把这些数每32位一组pack到一个int中去。
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2015-8-16 12:47):
请自行在斜体开始的地方脑补一个[ i ],我每次都忘记这件事。
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-8-15 14:49:28 | 显示全部楼层
你想的Linked List Find Cycle方法应该是可以的:把array中的每一个元素的值看做是其指向的下一个元素的下标(1-based)。那么从最后一个元素开始遍历而形成的链表中一定有环,而且环的开始位置的下标就是重复元素。

比如[3 1 2 1 4]这个数组,从最后一个数4开始,得到的链表是4 -> (4号位上的)1 -> 3 -> 2 -> (2号位上的)1 -> 3 -> .... 环的开头是3,那么3的所在位置的下标一定是重复元素的值。为什么?因为既然它能成为环的开始,说明环外一定有一个元素指向它,而环里也一定有一个元素指向它。

-----

分治法通常都是递归实现的,不用递归的话,通常要自己开辟内存维护当前所分区域的信息。所以恐怕O(NlogN)的算法你就算想出来了,也不满足O(1)memory这个限制条件。
回复 支持 反对

使用道具 举报

 楼主| starriver 发表于 2015-8-15 20:22:00 | 显示全部楼层
stellari 发表于 2015-8-15 14:49
. 1point3acres.com/bbs你想的Linked List Find Cycle方法应该是可以的:把array中的每一个元素的值看做是其指向的下一个元素的下 ...
. From 1point 3acres bbs
谢大神回复!完全没想到是环开始的下标,一直在想环里的值。豁然开朗,谢谢大神~
分治法那个是说没有O(nlogn)的解法么?那为什么他会提示我找O(nlogn)的解呢。。。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-15 21:07:04 | 显示全部楼层
starriver 发表于 2015-8-15 20:22
谢大神回复!完全没想到是环开始的下标,一直在想环里的值。豁然开朗,谢谢大神~
分治法那个是说没有O(n ...

千万别这么称呼我啊,我水平非常有限……我只是觉得分治法不太容易做到O(1)内存。但是,O(NlogN)的算法并非只有分治法一种,也许有其他的O(NlogN)算法可以解决这道题。只是我目前还没想到。
回复 支持 反对

使用道具 举报

swing 发表于 2015-8-15 22:40:22 | 显示全部楼层
stellari 发表于 2015-8-15 14:49
你想的Linked List Find Cycle方法应该是可以的:把array中的每一个元素的值看做是其指向的下一个元素的下 ...

好难懂, 还有没有别的方法

补充内容 (2015-8-15 22:47):
好像有点理解了,那这个复杂度是O(n)吗
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2015-8-15 22:50):
好像有点理解了,那这个算法的复杂度是不是O(n)
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-15 23:26:51 | 显示全部楼层
stellari 发表于 2015-8-15 14:49
你想的Linked List Find Cycle方法应该是可以的:把array中的每一个元素的值看做是其指向的下一个元素的下 ...

O(1) space的话怎么判断一个元素有没有被visit过呢?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-15 23:40:00 | 显示全部楼层
wenqiang88 发表于 2015-8-15 23:26
O(1) space的话怎么判断一个元素有没有被visit过呢?

不需要判断每个元素是否被visit过,用快慢指针法即可。
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-16 00:41:46 | 显示全部楼层
我觉得第二题不太可能吧...read only 和space o1 就意味着不能记录访问信息.
. visit 1point3acres.com for more.所以只能用bit操作.然而出现次数又不定.....
回复 支持 反对

使用道具 举报

agneshanlu 发表于 2015-8-16 00:56:55 | 显示全部楼层
楼主,你看这样行不行。就是很像用leetcode那道find first missing positive题目的解法。因为你确定了array里面的number全部都是[ 1到 n+1]之间的。
所以遍历数组:若当前index下的数字等于index + 1, 则说明在当前所应该在的位置。遍历下一个数字。
                       若不等于,则去找到index = number-1的位置,index = number - 1的位置上,数字等于number,则说明,重复,则返回这个数字。
                      不重复则swap两个数。再进行比较。
  1. int getDuplicateNumber(vector<int> nums)
  2. {
  3.     int i = 0;
  4.     while(i < nums.size())
  5.     {. 鍥磋鎴戜滑@1point 3 acres
  6.         int number = nums[i];
  7.         if(number == i+1)
  8.         {
  9.             i++;
  10.         }
  11.         else.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.         {
  13.             if(number == nums[number-1])
  14.             {
  15.                 return number;
  16.             }-google 1point3acres
  17.             else
  18.             {
  19.                 //swap nums[i] and nums[number];
    . visit 1point3acres.com for more.
  20.                 int tmp = nums[number-1];
  21.                 nums[number-1] = number;
  22.                 nums[i] = tmp;
  23.             }
  24.         }
  25.     }. 1point 3acres 璁哄潧
  26.     return -1;
  27. }
复制代码
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-8-16 00:58):.鏈枃鍘熷垱鑷1point3acres璁哄潧
好吧。好像不行。因为readonly。。。sorry
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-16 01:16:31 | 显示全部楼层
agneshanlu 发表于 2015-8-16 00:56
楼主,你看这样行不行。就是很像用leetcode那道find first missing positive题目的解法。因为你确定了array ...

如果不是read only, 这个题是google onsite的一道经典原题, 就是用负数记录visit的信息 - -  
回复 支持 反对

使用道具 举报

 楼主| starriver 发表于 2015-8-16 01:24:38 | 显示全部楼层
swing 发表于 2015-8-15 22:40
好难懂, 还有没有别的方法

补充内容 (2015-8-15 22:47):

是O(n)的
回复 支持 反对

使用道具 举报

 楼主| starriver 发表于 2015-8-16 01:25:11 | 显示全部楼层
readman 发表于 2015-8-16 01:16
如果不是read only, 这个题是google onsite的一道经典原题, 就是用负数记录visit的信息 - -

少任何一个条件都很容易解~
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-16 01:33:54 | 显示全部楼层
starriver 发表于 2015-8-16 01:25
少任何一个条件都很容易解~
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
- - 我刚才回的另一条已经说了...read only + space 1 就是不能记录visit 信息...
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-16 01:35:00 | 显示全部楼层
starriver 发表于 2015-8-16 01:25
少任何一个条件都很容易解~

但是如果这数组是sorted, 就有解

补充内容 (2015-8-16 01:35):
- - partial sorted
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-16 01:48:17 | 显示全部楼层
提示一点,数是1到n,看清了开头是1.。。。。。
所以这个题类似k color问题
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-16 02:20:04 | 显示全部楼层
jiebour 发表于 2015-8-16 01:48
提示一点,数是1到n,看清了开头是1.。。。。。
所以这个题类似k color问题
. 鍥磋鎴戜滑@1point 3 acres
k color是啥 染色?
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-8-16 04:18:09 | 显示全部楼层
这道题可以利用Pigeonhole principle
//without sorting and changing array only find one O(nlogn). Waral 鍗氬鏈夋洿澶氭枃绔,

    public static void findOne(int[] nums) {
        if (nums == null || nums.length < 2) return;
        int N = nums.length - 1;
        int low = 1; // this is the range[1..N]
        int high = N;
        while (low < high) {
            int mid = (low + high) / 2;
            int count = 0;. 1point 3acres 璁哄潧
            for (int index = 0; index < N + 1; index++) {
                if (nums[index] >= low && nums[index] <= mid) {
                    count++;
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            }
            if (count > mid - low + 1) { // there are more on the left range
                high = mid;
            } else {. 1point 3acres 璁哄潧
                low = mid + 1;
            }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        System.out.println(low);
    }
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-16 04:47:17 | 显示全部楼层
public int find (int nums[], int n) {
        for (int i = 0; i < nums.length; i++) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            int slow = nums-1;
            int fast = nums-1;. 鍥磋鎴戜滑@1point 3 acres
            int count = 0;
            while (count < nums.length && nums-1 != i){-google 1point3acres
                slow = nums[slow] - 1;
                fast = nums[nums[fast]-1] - 1;
                if (slow == fast) {
                    slow = nums - 1;
                    while (slow  != fast){
. more info on 1point3acres.com                        slow = nums[slow] - 1;
                        fast = nums[fast] - 1;. 鍥磋鎴戜滑@1point 3 acres
                    }
                    return slow+1;
                }
                count++;
            }
        }
        return -1;. From 1point 3acres bbs
    }

补充内容 (2015-8-16 04:51):
依然觉得bit操作能解...
回复 支持 反对

使用道具 举报

agneshanlu 发表于 2015-8-16 05:59:27 | 显示全部楼层
Williamslg 发表于 2015-8-16 04:18
这道题可以利用Pigeonhole principle. 1point3acres.com/bbs
//without sorting and changing array only find one O(nlogn)

sounds great!
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-16 08:31:58 | 显示全部楼层
stellari 发表于 2015-8-15 23:40
不需要判断每个元素是否被visit过,用快慢指针法即可。

有道理,赞
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 10:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表