一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 1060|回复: 13
收起左侧

Indeed OA+电面

[复制链接] |试试Instant~ |关注本帖
富民文 发表于 2017-9-15 23:22:42 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Indeed - 内推 - 技术电面 在线笔试 |Other在职跳槽

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

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

x
前几天参加了Indeed的招聘,oa是#10 + 电面一个小时,问了Summary Ranges,当时直接秒掉,follow up有duplicate 也秒掉,接着重点来了follow up是:输入改为无序、有重复,请设计优于O(n)时间复杂度的算法。我卡住了,然后过两天说跪了,请问大家对这个算法有什么好的想法吗?-google 1point3acres

多谢多谢

评分

2

查看全部评分

daguanyuan 发表于 2017-9-16 00:14:40 | 显示全部楼层
O(n)的倒是有一个,但是优于O(n)的暂时还没想到:数组内最大值是N,则建立一个N大小的数组,初始化为-1,表示还未出现;数组的index表示出现的值,数组的值表示index能达的最远的index,例如:依次输入[3, 1, 2, 5, 4, 99], 数组变化:arr[3] = 3; arr[1] = 1; 输入2时,发现邻居1和3都已经有了,查看1,最远可达1, 查看3, 最远可达3,于是更新arr[3] = 1, arr[1] = 3, arr[2] = 2(中间的都随便,只要不是-1就行); arr[5] = 5, 输入4,发现3, 5 都有了,查看3最远可达1,则更新arr[1] = 5, 查看5,最远可达5,则更新arr[5] = 1;
例子中只出现了刚好两个邻居都出现了,还有只有一侧已经在数组中的情况,但更简单,不举例了;
在最后,扫一边数组,得出答案

补充内容 (2017-9-16 00:20):
有点像并查集
回复 支持 3 反对 0

使用道具 举报

aaa18918 发表于 2017-10-12 06:10:03 | 显示全部楼层
daguanyuan 发表于 2017-9-16 00:14
O(n)的倒是有一个,但是优于O(n)的暂时还没想到:数组内最大值是N,则建立一个N大小的数组,初始化为-1,表 ...

如果输入是有负数,输入的数字很大很小都有,比如:
[-11111111111, 34, -11111111110, 8, -11, -10, -9, 8, 8, 33, 33, 6, 1, 9, 12, 99999999, 999999999, 999999998]
极端情况下[-sys.maxint-1, sys.maxint, sys.maxint-1]的输入,会有比较大的空间开销,而且我不确定arr[negative]在java中能不能访问,python中是从后往前数数组。

我的解法是用hash_table记下每个数,value值都设为True。第二遍扫hash_table的时候,如果当前key对应的value值为True,从这个key值往左往右扫,这样就把和这个key值相连的数都扫出来了。因为一共有O(N)个数,所以时间复杂度和空间复杂度都是O(N)。

问题:
1.我的解法得出的结果不是有序的。如果要排序的话会需要O(AlgA)时间复杂度,A是总共的range个数。O(AlgA)和O(N)谁大谁小,取决于压缩程度。但我们可以说在需要得到有结果的情况下,最好情况是O(N), 最坏情况是O(NlgN)。最好情况发生于压缩率大的时候,最坏情况发生于数组中所有数字都不相连的情况。

附代码和简单的测试。
def solution(input):. Waral 鍗氬鏈夋洿澶氭枃绔,
        hash_table = {}. Waral 鍗氬鏈夋洿澶氭枃绔,
        for i in input:.1point3acres缃
                hash_table = True. 1point3acres.com/bbs

        res = []
        for key in hash_table.iterkeys():
                if hash_table[key]:
                        hash_table[key] = False

                        l, r = key, key. 鍥磋鎴戜滑@1point 3 acres
                        while l-1 in hash_table and hash_table[l-1]:
                                l -= 1
                                hash_table[l] = False
                        while r+1 in hash_table and hash_table[r+1]:
                                r += 1
                                hash_table[r] = False

                        cur_range = "{}->{}".format(l, r) if l != r else str(r)
                        res.append(cur_range).鏈枃鍘熷垱鑷1point3acres璁哄潧

        return res

input1 = [-11111111111, 34, -11111111110, 8, -11, -10, -9, 8, 8, 33, 33, 6, 1, 9, 12, 99999999, 999999999, 999999998]
print solution(input1)

