一亩三分地论坛

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

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

谷歌面经

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

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

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

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

x
楼主在国内面的。
. 1point 3acres 璁哄潧
第一轮电面,老外,美国口音:. 鍥磋鎴戜滑@1point 3 acres
1,很多文件里面有很多数字,设计排序的算法,答了个外排序的归并,接着问很多机器怎么进一步优化。楼主不懂Map-Reduce就YY了一通。那边又要求希望两个Iterator做完所有排序,然后瞎扯了一会这题就这么过了。。。
2,写一个函数Children(Node *r)输出BST的当前节点的所有儿子。递归和非递归,哪个快怎样优化之类的问了问,就结束了。-google 1point3acres
第二轮电面,中文:
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),写完解释了一会就算结束了。. From 1point 3acres bbs
2,一些人排成队,每个人知道自己前面有多少个人比自己高。已知每个人的身高。要求根据这些信息求出原先排好的队。
贪心算法,证明了挺久,最后写完解释了一下就说时间到了,估计想的太久了就被BS了。

评分

3

查看全部评分

samantha_kr 发表于 2015-2-27 14:06:38 | 显示全部楼层
LZ二叉树那题咋做的啊。。递归都不会。。。求指导
回复 支持 1 反对 0

使用道具 举报

MTC 发表于 2014-11-5 22:11:02 | 显示全部楼层
LZ研三吗?你用C++面的?
回复 支持 反对

使用道具 举报

CrazyCow 发表于 2014-11-5 22:58:30 | 显示全部楼层
第二题 从高到低考虑,  不就好了?
写的话 用list?
我理解的对吗 ? 有坑?
回复 支持 反对

使用道具 举报

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

使用道具 举报

averillzheng 发表于 2014-11-6 06:55:04 | 显示全部楼层
kuyen 发表于 2014-11-6 03:27
楼主,onsite第一轮可以详细说下思路吗?第二轮有O(N) 解法?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
排队的那题,可以从高往低排。时间复杂度是O(n^2).
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-6 06:55:11 | 显示全部楼层
kuyen 发表于 2014-11-6 03:27. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主,onsite第一轮可以详细说下思路吗?第二轮有O(N) 解法?

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

使用道具 举报

还来得及吗 发表于 2014-11-6 09:54:47 | 显示全部楼层
排队那题没明白意思 lz可以再说下吗

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

使用道具 举报

sailorconan 发表于 2014-11-6 11:03:01 | 显示全部楼层
还来得及吗 发表于 2014-11-6 09:54
排队那题没明白意思 lz可以再说下吗

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

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

使用道具 举报

kuyen 发表于 2014-11-6 12:49:37 | 显示全部楼层
averillzheng 发表于 2014-11-6 06:55
排队的那题,可以从高往低排。时间复杂度是O(n^2).

如果是O(N^2)的话,可以直接对身高sort吗?这样还能达到O(NlogN)
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-6 13:08:53 | 显示全部楼层
kuyen 发表于 2014-11-6 12:49
如果是O(N^2)的话,可以直接对身高sort吗?这样还能达到O(NlogN)

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

使用道具 举报

kuyen 发表于 2014-11-6 13:22:05 | 显示全部楼层
averillzheng 发表于 2014-11-6 13:08. from: 1point3acres.com/bbs
n^2的时间只要是我在做的时候选择了list来return结果,每次insert元到list的时候。list的insert不是时间1 ...

I see. 但是用array来做,其实也是O(N^2)。所以我想有没有更好的办法
回复 支持 反对

使用道具 举报

byrlhb 发表于 2014-11-6 15:01:35 | 显示全部楼层
averillzheng 发表于 2014-11-6 06:55
排队的那题,可以从高往低排。时间复杂度是O(n^2).

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

使用道具 举报

averillzheng 发表于 2014-11-7 01:03:24 | 显示全部楼层
byrlhb 发表于 2014-11-6 15:01
那个比较tree的问题,你有没有什么想法,我怎么没有太看懂题

目前没有
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| 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)的就不知道了。
第一轮感觉也是有优化空间的,根据树形的拓扑关系有很多项其实可以不用比较的。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

MTC 发表于 2014-11-7 21:24:17 | 显示全部楼层
zombiecry 发表于 2014-11-7 15:58
是的。研三,我几轮都是C++。不过在google doc上写代码也不需要编译,所以语言其实不重要。

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

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

zhenggao1986 发表于 2014-11-8 15:07:33 | 显示全部楼层
排队的那个题,答案不唯一啊!

import java.util.Arrays;
import java.util.Comparator;.鏈枃鍘熷垱鑷1point3acres璁哄潧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
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];-google 1point3acres
        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) {. visit 1point3acres.com for more.
                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)
                System.out.print(p.higherBefore + " ");
        System.out.println("\n");
}
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
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);. 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
}
}
原始队列为 8 3 5 6 9 1 2 7 4
我写的算法输出如下,也符合要求,所以答案不唯一
Height: 8 2 3 5 6 1 4 9 7
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 01:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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