一亩三分地论坛

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

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

Google 3/15电面面经

[复制链接] |试试Instant~ |关注本帖
MyLuckyhusky 发表于 2016-3-17 02:40:22 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

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

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

x
第一次DOC写代码的体验给了google.全程都很紧张。 听口音小哥像是欧洲人,但是非常NICE,说如果没听明白一定要和他确定。
前两分钟自我介绍了一下在哪个组我其实没听出来说的太快然后没问任何简历上的问题就直接开始了。

1. Given two number a and b, find all the binary representations with length a and has b number of 1's and output in decimal in sorted order
Example:
input: a = 3, b = 1
[001, 010, 100]
output: [1, 2, 4]
Explain time and space complexity.

2. Determine if two int array is permutation.
刚开始觉得这个题太简单了还跟他确定了一下不是next permutation, 只要判断是不是permutation就好。
input: [1, 1, 0] and [0, 1, 1]
output: true.
Explain time and space complexity.

两道题都非常简单,大概不到三十分钟就写完了然后愉快地聊了一会天。 小哥一直在说自己很喜欢在Google 工作什么的,讲啦一下最近在用GO做的项目。 感觉小哥和我一样紧张,然后没有很多follow up的问题。发面经攒人品希望on site。



补充内容 (2016-3-18 02:26):
可以去onsite啦开心。

评分

3

查看全部评分

JohnsonMS 发表于 2016-3-19 22:30:31 | 显示全部楼层
第一题觉得应该 使用next permutation 求, 初始值值为最小的那个, 例如 len 5, bit 2, “00011”, 然后一个个next 计算, 直到最大
回复 支持 1 反对 0

使用道具 举报

wyb_1221 发表于 2016-3-17 03:42:17 | 显示全部楼层
楼主加油!楼主面的是哪个office啊?
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-3-17 04:17:10 | 显示全部楼层
楼主第一题是不是先求出一个solution,然后再求这个solution的所有permutation?
回复 支持 反对

使用道具 举报

 楼主| MyLuckyhusky 发表于 2016-3-17 06:11:51 | 显示全部楼层
wtcupup 发表于 2016-3-17 04:17
楼主第一题是不是先求出一个solution,然后再求这个solution的所有permutation?

好有道理。我当时心情紧张没想到permutation是找了所有的combination然后找到符合只有B个1的。写完以后他也没和我follow up后面的。 应该是找permutation更好。
回复 支持 反对

使用道具 举报

 楼主| MyLuckyhusky 发表于 2016-3-17 06:13:25 | 显示全部楼层
wyb_1221 发表于 2016-3-17 03:42
楼主加油!楼主面的是哪个office啊?

. 1point 3acres 璁哄潧我也不是很清楚,应该是MV? 面试小哥是MV的,还问了我想去哪个office,我还懵逼地说了Boston== 哈哈。
回复 支持 反对

使用道具 举报

hitowings 发表于 2016-3-18 14:02:12 | 显示全部楼层
第一题的时间复杂度楼主怎么回答的?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-20 02:11:49 | 显示全部楼层
请问楼主第一题是用backtracking吗?然后评估值.
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-20 02:12:12 | 显示全部楼层
第二题应该就是用hashmap计数吧
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-3-20 14:36:05 | 显示全部楼层
MyLuckyhusky 发表于 2016-3-17 06:11
好有道理。我当时心情紧张没想到permutation是找了所有的combination然后找到符合只有B个1的。写完以后他 ...

lz用permutation的复杂度是多少? 是不是还需要去重和把结果排个序才能输出?-google 1point3acres
.鏈枃鍘熷垱鑷1point3acres璁哄潧
谢谢
回复 支持 反对

使用道具 举报

 楼主| MyLuckyhusky 发表于 2016-3-21 06:50:17 | 显示全部楼层
guixi107 发表于 2016-3-20 14:36
lz用permutation的复杂度是多少? 是不是还需要去重和把结果排个序才能输出?

谢谢

你看看这个link: http://cs.stackexchange.com/questions/11611/can-all-permutations-of-a-set-or-string-be-generated-in-on-log-n-time
感觉把复杂度解释的很清楚~~
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-25 22:55:49 | 显示全部楼层
请问楼主是第二天就出了结果吗?
回复 支持 反对