input2 = []
print solution(input2)
-google 1point3acres
input3 = [5, 5, 5, 5, 5, 5, 55, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
print solution(input3)


输出:. From 1point 3acres bbs
['33->34', '6', '1', '8->9', '12', '-11->-9', '-11111111111->-11111111110', '999999998->999999999', '99999999']
[]
['1', '5->6', '55]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

赖赖有offer 发表于 2017-9-18 05:15:06 | 显示全部楼层
请问楼主OA题目有变吗?
回复 支持 反对

使用道具 举报

maydaycn 发表于 2017-9-18 05:31:52 | 显示全部楼层
同求问楼主 oa题目有变嘛~
回复 支持 反对

使用道具 举报

YonghuiFan 发表于 2017-9-25 12:23:11 | 显示全部楼层
同问OA有变化吗?
回复 支持 反对

使用道具 举报

 楼主| 富民文 发表于 2017-9-28 14:09:12 | 显示全部楼层
木有变化  紫薯
回复 支持 反对

使用道具 举报

Mr_HAHAHAHAHA 发表于 2017-10-24 12:49:29 | 显示全部楼层
daguanyuan 发表于 2017-9-16 00:14
O(n)的倒是有一个,但是优于O(n)的暂时还没想到:数组内最大值是N,则建立一个N大小的数组,初始化为-1,表 ...

你最后扫一遍数组是指大小为N的那个数组么?这样子如果是[0, 11111111]这种情况,岂不是复杂度比O(n)还要大?
回复 支持 反对

使用道具 举报

美帝等我! 发表于 2017-10-26 09:11:12 | 显示全部楼层
  1. public static List<String> summaryRangesOutOfOrder(int[] nums) {
  2.         List<int[]> list = new ArrayList<>();
  3.         Set<Integer> set = new HashSet<>();
  4.         for (int i: nums) {
  5.             set.add(i);
  6.         }
  7.         for (int num: nums) {
  8.             if (set.contains(num)) {. more info on 1point3acres.com
  9.                 int start = num;
  10.                 int end = num;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.                 set.remove(num);
  12.                 while (set.contains(start - 1)) {. from: 1point3acres.com/bbs
  13.                     start = start - 1;. from: 1point3acres.com/bbs
  14.                     set.remove(start);
  15.                 }
  16.                 while (set.contains(end + 1)) {
  17.                     end = end + 1;
  18.                     set.remove(end); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.                 }-google 1point3acres
  20.                 list.add(new int[]{start, end});
  21.             }
  22.         }
  23.         Collections.sort(list, new Comparator<int[]>() {
  24.             @Override
  25.             public int compare(int[] o1, int[] o2) {
  26.                 return o1[0] - o2[0];
  27.             }
  28.         });

  29.         List<String> res = new ArrayList<>();
  30.         for (int[] range: list) {
  31.             if (range[0] == range[1]) {
  32.                 res.add(range[0] + "");
  33.             } else {
  34.                 res.add(range[0] + "->" + range[1]);
  35.             }
  36.         }
  37.         return res;
  38.     }
复制代码
贴一个java代码 和python那个是一样的道理
回复 支持 反对

使用道具 举报

wocaole 发表于 2017-10-26 13:32:01 | 显示全部楼层
美帝等我! 发表于 2017-10-26 09:11
贴一个java代码 和python那个是一样的道理

鳄鱼大神,这个是乱序有重复的情况吗?

补充内容 (2017-10-26 13:33):
额,不好意思,没仔细看函数名,明显是的额。谢谢分享啊。我好好拜读下这code。
回复 支持 反对

使用道具 举报

wocaole 发表于 2017-10-26 13:46:04 | 显示全部楼层
美帝等我! 发表于 2017-10-26 09:11
贴一个java代码 和python那个是一样的道理

鳄神,还能大概讲讲思路吗?

补充内容 (2017-10-26 13:47):
额,我看看python那位的就行了。
回复 支持 反对

使用道具 举报

美帝等我! 发表于 2017-10-27 01:58:11 | 显示全部楼层
wocaole 发表于 2017-10-26 13:46
鳄神,还能大概讲讲思路吗?

补充内容 (2017-10-26 13:47):

哈哈哈哈wocaole你好 好像你都自己解决了
回复 支持 反对

使用道具 举报

wocaole 发表于 2017-10-27 03:26:14 | 显示全部楼层
美帝等我! 发表于 2017-10-27 01:58
哈哈哈哈wocaole你好 好像你都自己解决了

嗯, 最后用了一个哈希set搞定了。参考了前人的一个解法。
回复 支持 反对

使用道具 举报

美帝等我! 发表于 2017-10-27 03:33:42 | 显示全部楼层
wocaole 发表于 2017-10-27 03:26
嗯, 最后用了一个哈希set搞定了。参考了前人的一个解法。

很棒 你啥时候电面哟
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-21 15:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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