一亩三分地论坛

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

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

Google Onsite

[复制链接] |试试Instant~ |关注本帖
trampsun 发表于 2015-12-11 01:50:14 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - Other - Onsite |Other在职跳槽

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

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

x
这周2面的,现在在等结果,面得其实不好,recruiter说这周末或者下周初给我update,所以现在感到特别煎熬。。。发个面筋,希望能帮到大家,也希望大家能bless我拿到offer。.鐣欏璁哄潧-涓浜-涓夊垎鍦
其实题目都不难,可能是因为我是在职的原因。
我就不写我的做法了,现在心里太乱了。。。

1. 第一轮是写一个bounded blocking queue,主要写add(long timeout)和poll(long timeout),就是说如果一个thread想加个entry到queue里,它可以设置一个timeout,如果这个timeout时间内没有加进去,就返回或者throw exception。

2. 第二轮是System Design,讨论Gmail的存储设计,主要是API和如何存放检索等等。
. 鍥磋鎴戜滑@1point 3 acres
3. 第三轮是个中国大哥,直接说中文,感觉特别亲切。问题是给一个文件,里面每行是一个类似树的父子节点,比如说: .1point3acres缃
7,6
7,5
7, 4
6, 3
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 6,2
希望是打印出树状结构。
7 - 6
   - - 3
   - - 2
  +5
  +4
这个output的格式我也记得不太清楚了。我这题做的很不好,基本上没太能写出来,主要就是这个indentation没有弄好。

4. 第四轮是给两个list,求出在一个list中而不在另外一个list的entry,其实就是A-B和B-A。

5. 第五轮是找硬币题,不过是打印出最少硬币的序列,不是最小数值。这个题目我也答得不好,面试官希望我one pass,我的最初解是two pass,所以two pass写到一半他就说让写one pass的。写one pass的时候有bug,被指出来后,想到一个方法,面试官说是对的,不过不是面试官希望的。最后也没能写完,感到特别无力。。。

本帖被以下淘专辑推荐:

hyliu0000 发表于 2015-12-11 02:42:24 | 显示全部楼层
第三题感觉是不是应该利用hashmap《int, node》建立起来一个树?然后再遍历一下?
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-12 08:46:18 | 显示全部楼层
谢谢楼主分享~请问A-B和B-A那题应该怎么做哈?
回复 支持 反对

使用道具 举报

abysshades 发表于 2015-12-12 12:19:52 | 显示全部楼层
跟楼主同一天哎,HR也跟我说下周一之前给update。。。莫非周二上午9:30左右在building 41见过的么?
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-12 13:43:40 | 显示全部楼层
楼主 请问第5题怎么做到1 pass,我能想到的是把每个target sum对应最后一步要选的coin记录下来, 最后从后往前拿出所有的coin

补充内容 (2015-12-12 13:43):. more info on 1point3acres.com
这么做其实就是2pass了吗

回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-13 11:59:03 | 显示全部楼层
请问找硬币具体题目是?
回复 支持 反对

使用道具 举报

orangepie 发表于 2015-12-13 14:03:32 | 显示全部楼层
请问楼主 第四题两个list 那道题,  除了sort, 或者用set直接做; 还有什么更好地办法吗?
回复 支持 反对

使用道具 举报

shuishuimiao 发表于 2015-12-13 14:47:54 | 显示全部楼层
请问楼主能详细说一下找硬币这个题的题目吗
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-12-28 00:53:47 | 显示全部楼层
LifeGoesOn 发表于 2015-12-12 13:43
楼主 请问第5题怎么做到1 pass,我能想到的是把每个target sum对应最后一步要选的coin记录下来, 最后从后 ...

表示不理解题目诶0。0 怎么记录target sum呢~。谢谢
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2015-12-28 01:52:41 | 显示全部楼层
leetcode昨天刚加了这个题 用dp算最少个数 同时cache每步的最优解 最后应该能同时得出最少个数以及是哪些硬币 one pass
回复 支持 反对

