要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 5468|回复: 37
收起左侧

谷歌面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
zombiecry 发表于 2014-11-5 21:50:45 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类General 硕士 全职@Google - 校园招聘会 - 技术电面  | Other |

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

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

x
楼主在国内面的。

第一轮电面,老外,美国口音:
1,很多文件里面有很多数字,设计排序的算法,答了个外排序的归并,接着问很多机器怎么进一步优化。楼主不懂Map-Reduce就YY了一通。那边又要求希望两个Iterator做完所有排序,然后瞎扯了一会这题就这么过了。。。
2,写一个函数Children(Node *r)输出BST的当前节点的所有儿子。递归和非递归,哪个快怎样优化之类的问了问,就结束了。
第二轮电面,中文:
1,FindCloset(flaot a[],length,target),有序表找最接近数字,这个简单二分查找,写完他也没说什么。
2,数组加一个数,比如[2,3,4,5] + 45=[2,3,9,0]。DT的是只能用数组不能用vector,在加完还有进位的时候需要重新new空间,很快写完以后又让优化了几遍。onsite两轮后跪了,各一个算法题,都是中文,估计跪在了第二轮上,
1,给一个二叉树,让找出所有相同的子树。
先说了枚举所有节点对然后递归判断的n^3简单方法,面试官不满意,然后用memo优化到O(n^2),写完解释了一会就算结束了。
2,一些人排成队,每个人知道自己前面有多少个人比自己高。已知每个人的身高。要求根据这些信息求出原先排好的队。
贪心算法,证明了挺久,最后写完解释了一下就说时间到了,估计想的太久了就被BS了。

评分

3

查看全部评分


上一篇:Google phone interview
下一篇:人生第一次电面
我的人缘0
samantha_kr 发表于 2015-2-27 14:06:38 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
LZ二叉树那题咋做的啊。。递归都不会。。。求指导
回复 支持 1 反对 0

使用道具 举报

我的人缘0
MTC 发表于 2014-11-5 22:11:02 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
LZ研三吗?你用C++面的?
回复 支持 反对

使用道具 举报

我的人缘0
CrazyCow 发表于 2014-11-5 22:58:30 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第二题 从高到低考虑,  不就好了?
写的话 用list?
我理解的对吗 ? 有坑?
回复 支持 反对

使用道具 举报

我的人缘0
kuyen 发表于 2014-11-6 03:27:00 | 显示全部楼层
楼主,onsite第一轮可以详细说下思路吗?第二轮有O(N) 解法?
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-6 06:55:04 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
kuyen 发表于 2014-11-6 03:27
楼主,onsite第一轮可以详细说下思路吗?第二轮有O(N) 解法?

排队的那题,可以从高往低排。时间复杂度是O(n^2).
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-6 06:55:11 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
kuyen 发表于 2014-11-6 03:27
楼主,onsite第一轮可以详细说下思路吗?第二轮有O(N) 解法?

排队的那题,可以从高往低排。时间复杂度是O(n^2).
回复 支持 反对

使用道具 举报

我的人缘0
还来得及吗 发表于 2014-11-6 09:54:47 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
排队那题没明白意思 lz可以再说下吗

补充内容 (2014-11-6 10:00):
懂了。。就是从高往后然后根据情况插入第k个人。。另外相同子数那个hash tree如何
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
sailorconan 发表于 2014-11-6 11:03:01 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
还来得及吗 发表于 2014-11-6 09:54
排队那题没明白意思 lz可以再说下吗

补充内容 (2014-11-6 10:00):

结果多种,求出其中一个就行吧
回复 支持 反对

使用道具 举报

我的人缘0
kuyen 发表于 2014-11-6 12:49:37 | 显示全部楼层
averillzheng 发表于 2014-11-6 06:55
排队的那题,可以从高往低排。时间复杂度是O(n^2).
. 一亩-三分-地,独家发布
如果是O(N^2)的话,可以直接对身高sort吗?这样还能达到O(NlogN)
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-6 13:08:53 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
kuyen 发表于 2014-11-6 12:49
如果是O(N^2)的话,可以直接对身高sort吗?这样还能达到O(NlogN)

n^2的时间只要是我在做的时候选择了list来return结果,每次insert元到list的时候。list的insert不是时间1的运算。
回复 支持 反对

使用道具 举报

我的人缘0
kuyen 发表于 2014-11-6 13:22:05 | 显示全部楼层
averillzheng 发表于 2014-11-6 13:08
n^2的时间只要是我在做的时候选择了list来return结果,每次insert元到list的时候。list的insert不是时间1 ...
.本文原创自1point3acres论坛
I see. 但是用array来做,其实也是O(N^2)。所以我想有没有更好的办法
回复 支持 反对

使用道具 举报

我的人缘0
byrlhb 发表于 2014-11-6 15:01:35 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
averillzheng 发表于 2014-11-6 06:55
排队的那题,可以从高往低排。时间复杂度是O(n^2).

那个比较tree的问题,你有没有什么想法,我怎么没有太看懂题
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-7 01:03:24 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
byrlhb 发表于 2014-11-6 15:01
那个比较tree的问题,你有没有什么想法,我怎么没有太看懂题

目前没有
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| zombiecry 发表于 2014-11-7 14:30:37 | 显示全部楼层
CrazyCow 发表于 2014-11-5 22:58
第二题 从高到低考虑,  不就好了?. 牛人云集,一亩三分地
写的话 用list?
我理解的对吗 ? 有坑?

