一亩三分地论坛

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

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

bb 电面

[复制链接] |试试Instant~ |关注本帖
苏DsL 发表于 2015-4-1 22:09:24 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Bloomberg - 内推 - 技术电面 |Other在职跳槽

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

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

x
为亚麻发offer攒人品。。。
昨天的bb电面,估计是挂了。

先吐槽一下烙印,我到现在面的大公司有gg,亚麻,epic加昨天的bb,一共接触了gg一个烙印,亚麻4轮3个烙印,bb又是烙印,这是闹哪样?就算是去过印度也不能不把我当外人阿。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦

昨天这个烙印口音还行,一上来聊了一会我目前的工作。两个题。

1.[1,2,-2 ,1,-2]这样的叫singlecycle把,意思是,从index0开始,index0+array[index0]跳到1,然后index1+array[index1]继续跳,要求是,每个index都跳到,而且最终跳回index0. 题目没见过,一上来看懂题目花了一会时间,然后讲思路,我感觉电话的时候我表达能力归0了,讲不清楚,磨磨蹭蹭的边讲边写,后来我就直接上代码了,hashset解决,做完差不多30多分钟了,烙印说对的,然后问复杂度,时间空间都是O(n), 尼玛烙印还不满意,要求空间O(1),继续做,就想到用count来计数,count=array.length的时候检查当前index是否在0,结果烙印又给了个edge case[3, x, y, -3],想了半天,没能解决,这个时候已经50分钟了,烙印说算了,下一个题。

2. bst,给一个double数字n,要求找到bst里面跟这个数字最接近的节点,尼玛又没见过,然后就按照二叉树查找做,求当前节点和left与n的差值,取小的,烙印打断说不对,5,5.left=3, 3.right=4,  n=4.2这个时候确实就不对了,当时时间不够了,开始紧张起来,越紧张越没思路。。。最后时间不够了,烙印给了点提示,说的太快没听懂,后来就跟烙印说,维护一个最接近的值,往下面遍历,如果这个值开始变大了就输出之前那个。代码没写。

时间不够了,就让我问了几个问题,就结束了。估计是跪了。

现在感觉自己最大的问题就是,电面没法纸上或者白板上边写边画给面试官看,自己讲的时候表达不清,然后讲不清,时间慢慢走,自己就急了,有时候头脑就空白了。。。看来得想想办法增强这方面得能力咯

move on把。。大公司渐渐都招满了,看来只能继续苦逼等下半年了。。。
. from: 1point3acres.com/bbs
求米求抚慰。。

评分

1

查看全部评分

 楼主| 苏DsL 发表于 2015-4-1 22:10:16 | 显示全部楼层
求大神指点这两个题- -
回复 支持 反对

使用道具 举报

mrno5zzz 发表于 2015-4-1 22:34:02 | 显示全部楼层
我觉得第一题那个count的方法可以啊。如果第一次走到0时, count<length,那肯定不行。然后如果count=length的时候第一次到0就可以了, 可以设置个boolean变量来看是不是第一次
回复 支持 反对

使用道具 举报

 楼主| 苏DsL 发表于 2015-4-1 22:42:23 | 显示全部楼层
mrno5zzz 发表于 2015-4-1 22:34
我觉得第一题那个count的方法可以啊。如果第一次走到0时, count

[3,x, y, -3]就会一直3,-3,3,-3得跳,不满足条件呀
回复 支持 反对

使用道具 举报

mrno5zzz 发表于 2015-4-1 22:53:49 | 显示全部楼层
苏DsL 发表于 2015-4-1 22:42
[3,x, y, -3]就会一直3,-3,3,-3得跳,不满足条件呀

哦,首先遍历一遍数组,给每个元素加上index。[3,x, y, -3]变成[3, x+1, y+2, 0]。 我以为你已经加过了。 这样的话,就是3,0,3,0的跳了
回复 支持 反对

使用道具 举报

pyzhangyi 发表于 2015-4-1 23:35:16 | 显示全部楼层
楼主第一题是让判断一个数组是不是singlecycle吗?如果判断的话比较简单啊,可以设一个bool array,长度和原数组一样长,初始的时候index(0) 设为true,其他都是false。然后设一个变量叫nextIndex = array[0] + 0。 做一个循环 while(!bool[nextIndex]){bool[nextIndex] = true; nextIndex = array[nextIndex] + nextIndex}当跳出循环的时候,如果nextIndex = 0并且bool数组里全是true,就返回true。. 鍥磋鎴戜滑@1point 3 acres
第二题用递归解决。设一个double 变量 diff = root ->val - target. 如果diff为正,那下一次递归用root -> left, 如果diff为负,下一次递归用root -> right.如果diff = 0,直接返回当前root。然后比较
abs(递归返回节点值和target差值) 和 abs(diff),哪个小,就返回哪个节点。
不知道我理解题意对不对。我前阵子刚去BB面试,总体觉得他们面试官都不错,有一个老印还特别好。只可惜自己没能把握上一次机会~
回复 支持 反对

使用道具 举报

YY大帝 发表于 2015-4-1 23:56:26 | 显示全部楼层
苏DsL 发表于 2015-4-1 22:42
[3,x, y, -3]就会一直3,-3,3,-3得跳,不满足条件呀

把跳过的都变0吧,这样跳到0时检查是不是全设成0了
回复 支持 反对

使用道具 举报

 楼主| 苏DsL 发表于 2015-4-2 00:50:56 | 显示全部楼层
