一亩三分地论坛

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

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

G家onsite面经02/05

[复制链接] |试试Instant~ |关注本帖
L纪翔L 发表于 2015-2-25 08:09:16 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Other

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

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

x
来发题攒人品,5轮技术面试

. 鍥磋鎴戜滑@1point 3 acres
1. LRU, 讨论了为啥要用cache,什么情况下用
2. 德州扑克
  we have n cards, four suites (H, C, D, S). 1<=value<=13, we have the following hands type:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
      Straight flush      Four of a kind      Full house      Flush       Straight      Three of a kind      Two pair       One pairQuestions: given n cards, and find out the best hands type we could have, n is not 52. and the output does not have to be five. 如果你找到three of a kind,但是没有找到比它更大的了,那这三张就是Output3. 排队题:一群人在排队,中途突然散开了,过了一会儿要重新回到原来在队伍里面的位置,输入就是一个List of people object (没有任何顺序,可以想成就是给你一堆Object),每一个object包含两个信息:自己的身高height, 队伍里面前面比自己高的人数:numOfTaller。 输出要求是原来队伍怎么排列的,这道题我只想到一个O(n^2)的解法,欢迎大家讨论一下4. 进制转换, 十进制转换为any进制,会给一个base input5. 给你一个很长的整数数列(1 million), 有一个a query(start, end), you need to return the maximum value of array[start] - > array[end]. we have enough memory, so dont bother that, just want the query to be very quick. The orginal array structure can not be modified. 基本上是需要你Pre-compute一些东西,他不断的要求优化,简单的存入previous results (start, end)还加一些pre-compute。祝大家好运!


补充内容 (2015-4-1 04:45):
补充一下第三题,不是队伍里面比自己高的人数,是队伍前面比自己高的人数

评分

1

查看全部评分

本帖被以下淘专辑推荐:

ryancooper 发表于 2015-2-27 12:54:28 | 显示全部楼层
最后一题是经典的RMQ问题,简单一点的话可以在O(nlogn)的时间preprocess,然后每次query都是常数。
使用复杂的复合方法的话可以在O(n)的时间内preprocess完,然后每次query也是常数
回复 支持 1 反对 1

使用道具 举报

houqingniao 发表于 2015-2-25 09:14:29 | 显示全部楼层
Bless 楼主~~
德州扑克不懂,这样会对理解有问题吗。。。
回复 支持 反对

使用道具 举报

 楼主| L纪翔L 发表于 2015-2-25 09:16:53 | 显示全部楼层
houqingniao 发表于 2015-2-25 09:14
Bless 楼主~~
德州扑克不懂,这样会对理解有问题吗。。。

不会,我也不太懂,他给出了rules的,按照这个顺序从大到小的hands type, 让你找n张牌中可能出现的最大的
Straight flush     
Four of a kind 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Full house     
Flush      
Straight      
Three of a kind      
Two pair      
One pair
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-2-25 13:44:59 | 显示全部楼层
L纪翔L 发表于 2015-2-25 09:16
不会,我也不太懂,他给出了rules的,按照这个顺序从大到小的hands type, 让你找n张牌中可能出现的最大 ...
.1point3acres缃
ok,多谢了
回复 支持 反对

使用道具 举报

neomiracle 发表于 2015-2-25 15:12:13 | 显示全部楼层
第5题pre-compute是要计算什么呢,楼主可以说的具体一些不
回复 支持 反对

使用道具 举报

 楼主| L纪翔L 发表于 2015-2-26 02:47:19 | 显示全部楼层
neomiracle 发表于 2015-2-25 15:12
第5题pre-compute是要计算什么呢,楼主可以说的具体一些不

我自己的做法是,把array分成k段,每一段的最大值都pre-compute然后存起来,在计算(start, end)的时候,如果有3段已经计算好了的在这个范围内,我们只需要比较那3段的最大值,需要考虑start/end如果在某一段里面并且没有包含那一段的最大值,就要依次比较那一段的值和中间你找到的最大值,不知道这个是不是他想要的答案,他最后让我写了code
回复 支持 反对

使用道具 举报

neomiracle 发表于 2015-2-26 07:50:27 | 显示全部楼层
L纪翔L 发表于 2015-2-25 13:47
我自己的做法是,把array分成k段,每一段的最大值都pre-compute然后存起来,在计算(start, end)的时候 ...

谢谢楼主的回复,这个解法好巧妙
回复 支持 反对

使用道具 举报

whitenights 发表于 2015-2-26 15:28:14 | 显示全部楼层
  1.         public List<Person> solve(List<Person> data) {
  2.             Comparator<Person> cmp = new Comparator<Person>() {
  3.                 @Override
  4.                 public int compare(Person a, Person b) {
  5.                     if (a.height == b.height) {
  6.                         return 0;
  7.                     }.1point3acres缃
  8.                     return a.height < b.height ? 1 : -1;
  9.                 }
  10.             };
  11.             Collections.sort(data, cmp);
  12.             List<Person> res = new ArrayList<Person>();
    . 1point3acres.com/bbs
  13.             for (int i = 0; i < data.size(); i++) {
  14.                 res.add(data.get(i).order, data.get(i));. 1point 3acres 璁哄潧
  15.             }
  16.             return res;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.         }
复制代码
考虑到List.add()是O(n),复杂度是O(n^2)

补充内容 (2015-2-26 15:28):
不知有没有更好的解法
回复 支持 反对

使用道具 举报

