一亩三分地论坛

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

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

狗家Onsite

[复制链接] |试试Instant~ |关注本帖
tj474474 发表于 2016-11-17 13:01:09 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Failfresh grad应届毕业生

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

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

x
11/1 onsite也过了两个礼拜 上周接到电话还是跪了
. 1point 3acres 璁哄潧也差不多该整理心情来检讨一下当时的题目
我感觉运气蛮好的四轮都是不怎么难题

第一轮看脸感觉是个韩国小哥,一路不怎么跟我沟通这轮面的很吃力题也是四轮里面我感觉最难的
. Waral 鍗氬鏈夋洿澶氭枃绔,
这题分成三个部分都是基于一个integer的data stream
第一题是问说给定一个integer n有没有曾经在data stream里面出现过

这里我就用个HashMap纪录曾经出现过的integer然后有k进来的时候就去看有没有在map里. 1point 3acres 璁哄潧
. from: 1point3acres.com/bbs
第二题是同样的input n但是只考虑过去的k个element里面有没有出现n

这里我是用了个Queue去纪录过去的k个元素,当Queue的长度到了k之后就pop掉第一个的元素,同时如果是有曾经出现过的元素在Queue里面出现了还要把它挪到Queue的后头,找到Queue的方是就是用,感觉有点像是LRU的概念,但是我没有自己implement doublely linked list这个复杂度应该是O(n)了. 1point 3acres 璁哄潧
因为当有新的element进来的时候,透过Map就算可以找到该element在Queue当中的node还是没办法直接O(1) remove的

第三小问才是最难的,同样的input n,要找过去k个element里面存不存在integer i st.
|n - i| <= v
v等于是这个题目的第三个input. From 1point 3acres bbs
想像成
boolean checkExist(int n, int k, int v)

我当时想的办法是原先用来记载元素的HashMap改成用TreeMap,这样就可以直接用TreeMap去ceiling跟flooring去看一个range里面有没有存在node。

我感觉面试官非常不喜欢我的解法,从第二小题就感觉走错方向了。毕竟多维持一个queue还要回头维持map就有很多要细节感觉我都没有写好。

想看看大家对于这轮有没有更好的建议

第二轮大概是一个越南大马或泰国的妹子
题目是design一个class可以判断一个围棋的棋子是不是被围住了
经过一番讨论之后决定就是implement一个function在假定棋盘已经摆放很多旗子的情况下,给定任何一个位置跟那个位置的颜色(黑子或白子)判断一下那个棋是不是被包围了。
这题其实就是个DFS,但是就是要同时考虑input可能是两种颜色,然后还有可能是空格,还有边界。整体来讲,我思路大概是对的,但是code写得很乱,觉得这轮应该也没办法拿到strong positive。

第三轮是一个在Map组工作很久的美国人
一上来就先问了我整整大概20分钟的behavioral。其中一个比较有趣的问题是,他说如果他现在打电话给我intern的manager,他会如何形容我。大家参考一下哈哈 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 1point 3acres 璁哄潧
题目很简单.鏈枃鍘熷垱鑷1point3acres璁哄潧
就说如果给你一个字符串 char[]
"This is a dog" 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
就是很多个中间有至少一个以上的空格
类似这样要把它变成
"This is a dog "
就是一个two pointer的问题去解就好了,一开始想的有点复杂,稍微花多了一点时间,然后写出来的时候时间差不多就用完了。但是面试官感觉还是挺满意的,原本期待这轮可以拿个Strong positive,但是或许是题目太简单了吧...
. Waral 鍗氬鏈夋洿澶氭枃绔,
第四轮是一个穿着运动服的美国小哥感觉才刚从外面踢完足球回来
基本上就是一个
Number of Island ||
但是是要设计整个class,能够支持快速地知道当下有几个island,然后还可以随意在任何一个点添加island。

就这个小变动,让我有点乱了方向,竟然决定constructor跟addIsland()写成两个分开的function,都做了差不多的事,最后基本也没时间写到addIsland()。因为在constructor的时候可以只需要看他的上面跟左边就好了,因为之后走到下一个的时候他会回来看左边跟上面。为了这件事情我还花了很多时间说服那个小哥。然后当我在想着要如何实践Union and find纪录parent的那个array的时后,小哥还出来打断我,问说我在干嘛,叫我直接用Union(X, Y) Find(X)这种抽象的interface写一下就好了。把抽象的code塞进真正的java code就变得好混乱,最后又是留了整个白板的烂code。哎

