一亩三分地论坛

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

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

2.17 GOOGLE ONSITE 跪经 求分

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

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
EE转专业狗刷了N久的题准备google, 还是跪在Onsite了,来贡献一下面经
提早一天飞到san jose,给安排的房间那个床so fancy,左右两边独立调软硬,然并卵,几乎失眠的一夜第二天来到CL1300, 也就是google infrastructure部门, 没啥warm up,直接上题,题也都很裸

第一轮:
1. 实现一个class, 支持 get(key),   put(key, value),delete(key), getRandom()四个操作。用了hashmap 跟 Arraylist, 删除时候跟队尾swap一下达到 四个O(1)
2. A="abcde" B="abcxde" 除了x其他字符都一样 找出那个x


第二轮:
1. longest substring at most K distinct char. 高频题,快慢指针+hashmap计数。 优化点做法就是用双向链表类似LRU的方法做,hashmap不计数,只用来更新每个char最后的位置,更新时把结点拉到LRU的tail并删除head。
2. 一个list, 含有k个数,然后给N, 让等概率的从1-N里选出不在list里的数。 这题一下子问懵了,纠结半天怎么算那个等概率。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第三轮:
午饭后整个人都不在状态,来了一道看起来很简单的数组查询题,就是一个sorted array,若干位置是空的,给一个target求第一个比target小的position. LZ直接开写 binary search, 结果发现坑挺多,遇到空位置移动指针的时候怎么都有bug, 最终还是没能写出能work的代码,这题看着简单写起来不容易,也许上来应该先写个O(N)的理一下思路。这一轮一定被给了低分。

. more info on 1point3acres.com
第四轮:
多叉树序列化反序列化,写的磕磕绊绊。。这道刷题刷漏了,结果偏偏考到,真是验证墨菲定律



. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
祝小伙伴们好运 拿下google offer多多 求分求分~~~      

评分

4

查看全部评分

pengzewen37 发表于 2016-3-28 23:11:21 | 显示全部楼层
adiggo 发表于 2016-3-25 14:58
第三题 array是空 需要跳过去, 如果mid 的value的空, 那么该往左移动index, 直到找到第一个不是空的, ...

感觉这道题,就是讨论,最后复杂度还是O(n)
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-3-19 15:51:00 | 显示全部楼层
http://stackoverflow.com/questions/6979276/select-random-value-not-in-array
回复 支持 1 反对 0

使用道具 举报

stony0408 发表于 2016-2-27 11:36:57 | 显示全部楼层
不是在白板上写吗?
回复 支持 反对

使用道具 举报

 楼主| jmnjmnjmn 发表于 2016-2-27 11:54:33 | 显示全部楼层
stony0408 发表于 2016-2-27 11:36
不是在白板上写吗?

是白板写~
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-27 12:22:31 | 显示全部楼层
概率其实挺简单 如果我理解正确。 就是随机从N里选一个数直到不在那个list里。
回复 支持 反对

使用道具 举报

cicitaotao 发表于 2016-2-27 12:27:27 | 显示全部楼层
lz有送hc吗
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-2-27 14:57:39 | 显示全部楼层
那个binary search题目 是求从左向右还是从右向左数第一个比target小的index 啊?
从左向右数
int getPosition(int a[], int n, int target) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
   int left = 0, right = n - 1, middle, result = -1;
. more info on 1point3acres.com
   while (left <= right) {
       middle = left + (right - left) / 2;
      
       if (a[middle] >= target)
            right = middle - 1;
      else {.鏈枃鍘熷垱鑷1point3acres璁哄潧
            result = middle;
            right = middle - 1;
      }
   }

   return result;
}. From 1point 3acres bbs

从 右向左数. 鍥磋鎴戜滑@1point 3 acres
int getPosition(int a[], int n, int target) {
   int left = 0, right = n - 1, middle, result = -1;

   while (left <= right) {
       middle = left + (right - left) / 2;
      
       if (a[middle] >= target)
            right = middle - 1;
      else {
            result = middle;
            left = middle + 1;
      }
   }

   return result;
}
回复 支持 反对

使用道具 举报

 楼主| jmnjmnjmn 发表于 2016-2-27 17:10:56 | 显示全部楼层