使用道具 举报

 楼主| MyLuckyhusky 发表于 2016-3-26 01:00:41 | 显示全部楼层
bobzhang2004 发表于 2016-3-25 22:55
请问楼主是第二天就出了结果吗?

15号面完18号出的结果。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-30 04:01:06 | 显示全部楼层
写了下代码,不知道还可以改进吗. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  1. public class BinaryRepresentations {.鐣欏璁哄潧-涓浜-涓夊垎鍦

  2.         public static void main(String[] args) {
  3.                 List<Integer> res = getAllBinaryRepresentations(3, 1);
  4.                 for (int i : res) {
  5.                         System.out.println(i);
  6.                 }
  7.         }
  8.        
  9.         public static List<Integer> getAllBinaryRepresentations(int a, int b) {-google 1point3acres
  10.                 List<Integer> res = new ArrayList<Integer>();
  11.                 if (a <= 0) {
  12.                         return res;-google 1point3acres
  13.                 }
  14.                
  15.                 helper(res, new ArrayList<Integer>(), a, b);
  16.                 return res;-google 1point3acres
  17.         }

  18.         private static void helper(List<Integer> res, ArrayList<Integer> list, int a,
  19.                         int b) {. 1point 3acres 璁哄潧
  20.                 if (b < 0) {
  21.                         return;
  22.                 }
  23.                 if (a == 0) {
  24.                         if (b == 0) {
  25.                                 res.add(eval(list));
  26.                         }
  27.                         return;
  28.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.                
  30.                 list.add(0);
  31.                 helper(res, list, a - 1, b);
  32.                 list.remove(list.size() - 1);
  33.                 list.add(1);
  34.                 helper(res, list, a - 1, b - 1);
  35.                 list.remove(list.size() - 1);. From 1point 3acres bbs
  36.         }

  37.         private static int eval(ArrayList<Integer> list) {
  38.                 int val = 0;
  39.                 int num = 1;
  40.                 for (int i = list.size() - 1; i >= 0 ; i--) {. 鍥磋鎴戜滑@1point 3 acres
  41.                         val += list.get(i) * num;
  42.                         num *= 2;
  43.                 }
  44.                
  45.                 return val;. Waral 鍗氬鏈夋洿澶氭枃绔,
  46.         }
  47. }
复制代码
回复 支持 反对

使用道具 举报

phil 发表于 2016-3-30 04:53:18 | 显示全部楼层
我的理解是可以用n & (n - 1) 得出 1 的个数, 然后从 0 到 2 ^ a  - 1 扫一遍计数, 但可能O(2^a)的时间复杂度不会被接受啊
回复 支持 反对

使用道具 举报

jerry_lin324 发表于 2016-4-3 21:27:43 | 显示全部楼层
楼主,我是朋友内推的,现在刚被一个HR约了电话聊聊,我看这个HR的LinkedIn应该就是个general recruiter。这一般第一次电话面试是聊什么呢?还有请楼主讲解下他们家的大概流程,谢啦!祝楼主offer多多!
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-20 05:55:58 | 显示全部楼层
第一题,练习一下,顺便粘粘楼主好运
public class Solution {
    public int binaryRepresentations(int a, int b) {
        List<String> ret = new LinkedList<String>();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        dfs(ret, a, b, "");
        return ret;
    }
    void dfs(List<String> ret, int a, int b, String item) {. Waral 鍗氬鏈夋洿澶氭枃绔,
        if (item.length() == a) {
           if (b == 0) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
               ret.add(item);
           }
           return;
        }
        
        dfs(ret, a, b, item + '0');. 鍥磋鎴戜滑@1point 3 acres
        dfs(ret, a, b - 1, item + '1');
    }
}
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-20 07:43:51 | 显示全部楼层
MyLuckyhusky 发表于 2016-3-17 06:11
好有道理。我当时心情紧张没想到permutation是找了所有的combination然后找到符合只有B个1的。写完以后他 ...

permutation的复杂度不是比combination高吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 06:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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