May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 13901|回复: 36
收起左侧

[找工就业] Google 电面面经,已跪

[复制链接] |试试Instant~ |关注本帖
Soviet 发表于 2014-10-25 04:10:48 | 显示全部楼层 |阅读模式

2014(7-9月)-[12]CE硕士+3个月-1年 - 校园招聘会| 码农类全职@Google

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
前天面的,题我感觉不难啊都做出来了不知道为什么还是给拒了。
一个听起来反正不是烙印的面试官打过来的,态度不错,题目是一个coding加一个problem solving
coding:
u = [u1, u2, u3, u4, u5, u6, …] (integers)
=> reorder
s = [s1, s2, s3, s4, s5, s5, …]
s1 <= s2, s2 >=s3, s3 <= s4, s4 >= s5,.....
顺便提供我写的code你们看是不是有啥问题?反正面试官没咋挑毛病。。。
public void sort(int[] u){
    if(u.length<1){return;}

    boolean flag=true;
    for(int i=1;i<u.length;i++){
        if((flag && u[i-1]>u) || (!flag && u[i-1]<u)){
          swap(u,i-1,i);
        }
       flag=!flag;
    }
    return;

}
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
private void swap(int[] A, int i, int j) throwException{
     if(i>A.length-1 || j>A.length-1){return;}
     int tmp=A;
     A=A[j];
     A[j]=tmp;

}

problem solving:
2 player game
- there’s a set of marbles
- take turns removing 1 or 2
- winner removes the last one

- you get decide who goes first
我大概解释下,就是有俩人玩儿个游戏,现在桌上有n个弹球,你和你的对手轮流取,一次一个人只能取1个或2个,把桌面清空的那个人胜利。
你来决定谁第一个取弹球,在不同弹球数量n的情况下,请问你是否能制定出一个必胜策略?
OK以下是我的解答:
先枚举一些case归纳(OP= opponent):
n=1,2 I first  (很显然我可以一次拿完直接胜利)
n=3 OP first   (让对手先拿,他拿一个我就拿俩,他拿俩我就拿一个,最后一定是我赢)
n=4 =1+3 I first  (我先拿一个,然后轮到对手,立马转化为n=3的情况,最后一定是我赢)
n=5 =2+3 I first  (我先拿两个,然后轮到对手,立马转化为n=3的情况,最后一定是我赢)
n=6 =3+3 Op first  (相当于两个n=3 case的重复,此时应该让对手先)
n=7 =1+3+3 I first (这个不用解释了吧)

所以最后归纳出的策略就是:
n=number of sticks
if(n%3==0){OP first}

else{I first}

面试沟通也挺通畅的,时间卡的也不错,两个题都做完刚好43分钟,剩下两三分钟我问点问题就准时结束。。
各位大神看看有没有啥问题啊,反正最后我还是输了。。。



补充内容 (2014-10-25 04:22):
sort() 里面 if 的条件是 if((flag && u[i-1]>u) || (!flag && u[i-1]<u)),复制过去没注意。。

补充内容 (2014-10-25 04:26):
还有那个swap函数,那几句是int tmp=A A=A[j] A[j]=tmp, 帖子里面的typo是我从pdf直接复制粘贴过来造成的错误,我为了留下面经面试一完就把google doc导出pdf了。。不好意思各位没仔细编辑
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2014-10-25 04:31):
咦?为什么我在发帖的时候总是打不出数组元素A[ i ], u[ i ]呢?反正大家都能理解就对了。。面试的时候不是这样的。。

评分

5

查看全部评分

njuprincerain 发表于 2014-10-25 05:07:14 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼主第二题可以用DP做。.鏈枃鍘熷垱鑷1point3acres璁哄潧

如果轮到我选择球的时候, 我会胜利的要求是当我选择以后,留给对手的球他输了我就能赢,只要他无论怎样都赢了, 我就输了。 比如我现在手里有 i个球, 我只能选择两个球或者一个球, 留给对手的就是i-1 或 i-2 个球。 假设D= true or false 表示我当前能否赢。
那么DP表达式为
D = !D[i-1] || !D[i-2];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


补充内容 (2014-10-25 05:08):
basic case为 D[1] = true; D[2] = true; 因为无论怎样都可以拿1个或两个球
回复 支持 1 反对 0

使用道具 举报

 楼主| Soviet 发表于 2014-10-25 04:16:49 | 显示全部楼层
关注一亩三分地微博:
Warald
那个swap的, throwException是面试官问我你的那个illegal input check 有没有其他更好的办法呢?我就说要不加个throw Exception? 然后就问了一点这方面的我对这块还真没太深究过所以就大概说了几句糊弄过去了,然后这个coding问题还问了time complexity, 我说这应该O(n)吧
回复 支持 反对

使用道具 举报

tbu 发表于 2014-10-25 04:23:12 | 显示全部楼层
赞LZ的ID
同跪握爪!
回复 支持 反对

