一亩三分地论坛

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

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

Facebook 一面

[复制链接] |试试Instant~ |关注本帖
zengweiyi1994 发表于 2016-2-17 08:12:45 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 实习@Facebook - 内推 - 技术电面 |Other其他

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

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

x
先说一个你最近做的project, 遇到了什么比较难得问题~
code:

1.判断一个数组是否是一直递增或者一直递减的,如果是,return true. other else, return false
2.Best time to buy and sell stocks
3.反向输出一个链表的值




评分

1

查看全部评分

本帖被以下淘专辑推荐:

Jester_Z 发表于 2016-2-17 11:19:20 | 显示全部楼层
请问楼主 这个判断递增还是递减的 是什么思路呢  只能想到o(n)的  
不知道怎么二分~
回复 支持 反对

使用道具 举报

JamesJi 发表于 2016-2-17 11:25:18 | 显示全部楼层
Jester_Z 发表于 2016-2-16 22:19
请问楼主 这个判断递增还是递减的 是什么思路呢  只能想到o(n)的  
不知道怎么二分~

同理find peak element
回复 支持 反对

使用道具 举报

 楼主| zengweiyi1994 发表于 2016-2-17 11:31:38 | 显示全部楼层
只问到了O(n),就到下一题了。。所有代码只问了20分钟,然后就让我问问题了~~~
回复 支持 反对

使用道具 举报

 楼主| zengweiyi1994 发表于 2016-2-17 11:32:00 | 显示全部楼层
Jester_Z 发表于 2016-2-17 11:19
请问楼主 这个判断递增还是递减的 是什么思路呢  只能想到o(n)的  
不知道怎么二分~

只问到了O(n),就到下一题了。。所有代码只问了20分钟,然后就让我问问题了~~~
回复 支持 反对

使用道具 举报

yzkst06100 发表于 2016-2-17 11:38:47 | 显示全部楼层
楼主什么时候内推的呀,大约等了几久?
回复 支持 反对

使用道具 举报

 楼主| zengweiyi1994 发表于 2016-2-17 11:40:56 | 显示全部楼层
yzkst06100 发表于 2016-2-17 11:38. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主什么时候内推的呀,大约等了几久?

大概两个星期前推得~,推了两天就拿到面试~
回复 支持 反对

使用道具 举报

Jester_Z 发表于 2016-2-17 11:47:24 | 显示全部楼层
zengweiyi1994 发表于 2016-2-17 11:32
只问到了O(n),就到下一题了。。所有代码只问了20分钟,然后就让我问问题了~~~

20分钟就做三道题 好块~~ 楼主加油~
回复 支持 反对

使用道具 举报

Jester_Z 发表于 2016-2-17 11:50:29 | 显示全部楼层
JamesJi 发表于 2016-2-17 11:25
同理find peak element

感觉还是不太一样 比如1,5,2,3,5,7, 8, 9 这个数组 如果用find peak element的办法最后找到的是9 因为9的右边是负无穷 所以9算一个peak
但是如果是这道题 就找不到那个valley的点..因为直接往右边找了.
回复 支持 反对

使用道具 举报

JamesJi 发表于 2016-2-17 11:53:27 | 显示全部楼层
Jester_Z 发表于 2016-2-16 22:50
感觉还是不太一样 比如1,5,2,3,5,7, 8, 9 这个数组 如果用find peak element的办法最后找到的是9 因为9的 ...

那就设置一个MIN_VALUE一个MAX_VALUE两个boundry就好了
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-17 15:23:29 | 显示全部楼层
第一题必须o(n) 吧 一个loop 就行了 还能优化?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-17 15:34:02 | 显示全部楼层
个人愚见:第一题如果数组是随机的,只能是O(n)的方法。如果你跳过任何一个,都无法得出valid的结论,所以必须检查所有的元素。
回复 支持 反对

使用道具 举报

面无表情 发表于 2016-2-18 04:00:14 | 显示全部楼层
同意楼上,感觉必须O(n),楼主可以细讲讲怎么logn嘛?
回复 支持 反对

使用道具 举报

 楼主| zengweiyi1994 发表于 2016-2-19 02:04:59 | 显示全部楼层
面无表情 发表于 2016-2-18 04:00
同意楼上,感觉必须O(n),楼主可以细讲讲怎么logn嘛?

额。。楼主只做了O(n), 这道题并没有 follow up~
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-2-19 02:07:42 | 显示全部楼层
如果限定条件相邻只能+-1,则可以logn解决。否则目测是O(n)
回复 支持 反对

使用道具 举报

linlin1990 发表于 2016-2-20 06:06:39 | 显示全部楼层
什么结果什么结果
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-20 06:13:24 | 显示全部楼层
zxl9171 发表于 2016-2-19 02:07
如果限定条件相邻只能+-1,则可以logn解决。否则目测是O(n)

相邻只能+-1的话,似乎也不能确保能Log N解决。请问下你的思路是?
回复 支持 反对

使用道具 举报

woshixuyoudan 发表于 2016-3-1 09:15:04 | 显示全部楼层
zxl9171 发表于 2016-2-19 02:07
如果限定条件相邻只能+-1,则可以logn解决。否则目测是O(n)

如果是+-1的话O(1)就可以了
回复 支持 反对

使用道具 举报

valleyvalley 发表于 2016-3-2 07:12:43 | 显示全部楼层
怎么我以为第一题的意思是,符合要求的数组是类似于1,2,3,4 或者5,3,2,0这种。。。所以楼主这道题是说一个数组,一段递增一段递减也可以吗?还是别的我没理解?。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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