tanis 发表于 2015-2-26 16:07:50 | 显示全部楼层
whitenights 发表于 2015-2-26 15:28. 鍥磋鎴戜滑@1point 3 acres
考虑到List.add()是O(n),复杂度是O(n^2)

补充内容 (2015-2-26 15:28):

有点问题,你新建的ArrayList空间不足会报IndexOutOfBoundsException。还有点求教楼主,如果是相同高度怎么算?
回复 支持 反对

使用道具 举报

samantha_kr 发表于 2015-2-27 02:41:01 | 显示全部楼层
lz最后一题,如果是分段存最大值的话,如果start或者end落在分段的中间不是边界怎么办?
回复 支持 反对

使用道具 举报

rlzth2013 发表于 2015-2-27 03:33:16 | 显示全部楼层
感觉排队那一题是不是可以用counting sort? 总共n个人,有m个人比他高,那他的位置不就是n-m吗?这样只应该O(n)就可以了吧
回复 支持 反对

使用道具 举报

 楼主| L纪翔L 发表于 2015-2-27 07:39:39 | 显示全部楼层
rlzth2013 发表于 2015-2-27 03:33
感觉排队那一题是不是可以用counting sort? 总共n个人,有m个人比他高,那他的位置不就是n-m吗?这样只应该 ...

比他矮的人也有可能在他前面, 所以他的位置不一定是n-m哈我觉得
回复 支持 反对

使用道具 举报

mengxiangjia 发表于 2015-2-27 08:01:44 | 显示全部楼层
我觉得最后一题可以用tree吗,楼主拿到offer了吗
回复 支持 反对

使用道具 举报

 楼主| L纪翔L 发表于 2015-2-27 08:06:42 | 显示全部楼层
samantha_kr 发表于 2015-2-27 02:41
lz最后一题,如果是分段存最大值的话,如果start或者end落在分段的中间不是边界怎么办?
. visit 1point3acres.com for more.
那就要依次比较start到自己那隔边界, end到自己那隔边界,和中间的分段最大值,跟他也讨论了这个的
回复 支持 反对

使用道具 举报

 楼主| L纪翔L 发表于 2015-2-27 08:09:16 | 显示全部楼层
tanis 发表于 2015-2-26 16:07
有点问题,你新建的ArrayList空间不足会报IndexOutOfBoundsException。还有点求教楼主,如果是相同高度怎 ...

前提是没有相同高度的人,还没有到那一步时间就没了。。所以估计是挂在这道题上面了
回复 支持 反对

使用道具 举报

samantha_kr 发表于 2015-2-27 09:14:41 | 显示全部楼层
L纪翔L 发表于 2015-2-27 08:06
那就要依次比较start到自己那隔边界, end到自己那隔边界,和中间的分段最大值,跟他也讨论了这个的

谢谢楼主~~我觉得你答得很好呀。。感觉会有offer!
回复 支持 反对

使用道具 举报

samantha_kr 发表于 2015-2-27 09:16:25 | 显示全部楼层
L纪翔L 发表于 2015-2-27 08:06
那就要依次比较start到自己那隔边界, end到自己那隔边界,和中间的分段最大值,跟他也讨论了这个的

再请问一下,德普那个题输入是怎么给的呢~谢谢!!

补充内容 (2015-2-27 09:34):
如果能大概讲一下思路就最好啦。。本来觉得不难,最后发现还是挺麻烦!

补充内容 (2015-2-27 09:34):
谢谢楼主...
回复 支持 反对

使用道具 举报

tanis 发表于 2015-2-27 09:18:55 | 显示全部楼层
L纪翔L 发表于 2015-2-27 08:09
前提是没有相同高度的人,还没有到那一步时间就没了。。所以估计是挂在这道题上面了

楼主没问题的,他们主要看解题思路和能力,不要求最优解?楼主是在Mountain View面的?
回复 支持 反对

使用道具 举报

pro 发表于 2015-2-27 09:59:34 | 显示全部楼层
排队题,先按身高和比自己比自己高的人数升序排序(即首先考虑身高,身高相同的情况下考虑比自己高的人数),nlogn,然后从队尾开始一个个往前看“前面有几个比自己高”的数据(假设是n),把那个人(假设排在i)移到i+n和i+n+1中间去。只要把“移动和插入”这一步做到logn时间(链表+索引),就可以把整个题在nlongn完成。

最后一题,lz给出的解法在(start,end)的长度小于k的时候基本就是要重算……如果start和end在相邻的两段里也得重算吧。
我的方法是,用自平衡BST存储所有极大值的坐标。每次查询的时候遍历区间内的极大值,取最大的,和区间端点比较后返回。这个方法如果不优化的话最坏情况也基本上和重新算一样。但是可以在建立bst的时候,在各个节点存储子树所有极大值的最大值。这样几乎每次查询就是查bst的复杂度了。


回复 支持 反对

使用道具 举报

ham1989 发表于 2015-2-27 10:08:12 | 显示全部楼层
排队那道题  是不可以这么做 每个 人的位置 初始化 都是0  那么那么他的位置就是 0 + 多少个人在前面。 这如果 每个人身高不同 就可以 O(n) 时间排好序了  , 还有一种情况 就是有人身高相等 那么 需要用一个 hashmap 来存   是否出现过 这身高的人 key 是身高, value 是  上一个这个身高的人出现的位置 那个只要 +1 就是当前的位置。 这样遍历一遍 范今数组里就好了!!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 11:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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