传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 285|回复: 3
收起左侧

Indeed OA+电面

[复制链接] |试试Instant~ |关注本帖
富民文 发表于 6 天前 | 显示全部楼层 |阅读模式

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

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

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

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

评分

1

查看全部评分

daguanyuan 发表于 5 天前 | 显示全部楼层
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):
有点像并查集
回复 支持 2 反对 0

使用道具 举报

赖赖有offer 发表于 3 天前 | 显示全部楼层
请问楼主OA题目有变吗?
回复 支持 反对

使用道具 举报

maydaycn 发表于 3 天前 | 显示全部楼层
同求问楼主 oa题目有变嘛~
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 13:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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