一亩三分地论坛

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

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

G家面经,已跪

[复制链接] |试试Instant~ |关注本帖
yanyan2060 发表于 2016-6-14 02:15:31 | 显示全部楼层 |阅读模式

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

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

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

x
G家已跪,发面经攒人品。。
第一轮: 面试官迟到了。。给一个string,只含有a和b,a可以变成b,b可以变成a,也可以不操作,返回操作次数最少就可以得到的sort的string, 用了word ladder的方法。。也不知道对不对了。心理素质太差了。。。
第二轮 : Number of Islands 1 和 2, 只用写2的code 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第三轮: 给一个API, 叫getchar1024(), 总能返回1024个char, 里面有个:(,这个sad face 前面都是valid, 后面都不要, 实现getchar(int n)
第四轮 : 炸弹人, 一个matrix, 里面有敌人, 有墙, 炸弹可以放在空的格子里,每次一炸所在行列的敌人就被扎死了,问最多可以炸死的敌人个数,感觉和看花的题一样。。。
自己交流也不是很好。。面经没有好好准备。。来年再努力。。感谢亚麻收了我并且能留加州。。楼主EE毕业找不到工作。。野路子强行刷题转码工,找到工作就很开心了。都没有想到能去gg面试。。。先去亚麻学习知识了。。以后有机会再努力大G家~~~找工季结束!!祝各位都能拿到满意的offer!!!!

评分

4

查看全部评分

nevets 发表于 2016-6-14 13:12:10 | 显示全部楼层
第一题其实就1种情况:把一个字符串转换成若干个a之后若干个b,所以用一个数组B维护从0到i中b的个数,一个数组A维护从i到N-1中a的个数,然后循环一遍取min(B[i] + A[i + 1])

第四题其实只要知道每一个cell所在的横纵segment中有几个人就行,先预处理一遍然后NM求最大。
回复 支持 4 反对 0

使用道具 举报

July09 发表于 2016-6-14 11:21:48 | 显示全部楼层
第一题
int convertSortedString(String s) {
        int length = s.length();
        if (length <= 1)
            return length;
        //I assume we want aaa...bbb, ret can be all a or all b
//        let A[n] ends with a, B[n] ends with b
        //We can improve it without array....
        int [] a = new int [1+length];
        int [] b = new int [1+length];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        for (int i = 1; i <= length; ++i) {. 鍥磋鎴戜滑@1point 3 acres
            if (s.charAt(i-1) == 'a') {
                a[i] = a[i-1];
. 1point 3acres 璁哄潧                b[i] = 1 + Math.min(a[i-1], b[i-1]);. more info on 1point3acres.com
            } else {
                a[i] = 1 + a[i-1];
                b[i] = Math.min(a[i-1], b[i-1]);
            }
        }. from: 1point3acres.com/bbs

        return Math.min(a[length], b[length]);
    }
回复 支持 2 反对 0

使用道具 举报

edcent 发表于 2016-6-14 02:47:47 | 显示全部楼层
第一题输出是什么呢?是sort好的string吗,a在前面b在后面?然后要求操作次数最少?
回复 支持 1 反对 0

使用道具 举报

wavestyle 发表于 2016-6-14 02:25:45 | 显示全部楼层
楼主,第四题是只能放一个炸弹么?
回复 支持 反对

使用道具 举报

 楼主| yanyan2060 发表于 2016-6-14 02:31:10 | 显示全部楼层
wavestyle 发表于 2016-6-14 02:25
楼主,第四题是只能放一个炸弹么?

恩恩放一个炸弹
回复 支持 反对

使用道具 举报

edcent 发表于 2016-6-14 02:46:02 | 显示全部楼层
能炸死的敌人是当前行列所有的还是只是炸弹第一个能碰到的呢?
sad face那题也太逗了吧..
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2016-6-14 02:51:44 | 显示全部楼层
第四题 有墙 意思是隔着墙 就算同排同列也炸不死吗
回复 支持 反对

使用道具 举报

 楼主| yanyan2060 发表于 2016-6-14 02:55:09 | 显示全部楼层
xdrealmadrid 发表于 2016-6-14 02:51
第四题 有墙 意思是隔着墙 就算同排同列也炸不死吗

对的对的,有墙的话就扎不过去了。
回复 支持 反对

使用道具 举报

 楼主| yanyan2060 发表于 2016-6-14 02:55:52 | 显示全部楼层
edcent 发表于 2016-6-14 02:46
能炸死的敌人是当前行列所有的还是只是炸弹第一个能碰到的呢?
sad face那题也太逗了吧..

碰到墙之前,有敌人的话都炸死
回复 支持 反对

使用道具 举报

edcent 发表于 2016-6-14 03:05:29 | 显示全部楼层
第一题有点点像sort colors 就是不确定sort colors那种方法是不是最少操作
回复 支持 反对

使用道具 举报

alexanderzjs 发表于 2016-6-14 05:49:23 | 显示全部楼层
第一题是两个指针么?第一个指向b,改成a,然后第二个从后往前指向a改成b这样子?
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2016-6-14 06:36:26 | 显示全部楼层
第一题可以先扫描一遍array,找到所有b的位置。然后循环所有的这些位置,看如果这个位置的b是排序后的数列的第一个b的话要进行多少操作,这一步可以O(1)得到,一个循环下来找到最小的步数。算法应该是O(n)
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-14 06:46:59 | 显示全部楼层
Dp 解第一题,不知道对不对,测了点cases,没差。
  1. int miniChange(string str) {
  2.   int n = str.size();
  3.   vector<int> front(n, 0);
  4.   for(int i = 1; i < n; ++i) {
  5.     if(str[i] >= str[i-1]) front[i] = front[i-1];
  6.     else {
  7.       front[i] = front[i-1] + 1;
  8.     }
  9.   }. From 1point 3acres bbs

  10.   vector<int> backward(n, 0);-google 1point3acres
  11.   for(int i = n - 1; i > 0; --i) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.     if(str[i-1] <= str[i]) backward[i-1] = backward[i];
  13.     else {
  14.       backward[i-1] = backward[i] + 1;
  15.     }
  16.   }

  17.   int minChange = str.size();
  18.   for(int i = 0; i < n; ++i) {
  19.     minChange = min(minChange, front[i] + backward[i]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.   }
  21.   return minChange;
  22. }


  23. int main(void) {.1point3acres缃
  24.   cout << miniChange("aaab") << endl;
  25.   cout << miniChange("baab") << endl;
  26.   cout << miniChange("abab") << endl;
  27.   cout << miniChange("bbba") << endl;
  28.   cout << miniChange("baba") << endl;
  29. }
复制代码
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-14 06:48:37 | 显示全部楼层
第四题就是 dp
回复 支持 反对

使用道具 举报

alexanderzjs 发表于 2016-6-14 07:23:24 | 显示全部楼层
edcent 发表于 2016-6-14 03:05. Waral 鍗氬鏈夋洿澶氭枃绔,
第一题有点点像sort colors 就是不确定sort colors那种方法是不是最少操作

应该是的,类似于贪心吧,假设两端需要交换的b和a不交换,中间必然有另外一些ab需要去替换两端的值,所以必须要交换,不知道对不对哈
回复 支持 反对

使用道具 举报

coolshark 发表于 2016-6-14 09:19:07 | 显示全部楼层
lz好运气,亚麻也不错
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-6-14 12:03:01 | 显示全部楼层
July09 发表于 2016-6-14 11:21
第一题
int convertSortedString(String s) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        int length = s.length();

厉害~~. 1point3acres.com/bbs
感觉对头
回复 支持 反对

使用道具 举报

dong882205 发表于 2016-6-14 12:51:20 | 显示全部楼层
blackrose 发表于 2016-6-14 06:46
Dp 解第一题,不知道对不对,测了点cases,没差。

...正准备贴代码, 一看几乎一样, 肯定是对啦, 从前往后, 从后往前各扫一遍, 看加和
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-14 13:06:50 | 显示全部楼层
dong882205 发表于 2016-6-14 12:51
...正准备贴代码, 一看几乎一样, 肯定是对啦, 从前往后, 从后往前各扫一遍, 看加和

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 03:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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