使用道具 举报

一路向北~ 发表于 2016-1-14 15:17:46 | 显示全部楼层
楼主有结果了吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-25 06:30:56 | 显示全部楼层
kinggarden2001 发表于 2015-12-28 01:52
leetcode昨天刚加了这个题 用dp算最少个数 同时cache每步的最优解 最后应该能同时得出最少个数以及是哪些硬 ...

怎么cache呢?用hashMap吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-25 06:33:40 | 显示全部楼层
bounded blocking queue应该还需要是add什么东西吧?不能只有时间吧?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-25 07:02:02 | 显示全部楼层
写了下打印树的题,最后输出格式还是有一些差异
  1. public class PrintStructrue {

  2. . From 1point 3acres bbs
  3.         public static void main(String[] args) {
  4.                 PrintStructrue ps = new PrintStructrue();
  5.                 int[][] edges = { { 7, 6 }, { 7, 5 }, { 7, 4 }, { 6, 3 }, { 6, 2 } };
  6.                 ps.printStructure(edges);
  7.         }. from: 1point3acres.com/bbs

  8.         public void printStructure(int[][] edges) {
  9.                 if (edges == null || edges.length == 0) {
  10.                         return;-google 1point3acres
  11.                 }
  12.                 HashMap<Integer, HashSet<Integer>> graph = buildGraph(edges);
  13.                 HashMap<Integer, Integer> counter = new HashMap<Integer, Integer>();
  14.                 for (HashSet<Integer> set : graph.values()) {
  15.                         for (int ele : set) {
  16.                                 if (counter.containsKey(ele)) {
  17.                                         counter.put(ele, counter.get(ele) + 1);
  18.                                 } else {
  19.                                         counter.put(ele, 1);
  20.                                 }
  21.                         }
  22.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.                 Queue<Integer> queue = new LinkedList<Integer>();
  24.                 for (int ele : graph.keySet()) {
  25.                         if (!counter.containsKey(ele)) {
  26.                                 queue.offer(ele);
  27.                         }
  28.                 }
  29.                 while (!queue.isEmpty()) {
  30.                         int val = queue.poll();
  31.                         print(val, graph, 0);. 1point3acres.com/bbs
  32.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  33.         }

  34.         private void print(int val, HashMap<Integer, HashSet<Integer>> graph,
  35.                         int len) {
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  36.                 for (int i = 0; i < len; i++) {
  37.                         if (i == 0) {
  38.                                 System.out.print(" ");
  39.                         }
  40.                         System.out.print("-");
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  41.                 }
  42.                 System.out.println(val);
  43.                 for (int i : graph.get(val)) {
  44.                         print(i, graph, len + 1);
  45.                 }
  46.         }

  47.         private HashMap<Integer, HashSet<Integer>> buildGraph(int[][] edges) {.1point3acres缃
  48.                 HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
  49.                 for (int[] edge : edges) {
  50.                         if (!map.containsKey(edge[0])) {
  51.                                 map.put(edge[0], new HashSet<Integer>());. From 1point 3acres bbs
  52.                         }
  53.                         if (!map.containsKey(edge[1])) {
  54.                                 map.put(edge[1], new HashSet<Integer>());
  55.                         }. 1point3acres.com/bbs
  56.                         map.get(edge[0]).add(edge[1]);
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  57.                 }
  58.                 return map;
  59.         }
  60. }
复制代码
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-2-22 06:46:33 | 显示全部楼层
bobzhang2004 发表于 2016-1-24 18:02. 1point3acres.com/bbs
写了下打印树的题,最后输出格式还是有一些差异

你好,请问这一题的题目是什么意思能和我说下吗,看不明白,谢谢!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-5 23:48:37 | 显示全部楼层
第五轮是找硬币题,不过是打印出最少硬币的序列.这个题是要怎么存序列呢?hashmap还是stack
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-6 00:30:25 | 显示全部楼层
coin题,假设每个硬币只能用一次
  1. public class CoinsChangeIII {

  2.         public static void main(String[] args) {
  3.                 int[] coins = { 1, 2, 3, 4, 5, 6, 10 };
  4.                 List<Integer> res = minChange(coins, 9);
  5.                 for (int i : res) {
  6.                         System.out.print(i + " ");
  7.                 }. From 1point 3acres bbs
  8.         }

  9.         public static List<Integer> minChange(int[] coins, int num) {
  10.                 int[] table = new int[num + 1];
  11.                 int[] solution = new int[num + 1];
  12.                 Arrays.fill(table, Integer.MAX_VALUE);
  13.                 table[0] = 0;
  14.                 for (int i = 0; i < coins.length; i++) {
  15.                         for (int j = num; j > 0; j--) {
  16.                                 if (j >= coins[i] && table[j - coins[i]] != Integer.MAX_VALUE ) {. 1point3acres.com/bbs
  17.                                         if (table[j - coins[i]] + 1 < table[j]) {-google 1point3acres
  18.                                                 table[j] = table[j - coins[i]] + 1;
  19.                                                 solution[j] = i;
  20.                                         }
  21.                                 }
  22.                         }
  23.                 }. visit 1point3acres.com for more.
  24.                
  25.                 List<Integer> res = new ArrayList<Integer>();
  26.                 if (table[num] == Integer.MAX_VALUE) {
  27.                         return res;. 鍥磋鎴戜滑@1point 3 acres
  28.                 }
  29.                 while (num > 0) {
  30.                         res.add(coins[solution[num]]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  31.                         num -= coins[solution[num]];. 1point 3acres 璁哄潧
  32.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  33.                 Collections.reverse(res);-google 1point3acres
  34.                 return res;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35. . 1point 3acres 璁哄潧
  36.         }
  37. }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-6 00:30:50 | 显示全部楼层
coin题,假设每个硬币可以用多次
  1. public class CoinsChangeII {

  2.         public static void main(String[] args) {
  3.                 int[] coins = { 1, 4, 5, 10 };
  4.                 List<Integer> res = minChange(coins, 8);
  5.                 for (int i : res) {
  6.                         System.out.print(i + " ");
  7.                 }
  8.         }
  9. . from: 1point3acres.com/bbs
  10.         public static List<Integer> minChange(int[] coins, int num) {
  11.                 int[] table = new int[num + 1];
  12.                 int[] solution = new int[num + 1];
  13.                 for (int i = 1; i <= num; i++) {
  14.                         int minNum = Integer.MAX_VALUE;
  15.                         int minIndex = Integer.MAX_VALUE;
  16.                         for (int j = 0; j < coins.length; j++) {
  17.                                 if (coins[j] <= i && 1 + table[i - coins[j]] < minNum) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.                                         minNum = 1 + table[i - coins[j]];. 鍥磋鎴戜滑@1point 3 acres
  19.                                         minIndex = j;
  20.                                 }
  21.                         }
  22.                         table[i] = minNum;
  23.                         solution[i] = minIndex;. visit 1point3acres.com for more.
  24.                 }
  25. . from: 1point3acres.com/bbs
  26.                 List<Integer> res = new ArrayList<Integer>();
  27.                 if (table[num] == Integer.MAX_VALUE) {. from: 1point3acres.com/bbs
  28.                         return res;. 1point3acres.com/bbs
  29.                 }
  30.                 while (num > 0) {
  31.                         res.add(coins[solution[num]]);. more info on 1point3acres.com
  32.                         num -= coins[solution[num]];
  33.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦

  34.                 return res;

  35.         }
  36. }
复制代码
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-1 02:54:24 | 显示全部楼层
硬币题我是dp时每个点都用一个list来保存路径

补充内容 (2016-5-1 02:55):
不知道面试官希望的是什么样子的?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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