《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 831|回复: 1
收起左侧

google footer level 4,送foobar challenge链接

[复制链接] |试试Instant~ |关注本帖
9oooop 发表于 2017-7-3 10:09:49 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@Google - Other - 在线笔试 |Pass在职跳槽

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

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

x
关于google foobar这个博主介绍得很好:http://xiaohanyu.me/posts/2017-04-30-google-foobar-interview/ 我有好几题和他重复。贴一个遇到的level4题和我的解法。感觉gg foobar就是加点mathmatics的经典算法,high performance的implementation有难度,没有acm难。之后会贴个level5的新题。另外拿到个foobar challenge链接,想要的加米站内信,先到先得。如果要面试的话内推显然更快,主要是好玩。stem-font">Free the Bunny Prisoners
========================. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

You need to free the bunny prisoners before Commander Lambda's space station explodes! Unfortunately, the commander was very careful with her highest-value prisoners - they're all held in separate, maximum-security cells. The cells are opened by putting keys into each console, then pressing the open button on each console simultaneously. When the open button is pressed, each key opens its corresponding lock on the cell. So, the union of the keys in all of the consoles must be all of the keys. The scheme may require multiple copies of one key given to different minions..1point3acres缃

The consoles are far enough apart that a separate minion is needed for each one. Fortunately, you have already freed some bunnies to aid you - and even better, you were able to steal the keys while you were working as Commander Lambda's assistant. The problem is, you don't know which keys to use at which consoles. The consoles are programmed to know which keys each minion had, to prevent someone from just stealing all of the keys and using them blindly. There are signs by the consoles saying how many minions had some keys for the set of consoles. You suspect that Commander Lambda has a systematic way to decide which keys to give to each minion such that they could use the consoles.
.1point3acres缃
You need to figure out the scheme that Commander Lambda used to distribute the keys. You know how many minions had keys, and how many consoles are by each cell. You know that Command Lambda wouldn't issue more keys than necessary (beyond what the key distribution scheme requires), and that you need as many bunnies with keys as there are consoles to open the cell.

Given the number of bunnies available and the number of locks required to open a cell, write a function answer(num_buns, num_required) which returns a specification of how to distribute the keys such that any num_required bunnies can open the locks, but no group of (num_required - 1) bunnies can.

Each lock is numbered starting from 0. The keys are numbered the same as the lock they open (so for a duplicate key, the number will repeat, since it opens the same lock). For a given bunny, the keys they get is represented as a sorted list of the numbers for the keys. To cover all of the bunnies, the final answer is represented by a sorted list of each individual bunny's list of keys. Find the lexicographically least such key distribution - that is, the first bunny should have keys sequentially starting from 0.

num_buns will always be between 1 and 9, and num_required will always be between 0 and 9 (both inclusive). For example, if you had 3 bunnies and required only 1 of them to open the cell, you would give each bunny the same key such that any of the 3 of them would be able to open it, like so:. more info on 1point3acres.com
[
[0],
[0],
[0],
]
If you had 2 bunnies and required both of them to open the cell, they would receive different keys (otherwise they wouldn't both actually be required), and your answer would be as follows:
[
[0],
[1],
]
Finally, if you had 3 bunnies and required 2 of them to open the cell, then any 2 of the 3 bunnies should have all of the keys necessary to open the cell, but no single bunny would be able to do it. Thus, the answer would be:
[
[0, 1],
[0, 2],
[1, 2],
]


Languages
=========

To provide a Python solution, edit solution.py. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
To provide a Java solution, edit solution.java

. more info on 1point3acres.comTest cases. more info on 1point3acres.com
==========
. 1point3acres.com/bbs
Inputs:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    (int) num_buns = 2
    (int) num_required = 1
Output:
    (int) [[0], [0]]-google 1point3acres
. visit 1point3acres.com for more.
Inputs:
    (int) num_buns = 5
    (int) num_required = 3
Output:
    (int) [[0, 1, 2, 3, 4, 5], [0, 1, 2, 6, 7, 8], [0, 3, 4, 6, 7, 9], [1, 3, 5, 6, 8, 9], [2, 4, 5, 7, 8, 9]]

Inputs:
    (int) num_buns = 4
    (int) num_required = 4
Output:
    (int) [[0], [1], [2], [3]]. From 1point 3acres bbs



 楼主| 9oooop 发表于 2017-7-3 10:18:38 | 显示全部楼层
想法是这个: https://en.wikipedia.org/wiki/Combination
  1. public class Answer {. 1point3acres.com/bbs
  2. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.   public static int[][] answer(int num_buns, int num_required) { . from: 1point3acres.com/bbs
  4. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.     if(num_required > num_buns || num_required == 0) return new int[num_buns][0];
  6. . visit 1point3acres.com for more.
  7.     if(num_required == 1) return new int[num_buns][1];. 鍥磋鎴戜滑@1point 3 acres
  8. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.     .鏈枃鍘熷垱鑷1point3acres璁哄潧

  10.     int[] bun_labels = new int[num_buns];

  11.     int combSize = num_buns - num_required + 1;
  12. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.     for(int i = 0; i < num_buns; i++) bun_labels[i] = i;
  14. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.     List<List<Integer>> schema = getCombinations(bun_labels, combSize, 0);

  16.    
  17. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.     List<List<Integer>> result = new ArrayList<List<Integer>>();

  19.     for(int j = 0; j < num_buns; j++) result.add(new ArrayList<Integer>());

  20.    
  21. . From 1point 3acres bbs
  22.     for(int k = 0; k < schema.size(); k++) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  23. . 鍥磋鎴戜滑@1point 3 acres
  24.         List<Integer> positions = schema.get(k);
  25. . Waral 鍗氬鏈夋洿澶氭枃绔,
  26.         for(int pos : positions) {

  27.           result.get(pos).add(k);

  28.         }

  29.     }

  30.    

  31.     int[][] ans = new int[num_buns][result.get(0).size()];.1point3acres缃
  32. . more info on 1point3acres.com
  33.     for(int c = 0; c < result.size(); c++) {

  34.         List<Integer> cur = result.get(c);

  35.         for(int m = 0; m < cur.size(); m++) ans[c][m] = cur.get(m);
  36. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  37.     }
  38. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39.     return ans;

  40. }

  41. . 1point 3acres 璁哄潧
  42. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  43. private static List<List<Integer>> getCombinations(int[] items, int combSize, int startIndx) {

  44.     List<List<Integer>> result = new ArrayList<List<Integer>>();

  45.     if (combSize == 0) return result;
  46. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  47.     if (combSize == 1) {

  48.         for(int i = startIndx; i < items.length; i++) {

  49.             List<Integer> cur = new ArrayList<Integer>();

  50.             cur.add(items[i]);

  51.             result.add(cur);. more info on 1point3acres.com

  52.         }

  53.     } else {

  54.         for(int i = startIndx; i <= items.length - combSize; i++){

  55.             List<List<Integer>> cur = getCombinations(items, combSize-1, i+1);

  56.             for (List<Integer> ele : cur) {. 1point3acres.com/bbs

  57.                 ele.add(0, i);

  58.             }

  59.             result.addAll(cur);

  60.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  61.     }

  62.     return result;

  63. }

  64. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 22:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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