一亩三分地论坛

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

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

FB 刚电面

[复制链接] |试试Instant~ |关注本帖
sunraincyq 发表于 2014-12-2 12:20:13 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 博士 全职@Facebook - 猎头 - 技术电面 |Other

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

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

x
平时在版上经常看大家的面经,今天也来贡献下。预定的时间一个中国大哥打过来,直接上来问你会什么语言,做网站的技术会什么,然后问了下我做的项目。
开始做题。
1. is valid palindrome-google 1point3acres
2. find the maximum number in an integer array. The numbers in the array increase first, then decreases. Maybe there’s only increase or decrease. 先说了直接扫一遍,是O(n), 然后用binary search 就是O(log n).最后时间不够,没写完,应该是挂了。. 鍥磋鎴戜滑@1point 3 acres

太弱了,这是我半年以来的第一个技术电面,明显和自己平时做题不一样,脑袋有点空白的感觉,卡住了,结束后一想这题根本就不难。真的应该多练习自己说,然后总结。在这里求想一起练习的同学,可以互相出题,限时,用英文。感兴趣请站内信。

评分

3

查看全部评分

cauchyc 发表于 2014-12-3 04:07:43 | 显示全部楼层
FB真心业界良心,全是leetcode原题...
回复 支持 1 反对 0

使用道具 举报

houqingniao 发表于 2014-12-2 13:32:41 | 显示全部楼层
bless。 中国大哥不一定挂~~
回复 支持 反对

使用道具 举报

zhongneu 发表于 2014-12-3 04:04:37 | 显示全部楼层
What if there are duplicates in the second question? Can we still do it in O(logN)?
回复 支持 反对

使用道具 举报

zhongneu 发表于 2014-12-3 04:04:45 | 显示全部楼层
What if there are duplicates in the second question? Can we still do it in O(logN)?
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-12-3 04:22:03 | 显示全部楼层
我做过第二题。 没做过比较难写出正确的binary search。    楼主运气不大好.  
回复 支持 反对

使用道具 举报

3319233 发表于 2014-12-3 04:27:08 | 显示全部楼层
leetcode最新原题?好像是
回复 支持 反对

使用道具 举报

ptepte 发表于 2014-12-6 02:24:42 | 显示全部楼层
在这里求想一起练习的同学,可以互相出题,限时,用英文。感兴趣请站内信。
.鏈枃鍘熷垱鑷1point3acres璁哄潧

楼主还在找人练习么? 求加入!!!
回复 支持 反对

使用道具 举报

 楼主| sunraincyq 发表于 2014-12-8 01:08:36 | 显示全部楼层
houqingniao 发表于 2014-12-1 23:32. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
bless。 中国大哥不一定挂~~

唉,已经挂了,答的不好。
回复 支持 反对

使用道具 举报

 楼主| sunraincyq 发表于 2014-12-8 01:09:16 | 显示全部楼层
zhongneu 发表于 2014-12-2 14:04
What if there are duplicates in the second question? Can we still do it in O(logN)?

最大值没有DUPLICATE, 其他数字可能有,不过不妨碍
回复 支持 反对

使用道具 举报

kongkonglin 发表于 2014-12-8 17:17:46 | 显示全部楼层
是跟leetcode一样的那个sorted array shift产生的array求最大值?还是如楼主所说的先增大后减小?如果是后者,没办法用binary search吧?. 鍥磋鎴戜滑@1point 3 acres
如 case1:1,2,3,4,2,1
    case2:1,2,4,3,2,1
这些情况都没办法判断啊。
回复 支持 反对

使用道具 举报

 楼主| sunraincyq 发表于 2014-12-8 22:45:26 | 显示全部楼层
kongkonglin 发表于 2014-12-8 03:17
是跟leetcode一样的那个sorted array shift产生的array求最大值?还是如楼主所说的先增大后减小?如果是后者 ...
. 1point3acres.com/bbs
后一种情况,先增大再减小。用RECURSION然后类似BINARY SEARCH,不过需要多加CHECK来判断找哪边。
回复 支持 反对

使用道具 举报

jidhuang 发表于 2014-12-8 22:46:58 | 显示全部楼层
kongkonglin 发表于 2014-12-8 17:17
是跟leetcode一样的那个sorted array shift产生的array求最大值?还是如楼主所说的先增大后减小?如果是后者 ...

如果把A[mid] 和 A[mid-1] 比较 不就能知道当前是增序列还是减序列了吗,贴一个代码求轻拍:
def findMax(self, num):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        L = 0. 鍥磋鎴戜滑@1point 3 acres
        R = len(num)-1.鏈枃鍘熷垱鑷1point3acres璁哄潧
        while L < R:
            M = int((L+R)/2)-google 1point3acres
            if not (num[M] > num[L] and num[M] > num[R]):. 1point 3acres 璁哄潧
                return max(num[L],num[R])
            if num[M] > num[M-1] and num[M] > num[M+1]: # reach maximam
                return num[M]
            elif num[M] > num[M-1]: # left array is monotonic increasing
                L = M+1
            else: # right array is monotonic decreasing
                R = M-1
        return max(num[L],max(num[R],num[M]))
回复 支持 反对

使用道具 举报

zhongneu 发表于 2014-12-17 14:29:46 | 显示全部楼层
sunraincyq 发表于 2014-12-8 01:09
最大值没有DUPLICATE, 其他数字可能有,不过不妨碍

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1

can we use binary search to do it in O(logN)?
回复 支持 反对

使用道具 举报

wksora 发表于 2014-12-19 09:57:37 | 显示全部楼层
sunraincyq 发表于 2014-12-8 01:08
唉,已经挂了,答的不好。

楼主你好,她们是直接发的拒信么?隔了多久?非常感谢如果能告知。
回复 支持 反对

使用道具 举报

wksora 发表于 2014-12-19 09:57:44 | 显示全部楼层
sunraincyq 发表于 2014-12-8 01:08. 1point3acres.com/bbs
唉,已经挂了,答的不好。

楼主你好,她们是直接发的拒信么?隔了多久?非常感谢如果能告知。
回复 支持 反对

使用道具 举报

 楼主| sunraincyq 发表于 2014-12-19 13:16:41 | 显示全部楼层
wksora 发表于 2014-12-18 19:57
楼主你好,她们是直接发的拒信么?隔了多久?非常感谢如果能告知。

就两天左右时间,HR给我发的邮件
回复 支持 反对

使用道具 举报

wksora 发表于 2014-12-22 09:35:35 | 显示全部楼层
sunraincyq 发表于 2014-12-19 13:16
就两天左右时间,HR给我发的邮件

谢谢~ 祝你后面好运。
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-12-22 09:46:03 | 显示全部楼层
zhongneu 发表于 2014-12-17 14:29
1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1.1point3acres缃
. from: 1point3acres.com/bbs
can we use binary search to do it in O(logN)?

我觉得有duplicates的话 worst case是O(n)
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-12-22 09:48:23 | 显示全部楼层
jidhuang 发表于 2014-12-8 22:46
如果把A[mid] 和 A[mid-1] 比较 不就能知道当前是增序列还是减序列了吗,贴一个代码求轻拍:
def findMax ...
. 1point3acres.com/bbs
你这个会array index out of bound吧?
L = 0, R = 1, M = 0
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 03:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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