最后会挂掉真的也完全不意外,虽然几乎每一轮我都想出一个解法,但是在白板上coding的熟练度不太够,没办法很简洁地表示出自己的作法吧。
狗家的bar还是好高,光解决问题是没用的,code要快要漂亮才行

补充内容 (2016-11-17 13:03):
第二輪打出來怎麼格式跑掉了
"This    is     a     dog"
就是很多個中間有至少一個以上的空格
類似這樣要把它變成
"This is a dog           "

评分

1

查看全部评分

本帖被以下淘专辑推荐:

zyoppy008 发表于 2016-11-17 16:18:47 | 显示全部楼层
第二轮完全围住定义是啥 围住的中间还有空格算吗 把棋围到一个角落算吗 ? 第一轮第二题 k个element要求distinct吗? 不管怎么样 直接queue加hashmap 每次把queue的头pop掉然后相应在表里的也pop掉不就行吗 重复的push的时候不push 根据k distinct与否决定count加不加一
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-11-18 00:57:13 | 显示全部楼层
zyoppy008 发表于 2016-11-17 16:18
第二轮完全围住定义是啥 围住的中间还有空格算吗 把棋围到一个角落算吗 ? 第一轮第二题 k个element要求dis ...

围棋那题被围住的范围里面还有空格的的话不算围住。另外,被逼到墙角也算是被另外一个颜色包围。

k element那题不要求distinct的。
你这么一说我才想起来我当时好像就是在Map里面存count的。只有count减少到0的时候我才把他从Map里面pop掉。所以我的作法应该是没有什么问题,不用考虑更新queue的情况,每次有新的item进来只要把queue的头pop掉,然后去hashmap里面把它对应的count--,如果等于0从map里面remove掉。

第三小题虽然改成TreeMap但是我也是这么做的。. more info on 1point3acres.com

感谢你的提醒。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-18 01:11:07 | 显示全部楼层
tj474474 发表于 2016-11-18 00:57
围棋那题被围住的范围里面还有空格的的话不算围住。另外,被逼到墙角也算是被另外一个颜色包围。.1point3acres缃

k el ...

楼主 第一轮和LC Contain Duplicate I, II, III一样么?
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-18 01:36:02 | 显示全部楼层
tj474474 发表于 2016-11-18 00:57 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
围棋那题被围住的范围里面还有空格的的话不算围住。另外,被逼到墙角也算是被另外一个颜色包围。. 1point 3acres 璁哄潧

k el ...
. 1point 3acres 璁哄潧
其实可以不用map 用set吧 我的意思是 比如abcadr到r就把a从哈希表删掉 虽然还有一个a也没关系 因为a不可能是n 不然早返回了 个数的话只需要已queue里个数去算就好
回复 支持 反对

使用道具 举报

yangluphil 发表于 2016-11-18 01:36:08 | 显示全部楼层
第一题第三问是不是可以用bucket的思想,bucket大小为v,map<int, int>存(bucketId, num),checkExist先得出n的bucketId再去map里找bucketId, bucketId-1, bucketId+1对应的数里有没有符合条件的值,不想要treemap,还是用hashmap就可以了。不过这个做法需要v is constant across all calls,如果每次v不一样就不知道该怎么做了。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-18 01:38:40 | 显示全部楼层
tj474474 发表于 2016-11-18 00:57
围棋那题被围住的范围里面还有空格的的话不算围住。另外,被逼到墙角也算是被另外一个颜色包围。

k el ...

这样更好 如果碰到重复 不需要加入queue 只需要记一个总count就行
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-18 01:45:08 | 显示全部楼层
tj474474 发表于 2016-11-18 00:57
围棋那题被围住的范围里面还有空格的的话不算围住。另外,被逼到墙角也算是被另外一个颜色包围。
. more info on 1point3acres.com
k el ...

我发现想复杂了。是给定n 不是任意在k里重复的 只需要一个variable记录n的index 就可以呀
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 23:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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