一亩三分地论坛

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

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

12/16 Google实习电面面经

[复制链接] |试试Instant~ |关注本帖
wukey 发表于 2015-12-17 15:29:02 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
11月13号找了地里的前辈内推Google。
. From 1point 3acres bbs昨天刚考完最后一门,今天中午12点就两轮背靠背的电话面试(面试官离的近,所以甚至连电话都没挂,连着打了两个小时)。


废话不多说,上面经。


. from: 1point3acres.com/bbs
第一轮是一个美国哥们,
第一道题输入一个由10组成的字符串(背景是1代表一个youtube视频中有音频的部分,0代表没有音频的部分)。设计一个Binary Tree类,使最下一层的节点值与该字符串相等。
举个例子:given "1011"
     root . visit 1point3acres.com for more.
   /        \.1point3acres缃
node      node
/   \         /  \. 1point 3acres 璁哄潧
1   0       1   1

第二道题是这道题的follow up: 为了节省空间,我们用一个节点代表其下的所有节点值与该值相同。
举个栗子:given"1011"
     root
   /        \
node      1
/   \      
1   0      
. more info on 1point3acres.com

第二轮应该是一个印度哥们,但是口语清晰无比,而且叫Michael...
第一道问题是输入一个矩阵,返回另一个矩阵要求,每个元素是原矩阵所有该位置以左及以上的所有元素和(包括该元素)
举个栗子:输入1 2  返回 1 3
                      3 4          4 10

第二道问题是输入一个树(不是二叉树),返回一个字符串或者数组来表示这个树的结构。我的理解是相当于给树编码,具体方式自己决定。

看了地里很多面经,特地来回馈一下,求大米和祝福!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-1-14 05:50):
感谢大家打赏大米!进展:面试三天后得知进pool,在pool里三周后match上一个irvine office的组。

评分

8

查看全部评分

本帖被以下淘专辑推荐:

 楼主| wukey 发表于 2015-12-18 05:39:16 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-12-17 16:11
lz能分享下,你们做的这些题么

第一轮的第一道题我是用按层遍历树的方法去构建这个树,因为输入是2的指数,可以知道树的深度,所以在遍历过程中只要没到目标深度就new两个子节点,如果到了目标深度就把输入的值赋给这层所有的节点。
第一道题的follow up,是分治的思路用递归实现,每次将字符串分半,如果当前子串全部由同一个元素组成,就赋值,如果不是就继续分成两半考虑。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

第二轮第一题是比较简单的DP。第二题理解了题目之后其实跟第一轮的第一题差不多,也是按层遍历。

这是我的想法哈,大家多交流。

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

johnjavabean 发表于 2015-12-17 16:03:13 | 显示全部楼层
同学能提供下你当时给出的solution吗?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-17 16:11:01 | 显示全部楼层
lz能分享下,你们做的这些题么
回复 支持 反对

使用道具 举报

liruoyuxgd2006 发表于 2015-12-18 00:05:49 | 显示全部楼层
感觉第二题不就是traverse tree吗?
回复 支持 反对

使用道具 举报

liruoyuxgd2006 发表于 2015-12-18 00:06:28 | 显示全部楼层
LZ,每轮回答了2个题?看来时间还是蛮充裕的,我就做了一个题就没时间了
回复 支持 反对

使用道具 举报

ohyline 发表于 2015-12-18 00:31:09 | 显示全部楼层
祝楼主好运了~ 希望年底拿大奖!!!
回复 支持 反对

使用道具 举报

 楼主| wukey 发表于 2015-12-18 05:31:08 | 显示全部楼层
ohyline 发表于 2015-12-18 00:31. 1point3acres.com/bbs
祝楼主好运了~ 希望年底拿大奖!!!

谢谢!也祝你好运!
回复 支持 反对

使用道具 举报

 楼主| wukey 发表于 2015-12-18 05:40:13 | 显示全部楼层
johnjavabean 发表于 2015-12-17 16:03. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
同学能提供下你当时给出的solution吗?

请看对楼下同学的回复~ 大家多交流
回复 支持 反对

使用道具 举报

 楼主| wukey 发表于 2015-12-18 05:42:00 | 显示全部楼层
liruoyuxgd2006 发表于 2015-12-18 00:06
LZ,每轮回答了2个题?看来时间还是蛮充裕的,我就做了一个题就没时间了
. visit 1point3acres.com for more.
对,我的思路也是traverse tree。是的,每轮做了两道,但这几个题都不难的样子,所以可能有第三道题我没有做到。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-12-18 07:41:51 | 显示全部楼层
wukey 发表于 2015-12-18 05:39. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一轮的第一道题我是用按层遍历树的方法去构建这个树,因为输入是2的指数,可以知道树的深度,所以在遍 ...

给的数,比如1011,一定是2的倍数么?
如果是的话,还简单一些。。
我感觉这题,有点,不容易想出来啊。
回复 支持 反对

使用道具 举报

 楼主| wukey 发表于 2015-12-18 07:53:08 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-12-18 07:41. 1point 3acres 璁哄潧
给的数,比如1011,一定是2的倍数么?
如果是的话,还简单一些。。
我感觉这题,有点,不容易想出来啊 ...

