一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 4382|回复: 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。
其实题目都不难,可能是因为我是在职的原因。
我就不写我的做法了,现在心里太乱了。。。. Waral 鍗氬鏈夋洿澶氭枃绔,

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

2. 第二轮是System Design,讨论Gmail的存储设计,主要是API和如何存放检索等等。

3. 第三轮是个中国大哥,直接说中文,感觉特别亲切。问题是给一个文件,里面每行是一个类似树的父子节点,比如说:
7,6
7,5
7, 4. 1point3acres.com/bbs
6, 3
6,2. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
希望是打印出树状结构。
7 - 6
   - - 3
   - - 2
  +5.1point3acres缃
  +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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第三题感觉是不是应该利用hashmap《int, node》建立起来一个树?然后再遍历一下?
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-12 08:46:18 | 显示全部楼层
关注一亩三分地微博:
Warald
谢谢楼主分享~请问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):
这么做其实就是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记录下来, 最后从后 ...
. more info on 1point3acres.com
表示不理解题目诶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.         public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.                 PrintStructrue ps = new PrintStructrue();. visit 1point3acres.com for more.
  4.                 int[][] edges = { { 7, 6 }, { 7, 5 }, { 7, 4 }, { 6, 3 }, { 6, 2 } };
  5.                 ps.printStructure(edges);
    . From 1point 3acres bbs
  6.         }

  7.         public void printStructure(int[][] edges) {
  8.                 if (edges == null || edges.length == 0) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.                         return;
  10.                 }. more info on 1point3acres.com
  11.                 HashMap<Integer, HashSet<Integer>> graph = buildGraph(edges);
  12.                 HashMap<Integer, Integer> counter = new HashMap<Integer, Integer>();
  13.                 for (HashSet<Integer> set : graph.values()) {. 1point 3acres 璁哄潧
  14.                         for (int ele : set) {
  15.                                 if (counter.containsKey(ele)) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.                                         counter.put(ele, counter.get(ele) + 1);
  17.                                 } else {
  18.                                         counter.put(ele, 1); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.                                 }
  20.                         }
  21.                 }
  22.                 Queue<Integer> queue = new LinkedList<Integer>();
  23.                 for (int ele : graph.keySet()) {
  24.                         if (!counter.containsKey(ele)) {
  25.                                 queue.offer(ele);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.                         }
  27.                 }
  28.                 while (!queue.isEmpty()) {
  29.                         int val = queue.poll();
  30.                         print(val, graph, 0);
  31.                 }
  32.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  33.         private void print(int val, HashMap<Integer, HashSet<Integer>> graph,
  34.                         int len) {
  35.                 for (int i = 0; i < len; i++) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.                         if (i == 0) {
  37.                                 System.out.print(" ");
  38.                         }
  39.                         System.out.print("-");
  40.                 }
  41.                 System.out.println(val);
  42.                 for (int i : graph.get(val)) {
  43.                         print(i, graph, len + 1);
  44.                 }
  45.         }

  46.         private HashMap<Integer, HashSet<Integer>> buildGraph(int[][] edges) {
  47.                 HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
  48.                 for (int[] edge : edges) {
  49.                         if (!map.containsKey(edge[0])) {. visit 1point3acres.com for more.
  50.                                 map.put(edge[0], new HashSet<Integer>());
  51.                         }
  52.                         if (!map.containsKey(edge[1])) {
  53.                                 map.put(edge[1], new HashSet<Integer>());
  54.                         }
  55.                         map.get(edge[0]).add(edge[1]);
  56.                 }
  57.                 return map;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  58.         }
  59. }. Waral 鍗氬鏈夋洿澶氭枃绔,
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

bobzhang2004 发表于 2016-3-6 00:30:25 | 显示全部楼层
coin题,假设每个硬币只能用一次. From 1point 3acres bbs
  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.                 }
  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++) {. from: 1point3acres.com/bbs
  15.                         for (int j = num; j > 0; j--) {
  16.                                 if (j >= coins[i] && table[j - coins[i]] != Integer.MAX_VALUE ) {
  17.                                         if (table[j - coins[i]] + 1 < table[j]) {
  18.                                                 table[j] = table[j - coins[i]] + 1;
  19.                                                 solution[j] = i;
  20.                                         }
  21.                                 }
  22.                         }
  23.                 }
  24.                
  25.                 List<Integer> res = new ArrayList<Integer>();
  26.                 if (table[num] == Integer.MAX_VALUE) {
  27.                         return res;
  28.                 }
  29.                 while (num > 0) {
  30.                         res.add(coins[solution[num]]);
  31.                         num -= coins[solution[num]];
  32.                 }
  33.                 Collections.reverse(res);
  34.                 return res;
  35. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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.         public static List<Integer> minChange(int[] coins, int num) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.                 int[] table = new int[num + 1];
  11.                 int[] solution = new int[num + 1];
  12.                 for (int i = 1; i <= num; i++) {
  13.                         int minNum = Integer.MAX_VALUE;
  14.                         int minIndex = Integer.MAX_VALUE;
  15.                         for (int j = 0; j < coins.length; j++) {
  16.                                 if (coins[j] <= i && 1 + table[i - coins[j]] < minNum) {
  17.                                         minNum = 1 + table[i - coins[j]];
  18.                                         minIndex = j;. 鍥磋鎴戜滑@1point 3 acres
  19.                                 }
  20.                         }
  21.                         table[i] = minNum;
  22.                         solution[i] = minIndex;
  23.                 }

  24.                 List<Integer> res = new ArrayList<Integer>();
  25.                 if (table[num] == Integer.MAX_VALUE) {
  26.                         return res;.1point3acres缃
  27.                 }. 鍥磋鎴戜滑@1point 3 acres
  28.                 while (num > 0) {
  29.                         res.add(coins[solution[num]]);
  30.                         num -= coins[solution[num]];
  31.                 }

  32.                 return res; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  33.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  34. }
复制代码
回复 支持 反对

使用道具 举报

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, 2017-4-30 05:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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