一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2979|回复: 15
收起左侧

阅后即焚onsite

[复制链接] |试试Instant~ |关注本帖
zhuol 发表于 2015-4-7 23:11:16 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Snapchat - 网上海投 - Onsite |Fail在职跳槽

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

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

x
已跪, 发面经造福大家。
第一轮, n叉树判断是否有回路,dfs, 但是不希望一直维护一个祖先节点的哈希表,所以可以设计一个类,里面存一个布尔型的变量,访问过的设为true,回溯之后设为false
第二轮, rotate过的数组排序,nlogn找出最小值,o(n)时间构造新的数组
第三轮, 高精度加法,follow up可以是负数,多加一个高精度减法
第四轮, 一堆数,中间插入*,+或者括号,求最大值,dp就可以, 但是如果数字全部是正整数的话,只用通过判断1的个数是奇数还是偶数来求最大值,0(n)就可以了
               merge n个排序过的数组,优先队列或者divide and merge都可以. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
               简单的regax判断是否match
. Waral 鍗氬鏈夋洿澶氭枃绔,
第四轮做的有点多。。。不过都做出来了。。但是最后还是跪了。。。无念。。。and move on
希望对大家有帮助. Waral 鍗氬鏈夋洿澶氭枃绔,


评分

5

查看全部评分

 楼主| zhuol 发表于 2015-4-7 23:37:40 | 显示全部楼层
YY大帝 发表于 2015-4-7 23:26
请问LZ第四轮如果数字全为正,为什么要判断1的个数?

我说的不是很清楚,其实是连续的1, 比如这样1 1 1 1 1 1
其实只有1是特殊的,如果是大于1的正整数直接乘就好了,但是1的话就是要看情况来做加法,上面的例子其实可以这样看(1+1)(1+1)(1+1) 或者(1+1+1)(1+1+1),就是偶数个1的连加和奇数个,其实就是连着俩或者连着仨,其实更多的dp过程中会算到的。

无耻的打个广告的。。这里有算法, 直接看代码可能更清楚点
http://www.lostscroll.com/max-value-using-and/

补充内容 (2015-4-7 23:38):
但是如果有小数的话,比如double a>0就不适用了,只能正常的dp了
回复 支持 1 反对 0

使用道具 举报

YY大帝 发表于 2015-4-7 23:26:52 | 显示全部楼层
请问LZ第四轮如果数字全为正,为什么要判断1的个数?
回复 支持 反对

使用道具 举报

Olivia0624 发表于 2015-4-8 11:03:10 | 显示全部楼层
问下第二轮,rotate过的数组是不止一次rotate吗?如果只有rotate一次不是O(logn)就可以找到最小值么。。为啥要O(nlogn)。。
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-8 11:06:48 | 显示全部楼层
lz最近面了好多牛公司啊。。。还一边上班一边面的,膜拜死了
回复 支持 反对

使用道具 举报

 楼主| zhuol 发表于 2015-4-8 11:16:14 | 显示全部楼层
Olivia0624 发表于 2015-4-8 11:03
问下第二轮,rotate过的数组是不止一次rotate吗?如果只有rotate一次不是O(logn)就可以找到最小值么。。为 ...

我是想说logn的。。。打错了。。
回复 支持 反对

使用道具 举报

 楼主| zhuol 发表于 2015-4-8 11:17:30 | 显示全部楼层
yuxrose 发表于 2015-4-8 11:06
lz最近面了好多牛公司啊。。。还一边上班一边面的,膜拜死了

二连跪。。。悲催的一比
回复 支持 反对

使用道具 举报

Olivia0624 发表于 2015-4-8 11:20:29 | 显示全部楼层
zhuol 发表于 2015-4-7 22:16
我是想说logn的。。。打错了。。

恩恩那就行了~想半天为毛要多个n。。还以为理解错题意了。。. Waral 鍗氬鏈夋洿澶氭枃绔,
祝LZ早日拿大offer~
回复 支持 反对

使用道具 举报

 楼主| zhuol 发表于 2015-4-8 11:28:03 | 显示全部楼层
Olivia0624 发表于 2015-4-8 11:20
恩恩那就行了~想半天为毛要多个n。。还以为理解错题意了。。
祝LZ早日拿大offer~
.鐣欏璁哄潧-涓浜-涓夊垎鍦
上帝保佑 阿弥陀佛啊
回复 支持 反对

使用道具 举报

minglotus 发表于 2015-4-8 12:10:11 | 显示全部楼层
请问第一轮里,n叉树判断是否有回路可以用拓扑排序来做么?
回复 支持 反对

使用道具 举报

 楼主| zhuol 发表于 2015-4-8 12:41:07 | 显示全部楼层
minglotus 发表于 2015-4-8 12:10. 1point3acres.com/bbs
请问第一轮里,n叉树判断是否有回路可以用拓扑排序来做么?

应该也可以,不过要求尽量少用额外空间的说
回复 支持 反对

使用道具 举报

hesha0987 发表于 2015-5-9 13:25:11 | 显示全部楼层
诚心求问第四轮 “一堆数,中间插入*,+或者括号,求最大值,dp就可以, 但是如果数字全部是正整数的话,只用通过判断1的个数是奇数还是偶数来求最大值,0(n)就可以了” 这个题怎么做
回复 支持 反对

使用道具 举报

hit_piggy 发表于 2015-5-10 10:54:43 | 显示全部楼层
请问lz,第二题造新的数组是in-place吗。。还是new一个新的array,一个一个copy过去?
回复 支持 反对

使用道具 举报

 楼主| zhuol 发表于 2015-5-20 22:54:56 | 显示全部楼层
hit_piggy 发表于 2015-5-10 10:54
请问lz,第二题造新的数组是in-place吗。。还是new一个新的array,一个一个copy过去?

都可以啊,不想新开一个数组就翻转3次就好了嘛
比如4567123, 先整个翻转变成3217654, 然后翻转第一部分1237654, 然后翻转第二部分便曾1234567
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-5-22 06:23:17 | 显示全部楼层
zhuol 发表于 2015-4-7 23:37
我说的不是很清楚,其实是连续的1, 比如这样1 1 1 1 1 1
其实只有1是特殊的,如果是大于1的正整数直接 ...
. visit 1point3acres.com for more.
没看懂你的那个solution 2, 为什么只考虑k[i - 3]就行了,k[i- 4] 以后的情况不用考虑了吗?
回复 支持 反对

使用道具 举报

 楼主| zhuol 发表于 2015-5-22 21:45:41 | 显示全部楼层
mkcing 发表于 2015-5-22 06:23
没看懂你的那个solution 2, 为什么只考虑k就行了,k 以后的情况不用考虑了吗?

其实是不用的,你可以找几个数试一试,其实当四个一连续的时候就退化为22组合,5个连续的时候就退化为23组合为最优解
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 15:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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