May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1679|回复: 11
收起左侧

11/23 Google 面经

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

2016(7-9月) 码农类 本科 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
昨天刚面的google,题目其实比较简单。但是因为我本来没想找实习,之前跟人随意说起就被内推然后安排面试了,所以没怎么准备,只大概过了一遍基本要考的数据结构和算法,cc和leetcode上看了一点点题。

一面: 美国白人:
第一个大叔晚了大概五到六分钟开始的。自我介绍以后就直接做题。android pin 如果输入一系列密码, 不能有重复,不能少于四个,然后看密码是不是valid。
比如键盘如下:
012
345
678

然后如果你输02。。。是不可以的, 因为1 是obstruction。
我刚开始纠结了一下怎么做,卡了有点久。然后后来想出来比较笨的方法去做,但是跟面试官讨论test case的时候 发现他其实清除obstruction以后你也可以走对角线方向的密码。 但是我之前只考虑了horizontal 和 vertical。 这个时候没什么时间了,跟他讲了一下怎么fix bug 就挂了····

第二个是一个中国女生, 特别特别感谢她,一直跟我讨论到底我该怎么做。 其实真的是我太菜,又是第一次面试,所以在面试的过程中脑子一直不在线上。希望面试的姐姐看到可以感受到我的感谢。
第二个就是binary search tree, 给一个target sum, 看里面包不包含两个数可以达到这个target sum,有duplicate。
.鐣欏璁哄潧-涓浜-涓夊垎鍦follow up:因为我们会有很多可选的组合,找一个pair的差是最大的。因为我inorder, 所以找到的第一个其实就是差最大的。. 鍥磋鎴戜滑@1point 3 acres
然后也问了time 和 space complexity。

最后最后希望可以通过发面经攒rp吧,知道自己应该没什么戏,但是还是会想如果可以被加面就好了。之后还有bb的面试,如果g家没过就当给b家攒rp了。

评分

1

查看全部评分

 楼主| jacyjia 发表于 2015-11-26 01:52:01 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
crisc3 发表于 2015-11-25 15:27.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主 第一题求的是总共多少种可能吗?能否详细讲一下呢
关于BST那个 感觉是inorder弄成一个array之后 再用 ...

不是的 第一个就是看是不是一个valid的密码 比如我输0234 就不行 因为0和2 直接有一个obstruction是1.
就是你输入一个数字以后 比如我先输1 那么1 周围的都可以走了 包括横竖和对角线 我当时没想到对角线 做完以后他才跟我说也要算对角线的···而且我全程跟他讲的时候他都不跟我说我的思路对不对之类的····

第二个我就是用一个arraylist把树存了一遍 然后因为要考虑duplicate就又加了一个hashmap存每个数的个数。
所以我的方法就是O(N).而且不用两个pointer啊 直接用arraylist里面contains就是target-现在的数, 查看是不是在这个arraylist里面就行了
回复 支持 1 反对 0

使用道具 举报

crisc3 发表于 2015-11-25 15:27:13 | 显示全部楼层
关注一亩三分地微博:
Warald
楼主 第一题求的是总共多少种可能吗?能否详细讲一下呢. 鍥磋鎴戜滑@1point 3 acres
关于BST那个 感觉是inorder弄成一个array之后 再用two pointer做?这样是O(N) time, O(N) space 或者inorder每一个数,然后搜索sum-num 这样O(NlogN) time O(1) space 不知道有没有其他好的做法 请指教
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-11-26 06:03:53 | 显示全部楼层
jacyjia 发表于 2015-11-26 01:52
不是的 第一个就是看是不是一个valid的密码 比如我输0234 就不行 因为0和2 直接有一个obstruction是1. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
arraylist 的 contains()复杂度是O(n)的吧,要全部便利一遍
回复 支持 反对

使用道具 举报

 楼主| jacyjia 发表于 2015-11-26 09:47:08 | 显示全部楼层
yjfox 发表于 2015-11-26 06:03
arraylist 的 contains()复杂度是O(n)的吧,要全部便利一遍