我的解法是按已知比自己高的人数从低往高排。按身高从高往低应该也是可以的,优化一下应该能到O(nlogn)。
这个题想出做法容易,就是要证明贪心的正确性有些绕。当时我就是想证明想了蛮久,后来想想其实当时也有点把自己绕进去了。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| zombiecry 发表于 2014-11-7 14:33:00 | 显示全部楼层
kuyen 发表于 2014-11-6 03:27
楼主,onsite第一轮可以详细说下思路吗?第二轮有O(N) 解法?

我的想法就是用一个二维数组isSame[p][q]来记录每个p,q对比较的结果。然后枚举所有顶点对,每次还是递归比较,但是比较的过程填表,下次再比较填过的可以直接返回结果。这个数组最多被填n^2次。所以是n^2。
.留学论坛-一亩-三分地
补充内容 (2014-11-7 15:57):
第二轮一般容易想到的都是n^2的贪心,估计优化一下能到nlogn,O(n)的就不知道了。
第一轮感觉也是有优化空间的,根据树形的拓扑关系有很多项其实可以不用比较的。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| zombiecry 发表于 2014-11-7 15:58:19 | 显示全部楼层
MTC 发表于 2014-11-5 22:11
LZ研三吗?你用C++面的?

是的。研三,我几轮都是C++。不过在google doc上写代码也不需要编译,所以语言其实不重要。
回复 支持 反对

使用道具 举报

我的人缘0
MTC 发表于 2014-11-7 21:24:17 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
zombiecry 发表于 2014-11-7 15:58
是的。研三,我几轮都是C++。不过在google doc上写代码也不需要编译,所以语言其实不重要。

我好像知道你是谁了。。。P大的不?
回复 支持 反对

使用道具 举报

我的人缘0
kuyen 发表于 2014-11-7 22:44:31 | 显示全部楼层
zombiecry 发表于 2014-11-7 14:33
我的想法就是用一个二维数组isSame[q]来记录每个p,q对比较的结果。然后枚举所有顶点对,每次还是递归比较 ...

一维数组就可以了。从后往前依次把各个元素放到对应的位置上。最后一个很容易,直接放到n-k-1,n是总人数,k是前面比他高的人。倒数第二个需要从数组尾部走k步,但是每次遇到之前排好的元素,跳过不算步数。复杂度是O(N^2);O(nlogn)的话直接sort就行了,除非不让。再快的方法就不知道了
回复 支持 反对

使用道具 举报

我的人缘0
CrazyCow 发表于 2014-11-8 12:56:26 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
zombiecry 发表于 2014-11-7 14:30
我的解法是按已知比自己高的人数从低往高排。按身高从高往低应该也是可以的,优化一下应该能到O(nlogn)。 ...

是啊  可以的 用线段树什么的
回复 支持 反对

使用道具 举报

我的人缘0
zhenggao1986 发表于 2014-11-8 15:07:33 | 显示全部楼层
排队的那个题,答案不唯一啊!. 留学申请论坛-一亩三分地

import java.util.Arrays;
import java.util.Comparator;

class Person {
        public int height, higherBefore;
        public Person(int h, int hb) {
                height = h;
                higherBefore = hb;. 一亩-三分-地,独家发布
        }
}; 来源一亩.三分地论坛.

public class Test {

public static void swap(Person[] array, int i, int j) {
        if (array == null || array.length == 0 || i == j) return;
        Person tmp = array[i];
        array[i] = array[j];. 1point 3acres 论坛
        array[j] = tmp;
}

public static void lineUp(Person[] array) {
        Comparator<Person> personComparator = new Comparator<Person>() {
                public int compare(Person p1, Person p2) {return p2.height - p1.height;} 来源一亩.三分地论坛.
        };
        Arrays.sort(array, personComparator);
        for (int i = 1; i < array.length; ++i) {
                int higherBefore = 0, shiftLeft = i;
                for (int j = 0; j < i; ++j)
                        if (array[j].height > array[i].height) ++higherBefore;
                while (higherBefore > array[shiftLeft].higherBefore && shiftLeft > 0) {
                        if (array[shiftLeft - 1].height > array[shiftLeft].height) --higherBefore;
                        swap(array, shiftLeft, shiftLeft - 1);
                        --shiftLeft;
                }
        }
}

public static void print(Person[] array) {
        System.out.print("Height: ");
        for (Person p : array)
                System.out.print(p.height + " ");
        System.out.print("\nHigher: ");
        for (Person p : array). from: 1point3acres
                System.out.print(p.higherBefore + " ");
        System.out.println("\n");
}
. Waral 博客有更多文章,
public static void main(String[] args) {
        // 8 3 5 6 9 1 2 7 4
        Person[] array = {new Person(5, 1), new Person(2, 1), new Person(9, 0),
                          new Person(8, 0), new Person(4, 3), new Person(1, 5),
                          new Person(7, 2), new Person(6, 1), new Person(3, 1)};
        print(array);
        lineUp(array);
        print(array);
. more info on 1point3acres
}
}
原始队列为 8 3 5 6 9 1 2 7 4
我写的算法输出如下,也符合要求,所以答案不唯一
Height: 8 2 3 5 6 1 4 9 7
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-27 22:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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