duduhaha 发表于 2016-2-27 14:57-google 1point3acres
那个binary search题目 是求从左向右还是从右向左数第一个比target小的index 啊?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
从左向右数. Waral 鍗氬鏈夋洿澶氭枃绔,
int getPosi ...
. 1point 3acres 璁哄潧
从小到大排序的 所以是从左边第一个咯 然后array里空的index记得要跳过去
回复 支持 反对

使用道具 举报

 楼主| jmnjmnjmn 发表于 2016-2-27 17:11:32 | 显示全部楼层
kinggarden2001 发表于 2016-2-27 12:22.鐣欏璁哄潧-涓浜-涓夊垎鍦
概率其实挺简单 如果我理解正确。 就是随机从N里选一个数直到不在那个list里。

是的 后来就想到了 当时不知怎么脑子就跟浆糊一样
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-2-27 17:58:11 | 显示全部楼层
请问楼主面完以后多就知道HC的消息啊,祝楼主找工顺利!!!
回复 支持 反对

使用道具 举报

liuzhe1218 发表于 2016-2-28 01:54:55 | 显示全部楼层
求教概率那题还有二分查找包含空的那题有什么好办法嘛?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-28 09:00:20 | 显示全部楼层
题目都很常规啊
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-3-21 07:47:37 | 显示全部楼层
kinggarden2001 发表于 2016-2-27 12:22. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
概率其实挺简单 如果我理解正确。 就是随机从N里选一个数直到不在那个list里。

概率那题是不是要先把list 遍历一遍把数存进hash. 这样免得每次生成随机数之后,还得花O(n)去判断那个数是否在list中?
回复 支持 反对

使用道具 举报

xblwyc 发表于 2016-3-21 16:17:54 | 显示全部楼层
概率那题应该是用二分来解得,因为一般来讲N会给的极大,K应该是个合理的数字。
可以考虑把每一个禁止的数都从右边填上相应的数,比如N = 4,list= {1,3},数组就应该是{2,4,X,X},那么随机生成[0,N - k)范围的数,然后output对应位置的数即可。
因为又不可能将每一位的具体数字求出来,所以我现在只想到了用二分 + 二分的O(lgNlgK)的解法。第二个二分用来计算<=该值得list中的数有多少个
回复 支持 反对

使用道具 举报

夜辉冥 发表于 2016-3-23 01:30:54 | 显示全部楼层
longest substring at most K distinct char 楼主这题的优化是怎么做的没太明白。如果你只记录最后一个出现这个char的序号,如果出现这种情况怎么办?
1112223 k=2
回复 支持 反对

使用道具 举报

 楼主| jmnjmnjmn 发表于 2016-3-26 03:42:03 | 显示全部楼层
夜辉冥 发表于 2016-3-23 01:30
longest substring at most K distinct char 楼主这题的优化是怎么做的没太明白。如果你只记录最后一个出现 ...

LRU的size不超过k的时候,慢指针不用动,快指针往前走,减一减就是substring长度
快指针走到3的时候,更新完LRU size会超过2,这个时候慢指针指到LRU头结点存的idx,再删掉LRU头
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-3-26 03:58:33 | 显示全部楼层
jmnjmnjmn 发表于 2016-2-27 17:10
从小到大排序的 所以是从左边第一个咯 然后array里空的index记得要跳过去

第三题 array是空 需要跳过去, 如果mid 的value的空, 那么该往左移动index, 直到找到第一个不是空的, 与target比较大小, 如果小于target, left = mid+1, 大于target, right = index-1, 当然也有特殊情况, 如果index == left 了 并且是空,应该直接设为left = mid + 1, 但是 这样的running time 在最差情况下 是O(n)吧。
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-3-26 04:03:58 | 显示全部楼层
jmnjmnjmn 发表于 2016-2-27 17:10
从小到大排序的 所以是从左边第一个咯 然后array里空的index记得要跳过去
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
另外 空的位置 是随机的么, 还是连在 一块的?
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-18 03:10:07 | 显示全部楼层
3, binary search, 就是注意下如果是mid=empty, 先search右边, 找不到再search左右;如果是mid>=target, search左边;如果是mid<target, search右边找不到的话,return mid
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 02:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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