也对·····其实直接最开始用hashmap存就行 不用弄两遍 我刚开始没有做duplicate duplicate是后面follow up的时候加的
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-11-29 02:49:22 来自手机 | 显示全部楼层
第一题应该就可以hashmal存每个数字可以reach的数字,然后就扫描一次,检查每一个数字的下一位是合理的就行了吧
回复 支持 反对

使用道具 举报

 楼主| jacyjia 发表于 2015-11-29 15:11:27 | 显示全部楼层
bobzhang2004 发表于 2015-11-29 02:49
第一题应该就可以hashmal存每个数字可以reach的数字,然后就扫描一次,检查每一个数字的下一位是合理的就行 ...

也行吧 我是做了一个array/matrix, 存status,可以和不可以。 第一个直接放入,更新可以到达的。 后面的现查所在的位置的值是可以还是不可以,如果是可以的话继续更新,不可以直接return false
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-1 06:28:22 | 显示全部楼层
binary search tree, 给一个target sum这题是用两个stack,然后一个放最小的node, 一个放最大得node,然后就像两个指针一样来找吗? sum>target, right--; sum < target, left++,一样?时间复杂度是O(n),空间复杂度是O(n)?如果是单纯的bianry search,是O(nlgn)
回复 支持 反对

使用道具 举报

 楼主| jacyjia 发表于 2015-12-1 07:23:33 | 显示全部楼层
bobzhang2004 发表于 2015-12-1 06:28
binary search tree, 给一个target sum这题是用两个stack,然后一个放最小的node, 一个放最大得node,然后 ...

我直接inorder traversal了···O(N) 存node进arraylist 再走一次hashmap存node 和frequency(因为要查duplicate的情况,且containsO(1))
然后从头开始 直接用hashmap containskey 查 target-current node存在与否 O(N).
所以时间空间都是O(N)
不过也可以two pointers直接走arraylist不用存进hashmap我觉得···当时没想那么多直接弄了hashmap
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-1 09:31:54 | 显示全部楼层
楼主这个办法应该可以。我是看过一个帖说要求不用多余的arraylist/array来做
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-1 09:45:20 | 显示全部楼层
写了下code,感觉如果可以用arraylist的话就比较简单了
  1. static class TreeNode {
  2.                 TreeNode left;
  3.                 TreeNode right;
  4.                 int val;
  5.                 public TreeNode(int val) {
  6.                         this.val = val;
  7.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.         }
  9.         public static List<TreeNode> getTwoSumInBST(TreeNode root, int target) {
  10.                 List<TreeNode> res = new ArrayList<TreeNode>();
  11.                 List<TreeNode> nodes = new ArrayList<TreeNode>();
  12.                 getNodes(root, nodes);
  13.                 int left = 0;
  14.                 int right = nodes.size() - 1;
  15.                 while (left < right) {
  16.                         int sum = nodes.get(left).val + nodes.get(right).val;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  17.                         if (sum == target) {
  18.                                 res.add(nodes.get(left));
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.                                 res.add(nodes.get(right));
  20.                                 for (TreeNode n : res) {. 鍥磋鎴戜滑@1point 3 acres
  21.                                         System.out.println(n.val);
  22.                                 }
  23.                                 return res;
  24.                         } else if (sum > target) {
  25.                                 right--;. From 1point 3acres bbs
  26.                         } else {
  27.                                 left++;
  28.                         }
  29.                 }
  30.                
  31.                 return res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  32.         }
  33.        
  34.        
  35.         private static void getNodes(TreeNode root, List<TreeNode> nodes) {
  36.                 if (root == null) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  37.                         return; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  38.                 }
  39.                 getNodes(root.left, nodes);-google 1point3acres
  40.                 nodes.add(root);. visit 1point3acres.com for more.
  41.                 getNodes(root.right, nodes);. 1point 3acres 璁哄潧
  42.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jacyjia 发表于 2015-12-1 09:58:56 | 显示全部楼层
bobzhang2004 发表于 2015-12-1 09:31
楼主这个办法应该可以。我是看过一个帖说要求不用多余的arraylist/array来做
. Waral 鍗氬鏈夋洿澶氭枃绔,
我当时问她可不可以把node全部放在arraylist里面 她允许了 就比较简单 然后我也没想不放的解法 多谢你的code~
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-24 10:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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