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


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 585|回复: 13
收起左侧

[找工就业] IXL 9.7 OA 貌似是新题

[复制链接] |试试Instant~ |关注本帖
jingshihao 发表于 2017-9-8 10:11:33 | 显示全部楼层 |阅读模式

2018(10-12月)-[16]CS硕士+<3个月短暂实习/全职 - 网上海投| 码农类全职@IXLfresh grad应届毕业生

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

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

x
前天网上海投的,今天收到了OA, 然后跪了。
第一题和面经一样,找有多少个圈,一看就知道怎么做。

第二题,给一组三角形的三个边的长度,判断每个三角形是不是valid。. 鍥磋鎴戜滑@1point 3 acres

第三题,给一数组,数组的每一个元素代表当前下标的direct predator。indirect predator 即为 direct predator 的 direct predator。我理解好像只向上找一次。要求给出一个最小的group的数,使得每个group里面的元素互相不为direct or indirect predator。
这道题竟然最后没有通过测试。。。。。 还是能力不行啊

第四题,给一数组,找到一个最小的区间,使得该区间包含这个数组的众数。例如,1, 2, 2, 3, 1, 众数为1, 2,  有两个区间{1, 2, 2, 3, 1}和{2, 2}, 返回2。
这题用了两个hashmap做的,感觉还有其他解法。。。
. more info on 1point3acres.com
求接下来的找工人品爆发啊
zhouz88 发表于 2017-9-8 10:21:13 | 显示全部楼层
disjoint sets 啊 第二题
回复 支持 反对

使用道具 举报

mk48 发表于 2017-9-9 08:23:42 | 显示全部楼层
我也是這套題
回复 支持 反对

使用道具 举报

 楼主| jingshihao 发表于 2017-9-9 09:00:33 | 显示全部楼层

第三题怎么做的
回复 支持 反对

使用道具 举报

uuisafresh 发表于 2017-9-9 09:54:42 | 显示全部楼层
我刚刚做完这套哈,第三题也是有点小纠结,贡献给大家我的解法,虽然听说这家公司做了OA就拒。

第三题乍眼看是并查集问题,但是predator关系图可能是颗树,就是3-(1,2),这样这个group有3个动物,但是只需要两组就够了,所以我的解法就是返回树的高度
回复 支持 反对

使用道具 举报

 楼主| jingshihao 发表于 2017-9-9 10:57:08 | 显示全部楼层
uuisafresh 发表于 2017-9-9 09:54
我刚刚做完这套哈,第三题也是有点小纠结,贡献给大家我的解法,虽然听说这家公司做了OA就拒。

第三题乍 ...
. 1point3acres.com/bbs
嗯,应该是正解,是返回最大树的高度吗
回复 支持 反对

使用道具 举报

uuisafresh 发表于 2017-9-9 11:31:58 | 显示全部楼层
jingshihao 发表于 2017-9-9 10:57
嗯,应该是正解,是返回最大树的高度吗

对的。字数字数字数
回复 支持 反对

使用道具 举报

bauer 发表于 2017-9-9 13:10:06 | 显示全部楼层
第三题是树的最高高度。开辟一个高度数组,遍历原数组的时候,如果发现是最高级捕食者(-1),跳过。如果是被捕食者,就更新他的捕食者的高度,并且需要递归更新。最后返回最高级捕食者的高度就可以了。通过了全部test case,但不清楚有没有更优解。
回复 支持 反对

使用道具 举报

skia48 发表于 2017-9-10 06:58:40 | 显示全部楼层
不愧为是做教育的公司啊~ 他们家好喜欢出有关数学的编程题
回复 支持 反对

使用道具 举报

天空无语 发表于 2017-9-13 13:09:32 | 显示全部楼层
bauer 发表于 2017-9-9 13:10
第三题是树的最高高度。开辟一个高度数组,遍历原数组的时候,如果发现是最高级捕食者(-1),跳过。如果是 ...
. visit 1point3acres.com for more.
没有考虑存在loop的情况吗? 1->2 2->3 3->1
回复 支持 反对

使用道具 举报

bauer 发表于 2017-9-13 13:45:26 | 显示全部楼层
天空无语 发表于 2017-9-13 13:09
没有考虑存在loop的情况吗? 1->2 2->3 3->1
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
题目要求不会有的吧我记得,捕食关系不会出现环的。
回复 支持 反对

使用道具 举报

天空无语 发表于 2017-9-13 14:06:41 | 显示全部楼层
bauer 发表于 2017-9-13 13:45. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
题目要求不会有的吧我记得,捕食关系不会出现环的。

这个面经里说的一个group里元素互不为direct or indirect predator, 意思是不能是parent 和 grandparent 的意思吗? 看别的面经里面貌似是只要是一条食物链上的都不行。。哪个是对的呢
回复 支持 反对

使用道具 举报

hanhandai 发表于 2017-9-14 03:26:33 | 显示全部楼层
这家我投了3次都不给OA。。。
回复 支持 反对

使用道具 举报

bauer 发表于 2017-9-14 10:57:15 | 显示全部楼层
天空无语 发表于 2017-9-13 14:06
这个面经里说的一个group里元素互不为direct or indirect predator, 意思是不能是parent 和 grandparent ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可以理解为树的逐层遍历?每一层一个group就可以
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 18:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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