使用道具 举报

 楼主| Soviet 发表于 2014-10-25 05:10:10 | 显示全部楼层
njuprincerain 发表于 2014-10-25 05:07
楼主第二题可以用DP做。

如果轮到我选择球的时候, 我会胜利的要求是当我选择以后,留给对手的球他输了 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Good idea!这个思考角度很好。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
不过面试官似乎强调是你知道了弹球个数,基于此你决定谁先,保证你必胜。
回复 支持 反对

使用道具 举报

njuprincerain 发表于 2014-10-25 05:17:04 | 显示全部楼层
Soviet 发表于 2014-10-25 05:10. 鍥磋鎴戜滑@1point 3 acres
Good idea!这个思考角度很好。。
不过面试官似乎强调是你知道了弹球个数,基于此你决定谁先,保证你必胜 ...

那么这个解法依旧正确 因为我可以算出来D[n] = true or false 根据DP 如果是false 那当然他先选 如果是True 那我肯定可以先选。
回复 支持 反对

使用道具 举报

zbwc 发表于 2014-10-25 05:44:13 | 显示全部楼层
从算法的角度讲是没啥问题啊。。。
回复 支持 反对

使用道具 举报

纠结帝 发表于 2014-10-25 06:04:36 | 显示全部楼层
lz是申full time的?

好像full time电面都只有一个
. 1point3acres.com/bbsintern都是两个backtoback
回复 支持 反对

使用道具 举报

 楼主| Soviet 发表于 2014-10-25 06:18:38 | 显示全部楼层
纠结帝 发表于 2014-10-25 06:04
lz是申full time的?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

好像full time电面都只有一个

对,校招fulltime
回复 支持 反对

使用道具 举报

纠结帝 发表于 2014-10-25 06:40:34 | 显示全部楼层
我隐约感觉是交流 或者其他behavior上 的问题
我最近一次面试也是觉得交流得很不错了
但是后来问recruiter才知道是communicate +cooperation做的不够好 (但是我面的是square 他家的pair interview特别看重这个)


所以建议还是问recruiter 看看是什么问题
然后有条件的话多一点mock 然后问问feedback

祝好运!
回复 支持 反对

使用道具 举报

js_cl 发表于 2014-10-25 08:24:59 | 显示全部楼层
谢楼主 确实看起来比较简单 可能问题出在交流上?

或者等别的大神解答吧
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2014-10-25 11:52:00 | 显示全部楼层
楼主第一题的代码有bug
回复 支持 反对

使用道具 举报

 楼主| Soviet 发表于 2014-10-25 12:26:01 | 显示全部楼层
ototsuyume 发表于 2014-10-25 11:52
楼主第一题的代码有bug

求指出。。
回复 支持 反对

使用道具 举报

zhangshiying 发表于 2014-10-26 01:36:11 | 显示全部楼层
第一题原array不一定是sorted吧
回复 支持 反对

使用道具 举报

 楼主| Soviet 发表于 2014-10-26 04:18:08 | 显示全部楼层
zhangshiying 发表于 2014-10-26 01:36. from: 1point3acres.com/bbs
第一题原array不一定是sorted吧
.鐣欏璁哄潧-涓浜-涓夊垎鍦
不是,是任意顺序的,题目要求是排成那个奇怪的顺序
回复 支持 反对

使用道具 举报

zxyviopond 发表于 2014-10-26 15:28:54 | 显示全部楼层
LZ 那个SWAP有没有考虑 i,j 小于0的情况?. 1point 3acres 璁哄潧
以及,反正都是跟它前一个交换,不用把i,j都传进来吧,传一个就行了啊。
回复 支持 反对

使用道具 举报

王可雪 发表于 2014-10-26 15:50:49 | 显示全部楼层
感觉楼主代码没啥问题。
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdlib>
  4. using std::swap;
  5. using std::cout;
  6. using std::endl;

  7. class Solution {
  8. public:
  9.     void reorder(int *u, int n) {
  10.         if (n < 2)
  11.             return;
  12.         int i;
  13.         for (i = 1; i < n; i++) {
  14.             if ((i % 2) ^ (u[i-1] < u[i])) {
  15.                 swap(u[i-1], u[i]);
  16.             }
  17.         }. visit 1point3acres.com for more.
  18.     }
  19. };
复制代码
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-10-26 21:05:17 | 显示全部楼层
王可雪 发表于 2014-10-26 15:50
感觉楼主代码没啥问题。

好厉害! 代码好短! 能解释下15行吗?
回复 支持 反对

使用道具 举报

nullas 发表于 2014-10-30 06:56:15 | 显示全部楼层
楼主第一个问题回答的太牛逼了
回复 支持 反对

使用道具 举报

458870432 发表于 2014-11-12 14:27:09 | 显示全部楼层
我电面google也出了跟lz一样的第一题,follow up是有多少种可能。。。。。lz是被拒了还是自己感觉不好?我等了一个多月来的onsite
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-24 12:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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