是的,我问过之后,面试官说会是2的倍数。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2015-12-18 09:08:19 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!-google 1point3acres
. from: 1point3acres.com/bbs
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

wtcupup 发表于 2015-12-18 09:11:44 | 显示全部楼层
  1. 第二轮第一题:.1point3acres缃
  2. dp[i][j]=dp[i][j-1]+sum, where sum is the cumulative sum of the elements on top of matrix[i][j]
复制代码
回复 支持 反对

使用道具 举报

e5399014 发表于 2015-12-28 04:07:39 | 显示全部楼层
你有结果了么
回复 支持 反对

使用道具 举报

 楼主| wukey 发表于 2015-12-28 11:48:44 | 显示全部楼层
面试三天后得到进pool的消息
回复 支持 反对

使用道具 举报

rchen29 发表于 2015-12-30 14:40:44 | 显示全部楼层
楼主 请问电面一般都是两道题吗
回复 支持 反对

使用道具 举报

 楼主| wukey 发表于 2015-12-31 05:30:45 | 显示全部楼层
rchen29 发表于 2015-12-30 14:40
楼主 请问电面一般都是两道题吗

据我所知,每轮一般是两道题
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-4 06:37:42 | 显示全部楼层
写了下第一题的代码. more info on 1point3acres.com
  1. public class BinayTreeExpressString {
  2.        
  3.         static class Node {
  4.                 int val;
  5.                 Node left;
  6.                 Node right;
  7.                 public Node(int val) {
  8.                         this.val = val;
  9.                 }
  10.         }
  11.         public static  Node useBinayTreeExpressString(String str) {
  12.                 if (str == null || str.length() == 0) {
  13.                         return null;
  14.                 }
  15.                 if (str.length() == 1) {
  16.                         return new Node(Integer.valueOf(str.charAt(0)));
  17.                 }
  18.                 int len = str.length();. from: 1point3acres.com/bbs
  19.                 int level = (int)(Math.log(len) / Math.log(2));
  20.                 Node root = new Node(-1);
  21.                 int index = 0;
  22.                 Queue<Node> queue = new LinkedList<Node>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.                 queue.offer(root);
  24.                 System.out.println(level);
  25.                 while (index < level) {
  26.                         index++;
  27.                         if (index < level) {
  28.                                 int size = queue.size(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.                                 for (int i = 0; i < size; i++) {-google 1point3acres
  30.                                         Node cur = queue.poll();
  31.                                         cur.left = new Node(-1);
  32.                                         queue.offer(cur.left);
  33.                                         cur.right = new Node(-1);
  34.                                         queue.offer(cur.right);.1point3acres缃
  35.                                 }
  36.                         } else {
  37.                                 for (int i = 0; i < str.length();) {
  38.                                         Node cur = queue.poll();
  39.                                         cur.left = new Node((str.charAt(i++) - '0'));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  40.                                         if (i < str.length()) {
  41.                                                 cur.right = new Node((str.charAt(i++) - '0'));
  42.                                         }. 1point 3acres 璁哄潧
  43.                                 }
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  44.                         }
  45.                 }
  46.                 return root;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  47.         }
  48.         public static Node useBinayTreeExpressStringFollowUp(String str) {
  49.                 if (str == null || str.length() == 0) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  50.                         return null;
  51.                 }
  52.                 if (str.length() == 1) {
  53.                         return new Node((str.charAt(0) - '0'));
  54.                 }
  55.                 return helper(str, 0, str.length() - 1);.1point3acres缃
  56.         }
  57.         private static Node helper(String str, int start, int end) {
  58.                 if (start > end) {
  59.                         return null;
  60.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  61.                 if (start == end || isAllTheSame(str, start, end)) {
  62.                         return new Node((str.charAt(start) - '0'));
  63.                 }
  64.                 int mid = (end - start) / 2 + start;
  65.                 Node node = new Node(-1);
  66.                 node.left = helper(str, start, mid);
  67.                 node.right = helper(str, mid + 1, end);
  68.                 return node;. 1point 3acres 璁哄潧
  69.         }
  70.         private static boolean isAllTheSame(String str, int start, int end) {
  71.                 char c = str.charAt(start++);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  72.                 while (start <= end) {. 1point3acres.com/bbs
  73.                         if (str.charAt(start) != c) {
  74.                                 return false;
  75.                         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  76.                         start++;
  77.                 }
  78.                 return true;
  79.         }
  80.        
  81.         public static void print(Node node) {
  82.                 if (node == null) {
  83.                         return;
  84.                 }
  85.                 print(node.left);
  86.                 if (node.left == null && node.right == null) {
  87.                         System.out.print(node.val);
  88.                 }
  89.                 print(node.right);
  90.         }
  91.         public static void printTree(Node node) {
  92.                 if (node == null) {
  93.                         return;
  94.                 }
  95.                 printTree(node.left);.1point3acres缃
  96.                         System.out.print(node.val);
  97.                 printTree(node.right);
  98.         }
  99.         public static void main(String[] args) {
  100. //                Node node = useBinayTreeExpressString("1011");
  101.                 Node node = useBinayTreeExpressStringFollowUp("1011");
  102.                 printTree(node);
  103.         }
  104. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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