入职后感觉很空虚

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1506|回复: 13
收起左侧

Indeed OA+电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
富民文 发表于 2017-9-15 23:22:42 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (53)
 
 
0% (0)  踩

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

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

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

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

多谢多谢

评分

参与人数 2大米 +33 收起 理由
singer82 + 3 很有用的信息!
candy_shmily + 30

查看全部评分


上一篇:丢盒子 OA
下一篇:Amazon OA2
我的人缘0
yikehongxin 发表于 2017-9-16 00:14:40 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  91% (226)
 
 
8% (22)  踩
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;
例子中只出现了刚好两个邻居都出现了,还有只有一侧已经在数组中的情况,但更简单,不举例了;
在最后,扫一边数组,得出答案. Waral 博客有更多文章,

补充内容 (2017-9-16 00:20):
有点像并查集
回复

使用道具 举报

我的人缘0
aaa18918 发表于 2017-10-12 06:10:03 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  86% (86)
 
 
14% (14)  踩
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中是从后往前数数组。. 1point 3acres 论坛
.1point3acres网
我的解法是用hash_table记下每个数,value值都设为True。第二遍扫hash_table的时候,如果当前key对应的value值为True,从这个key值往左往右扫,这样就把和这个key值相连的数都扫出来了。因为一共有O(N)个数,所以时间复杂度和空间复杂度都是O(N)。

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

附代码和简单的测试。.留学论坛-一亩-三分地
def solution(input):
. From 1point 3acres bbs        hash_table = {}
        for i in input:
                hash_table = True. 1point3acres

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

                        l, r = key, key. from: 1point3acres
                        while l-1 in hash_table and hash_table[l-1]:. 1point3acres
                                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.本文原创自1point3acres论坛

input1 = [-11111111111, 34, -11111111110, 8, -11, -10, -9, 8, 8, 33, 33, 6, 1, 9, 12, 99999999, 999999999, 999999998]
print solution(input1)
来源一亩.三分地论坛.
input2 = []. 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]. more info on 1point3acres


评分

参与人数 1大米 +3 收起 理由
singer82 + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
美帝等我! 发表于 2017-10-26 09:11:12 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (23)
 
 
0% (0)  踩
  1. public static List<String> summaryRangesOutOfOrder(int[] nums) {
  2.         List<int[]> list = new ArrayList<>();
  3.         Set<Integer> set = new HashSet<>();.本文原创自1point3acres论坛
  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;
  11.                 set.remove(num);. 围观我们@1point 3 acres
  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;-google 1point3acres
  18.                     set.remove(end);
  19.                 }
  20.                 list.add(new int[]{start, end});.1point3acres网
  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.             }.本文原创自1point3acres论坛
  28.         });

  29.         List<String> res = new ArrayList<>();
  30.         for (int[] range: list) {
  31.             if (range[0] == range[1]) {
    来源一亩.三分地论坛.
  32.                 res.add(range[0] + "");
    .本文原创自1point3acres论坛
  33.             } else {
  34.                 res.add(range[0] + "->" + range[1]);
  35.             }
  36.         }
  37.         return res;
  38.     }
复制代码
贴一个java代码 和python那个是一样的道理
回复

使用道具 举报

我的人缘0
赖赖有offer 发表于 2017-9-18 05:15:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (27)
 
 
3% (1)  踩
请问楼主OA题目有变吗?
回复

使用道具 举报

我的人缘0
maydaycn 发表于 2017-9-18 05:31:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
同求问楼主 oa题目有变嘛~
回复

使用道具 举报

我的人缘0
YonghuiFan 发表于 2017-9-25 12:23:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (18)
 
 
5% (1)  踩
同问OA有变化吗?
回复

使用道具 举报

我的人缘0
 楼主| 富民文 发表于 2017-9-28 14:09:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (53)
 
 
0% (0)  踩
木有变化  紫薯
Mobile Apps Category (English)728x90
回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
wocaole 发表于 2017-10-26 13:32:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (8)
 
 
33% (4)  踩
美帝等我! 发表于 2017-10-26 09:11.本文原创自1point3acres论坛
贴一个java代码 和python那个是一样的道理

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

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

使用道具 举报

我的人缘0
wocaole 发表于 2017-10-26 13:46:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (8)
 
 
33% (4)  踩
美帝等我! 发表于 2017-10-26 09:11
贴一个java代码 和python那个是一样的道理
. 留学申请论坛-一亩三分地
鳄神,还能大概讲讲思路吗?

补充内容 (2017-10-26 13:47): 来源一亩.三分地论坛.
额,我看看python那位的就行了。
回复

使用道具 举报

我的人缘0
美帝等我! 发表于 2017-10-27 01:58:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (23)
 
 
0% (0)  踩
wocaole 发表于 2017-10-26 13:46
鳄神,还能大概讲讲思路吗?. more info on 1point3acres
来源一亩.三分地论坛.
补充内容 (2017-10-26 13:47):

哈哈哈哈wocaole你好 好像你都自己解决了
回复

使用道具 举报

我的人缘0
wocaole 发表于 2017-10-27 03:26:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  66% (8)
 
 
33% (4)  踩
美帝等我! 发表于 2017-10-27 01:58
哈哈哈哈wocaole你好 好像你都自己解决了

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

使用道具 举报

我的人缘0
美帝等我! 发表于 2017-10-27 03:33:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (23)
 
 
0% (0)  踩
wocaole 发表于 2017-10-27 03:26
嗯, 最后用了一个哈希set搞定了。参考了前人的一个解法。

很棒 你啥时候电面哟
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-19 15:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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