亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3413|回复: 22
收起左侧

Google 3/15电面面经

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

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

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

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

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. from: 1point3acres.com/bbs
Example:
input: a = 3, b = 1. 鍥磋鎴戜滑@1point 3 acres
[001, 010, 100]
output: [1, 2, 4]. visit 1point3acres.com for more.
Explain time and space complexity.

2. Determine if two int array is permutation.
刚开始觉得这个题太简单了还跟他确定了一下不是next permutation, 只要判断是不是permutation就好。-google 1point3acres
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

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 462, 订阅: 106
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. 1point3acres.com/bbs
楼主第一题是不是先求出一个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啊?

我也不是很清楚,应该是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的复杂度是多少? 是不是还需要去重和把结果排个序才能输出?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

谢谢
回复 支持 反对

使用道具 举报

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

谢谢
. visit 1point3acres.com for more.
你看看这个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) {
  10.                 List<Integer> res = new ArrayList<Integer>();-google 1point3acres
  11.                 if (a <= 0) {
  12.                         return res;
  13.                 }.1point3acres缃
  14.                
  15.                 helper(res, new ArrayList<Integer>(), a, b);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.                 return res;
  17.         }
  18. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.         private static void helper(List<Integer> res, ArrayList<Integer> list, int a,. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.                         int b) {
  21.                 if (b < 0) {
  22.                         return;
  23.                 }
  24.                 if (a == 0) {
  25.                         if (b == 0) {
  26.                                 res.add(eval(list));
  27.                         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.                         return;
  29.                 }
  30.                
  31.                 list.add(0);
  32.                 helper(res, list, a - 1, b);
  33.                 list.remove(list.size() - 1); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  34.                 list.add(1);. 1point 3acres 璁哄潧
  35.                 helper(res, list, a - 1, b - 1);. from: 1point3acres.com/bbs
  36.                 list.remove(list.size() - 1);
  37.         }

  38.         private static int eval(ArrayList<Integer> list) {
  39.                 int val = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  40.                 int num = 1;
  41.                 for (int i = list.size() - 1; i >= 0 ; i--) {. 鍥磋鎴戜滑@1point 3 acres
  42.                         val += list.get(i) * num;
  43.                         num *= 2;
  44.                 }
  45.                 . visit 1point3acres.com for more.
  46.                 return val;
  47.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  48. }
复制代码
回复 支持 反对

使用道具 举报

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 | 显示全部楼层
第一题,练习一下,顺便粘粘楼主好运. From 1point 3acres bbs
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) {
        if (item.length() == a) {
           if (b == 0) {
               ret.add(item);
           }
           return;
        }
        . Waral 鍗氬鏈夋洿澶氭枃绔,
        dfs(ret, a, b, item + '0');
        dfs(ret, a, b - 1, item + '1');
    }-google 1point3acres
}
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

寂寞的季节 发表于 2017-3-28 08:26:21 | 显示全部楼层
  1. public List<Integer> binaryRepresentation(int a, int b) {
  2.         List<Integer> result = new ArrayList<Integer>();
  3.         if (a < b) {
  4.             return result;
  5.         }. From 1point 3acres bbs
  6.         dfs(result, a, b, a - b, "");. from: 1point3acres.com/bbs
  7.         return result;. 1point 3acres 璁哄潧
  8.     }

  9.     private void dfs(List<Integer> result, int a, int b, int c, String path) {-google 1point3acres
  10.         if (path.length() == a) {
  11.             result.add(Integer.parseInt(path, 2));
  12.         }
  13.         if (c > 0) {
  14.             dfs(result, a, b, c - 1, path + "0");. 1point3acres.com/bbs
  15.         }-google 1point3acres
  16.         if (b > 0) {
  17.             dfs(result, a, b - 1, c, path + "1");
  18.         }
  19.     }
复制代码
. 鍥磋鎴戜滑@1point 3 acres

第一题求所有的符合的combination,先0后1枚举就能是排好序的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-10-21 03:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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