《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 930|回复: 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)时间复杂度的算法。我卡住了,然后过两天说跪了,请问大家对这个算法有什么好的想法吗?

多谢多谢. from: 1point3acres.com/bbs

评分

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; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
例子中只出现了刚好两个邻居都出现了,还有只有一侧已经在数组中的情况,但更简单,不举例了;. From 1point 3acres bbs
在最后,扫一边数组,得出答案

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

使用道具 举报

aaa18918 发表于 2017-10-12 06:10:03 | 显示全部楼层
daguanyuan 发表于 2017-9-16 00:14. more info on 1point3acres.com
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)。

问题:. visit 1point3acres.com for more.
1.我的解法得出的结果不是有序的。如果要排序的话会需要O(AlgA)时间复杂度,A是总共的range个数。O(AlgA)和O(N)谁大谁小,取决于压缩程度。但我们可以说在需要得到有结果的情况下,最好情况是O(N), 最坏情况是O(NlgN)。最好情况发生于压缩率大的时候,最坏情况发生于数组中所有数字都不相连的情况。
.1point3acres缃
附代码和简单的测试。
def solution(input):
        hash_table = {}
        for i in input:
                hash_table = True

        res = []
        for key in hash_table.iterkeys():
                if hash_table[key]:
                        hash_table[key] = False
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        l, r = key, key-google 1point3acres
                        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)

        return res

input1 = [-11111111111, 34, -11111111110, 8, -11, -10, -9, 8, 8, 33, 33, 6, 1, 9, 12, 99999999, 999999999, 999999998]
print solution(input1). Waral 鍗氬鏈夋洿澶氭枃绔,

input2 = []-google 1point3acres
print solution(input2)

input3 = [5, 5, 5, 5, 5, 5, 55, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6]
print solution(input3)


输出:
['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<>();. visit 1point3acres.com for more.
  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)) {
  9.                 int start = num;
  10.                 int end = num;. From 1point 3acres bbs
  11.                 set.remove(num);
  12.                 while (set.contains(start - 1)) {
  13.                     start = start - 1;
  14.                     set.remove(start); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.                 }
  16.                 while (set.contains(end + 1)) {
  17.                     end = end + 1;
  18.                     set.remove(end);
  19.                 }
  20.                 list.add(new int[]{start, end});. 1point 3acres 璁哄潧
  21.             }
  22.         }
  23.         Collections.sort(list, new Comparator<int[]>() {
  24.             @Override
  25.             public int compare(int[] o1, int[] o2) {. visit 1point3acres.com for more.
  26.                 return o1[0] - o2[0];
  27.             }. 1point 3acres 璁哄潧
  28.         });
  29. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  30.         List<String> res = new ArrayList<>();
  31.         for (int[] range: list) {
  32.             if (range[0] == range[1]) {
  33.                 res.add(range[0] + "");
  34.             } else {
  35.                 res.add(range[0] + "->" + range[1]);
  36.             }
  37.         }
  38.         return res;
  39.     }
复制代码
贴一个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那个是一样的道理
. 鍥磋鎴戜滑@1point 3 acres
鳄神,还能大概讲讲思路吗?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (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, 2017-11-24 17:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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