pyzhangyi 发表于 2015-4-1 23:35
楼主第一题是让判断一个数组是不是singlecycle吗?如果判断的话比较简单啊,可以设一个bool array,长度和原 ...

第一题follow up是要求空间o(1) 而且不能改数组。。。

第二题确实是我自己当时紧张了,挂了电话之后一想就出来了。。
回复 支持 反对

使用道具 举报

 楼主| 苏DsL 发表于 2015-4-2 00:51:09 | 显示全部楼层
YY大帝 发表于 2015-4-1 23:56
把跳过的都变0吧,这样跳到0时检查是不是全设成0了

不让改数组。。
回复 支持 反对

使用道具 举报

ningchris 发表于 2015-4-2 01:57:57 | 显示全部楼层
楼主你好歹面了两题
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我只面了一题啊

就一个设计题 然后叫我不停地optimize.....大约3个follow up这个样子 倒是给我个算法题啊!
回复 支持 反对

使用道具 举报

ningchris 发表于 2015-4-2 02:11:00 | 显示全部楼层
第一题我感觉楼上的同学已经给出最优解了 不让改数组我也不知道怎么做
回复 支持 反对

使用道具 举报

 楼主| 苏DsL 发表于 2015-4-2 02:34:36 | 显示全部楼层
ningchris 发表于 2015-4-2 02:11
第一题我感觉楼上的同学已经给出最优解了 不让改数组我也不知道怎么做

我觉得如果o(1)应该就必须要改数组了,但是我一改数组他就说no,这里我觉得就是在挖坑。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题确实是自己被自己坑了,表现太差- -
回复 支持 反对

使用道具 举报

pyzhangyi 发表于 2015-4-2 02:42:04 | 显示全部楼层
苏DsL 发表于 2015-4-2 00:50
第一题follow up是要求空间o(1) 而且不能改数组。。。

第二题确实是我自己当时紧张了,挂了电话之后一 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果要求空间是O(1), 就设两个变量, index1和index2, 如果数组是singlecycle,那必需满足array[index1] + index1 = 0,继续往前推,要满足的条件就是array[index2] + index2 = index1。如果没找到,返回false,如果找到的话,那就再找是否有index1满足array[index1] + index1 = index2,终止条件是index1 = array[0] + 0,如果可以满足终止条件,那返回true,不然在loop里会返回false。可是这样一来,每次都要遍历一下数组,时间消耗就大了~
回复 支持 反对

使用道具 举报

pyzhangyi 发表于 2015-4-2 02:42:56 | 显示全部楼层
苏DsL 发表于 2015-4-2 00:50
第一题follow up是要求空间o(1) 而且不能改数组。。。

第二题确实是我自己当时紧张了,挂了电话之后一 ...

如果要求空间是O(1), 就设两个变量, index1和index2, 如果数组是singlecycle,那必需满足array[index1] + index1 = 0,继续往前推,要满足的条件就是array[index2] + index2 = index1。如果没找到,返回false,如果找到的话,那就再找是否有index1满足array[index1] + index1 = index2,终止条件是index1 = array[0] + 0,如果可以满足终止条件,那返回true,不然在loop里会返回false。可是这样一来,每次都要遍历一下数组,时间消耗就大了~
. from: 1point3acres.com/bbs
补充内容 (2015-4-2 02:53):. Waral 鍗氬鏈夋洿澶氭枃绔,
还有就是index1 != index2
回复 支持 反对

使用道具 举报

gzwenyue 发表于 2015-4-26 15:29:53 | 显示全部楼层
我有一个想法,楼主看可行不。 用 count 来记录jump的次数,pos来记录当前位置。所以一共有三种状态,返回0时,count<n, count=n,(n为array长度) 以及永远不返回。 对于第一种情况,明显有元素没遍历到,对于第三种元素,就是有元素遍历的两次,行成了环,这样永远不回出环了。对于第二种情况就是满足要求的singlecycle. 因为如果有非0节点遍历两次及以上,永远都不会再访问0了。所以必然每个节点都是访问一次,所以多有节点都访问到了。
基于以上判断,程序就以pos再次访问到0或者count==n终止。终止时count==n且pos在0上就是满足singlecycle的array,否则不然。
回复 支持 反对

使用道具 举报

 楼主| 苏DsL 发表于 2015-4-27 09:13:51 | 显示全部楼层
gzwenyue 发表于 2015-4-26 15:29
我有一个想法,楼主看可行不。 用 count 来记录jump的次数,pos来记录当前位置。所以一共有三种状态,返回0 ...

感觉很巧诶,我看行~
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-12 04:26:41 | 显示全部楼层
第二题维护一个target以及minDiff,遇到小的minDiff就更新并且存下当前target,把树遍历一遍后返回target就好了
回复 支持 反对

使用道具 举报

yueyub 发表于 2015-12-13 10:33:04 | 显示全部楼层
JamesJi 发表于 2015-12-12 04:26
第二题维护一个target以及minDiff,遇到小的minDiff就更新并且存下当前target,把树遍历一遍后返回target就 ...
-google 1point3acres
不对,你这个是o(n),此题应该log n 求解
回复 支持 反对

使用道具 举报

leonidas1573 发表于 2015-12-13 10:35:52 | 显示全部楼层
yueyub 发表于 2015-12-13 10:33
不对,你这个是o(n),此题应该log n 求解

亲...他的方法是O(h)的.h是树的深度.自然是O(logn)啊.....
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-13 10:40:43 | 显示全部楼层
yueyub 发表于 2015-12-12 21:33
不对,你这个是o(n),此题应该log n 求解

可以说一下你的logn方法吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 04:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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