一亩三分地论坛

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

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

Google电面

[复制链接] |试试Instant~ |关注本帖
夜行码农耗子 发表于 2015-10-5 04:38:47 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
九月十五号第一轮电面
题目:给一个先递增后递减的数组,找到最大值。题很简单但是没答好,题目里面有个不认识的单词当时偷懒没有问面试官,写了个Binary Search之后面试官问我如果输入是1233321怎么办,我说这输入是invalid啊,面试官微微一笑说这数组是非严格递增递减,也就是说有重复。我改完之后时间就到了=-=. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
因为第一面答的不好,九月三十号让面了第二轮。
第一题Moving Average.很简单,题目说给的是一个stream,求前K个数的平均值,这个题看到过挺多次的但是好像没有看到标准的答案,这里说说我的方法反正面试官觉得是对的。。就是用个dequeue存K个数就行了。. From 1point 3acres bbs
第二题说了一大堆,大概意思就是他给你一个URL让你求这个URL访问到的页面的和。面试官给了一个API,输入URL返回URL所连接到的URL,做法也很简单就是写个DFS然后调用这个API,再用个Set去重就好了。
题目都不难,没多大参考价值,但是希望能帮到大家一点。
祝大家找工顺利!

评分

3

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 夜行码农耗子 发表于 2015-10-5 04:40:15 | 显示全部楼层
第二题的API大概是 vector<string> Find(const string &URL)
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-5 14:03:58 | 显示全部楼层
哈哈,第二题我在MS面试遇到过~
回复 支持 反对

使用道具 举报

goo 发表于 2015-10-5 21:16:18 | 显示全部楼层
如果有重复该怎么办呢?难道要while(num[i]==nums[i-1]) i++; 找到不重复的吗?
回复 支持 反对

使用道具 举报

readman 发表于 2015-10-5 22:02:21 | 显示全部楼层
goo 发表于 2015-10-5 21:16
如果有重复该怎么办呢?难道要while(num==nums) i++; 找到不重复的吗?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
- - 为什么......
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-10-5 22:27:56 来自手机 | 显示全部楼层
有重复的话。直接for loop?
回复 支持 反对

使用道具 举报

goo 发表于 2015-10-5 23:04:06 | 显示全部楼层

不懂啊 瞎猜的 有重复怎么办了?
回复 支持 反对

使用道具 举报

yyboyz 发表于 2015-10-5 23:11:41 | 显示全部楼层
楼主你好 你是new grad吗? 面加州的还是纽约的?
回复 支持 反对

使用道具 举报

goo 发表于 2015-10-5 23:18:49 | 显示全部楼层

我的想法是这样的  binary search
left=0,right=n;. 鍥磋鎴戜滑@1point 3 acres
比较num[mid]和num[mid-1] num[mid+1]的大小关系
如果num[mid-1]<num[mid]<num[mid+1] 处在上升 left=mid+1;
num[mid-1]>num[mid]>num[mid+1]在下降 right=mid-1;
如果num[mid-1]<num[mid]>num[mid+1] 找到最大值 为num[mid];
. from: 1point3acres.com/bbs
但是num[mid]是重复就不能比较了 所以我想用while() 找到不重复的那个再比较
但感觉应该有更好的方法
回复 支持 反对

使用道具 举报

yyboyz 发表于 2015-10-5 23:38:24 | 显示全部楼层
google 就爱考变种题
第一题: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

public int findMax(int[] input) {

                int low = 0;. From 1point 3acres bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
                int high = input.length - 1;

                while (low + 1 < high) {
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        int mid = (low + high) / 2;

                        // the input[mid] is larger than the first element, then discard
                        // left part
. from: 1point3acres.com/bbs
                        if (input[mid] > input[low]) {

                                low = mid;
. 1point 3acres 璁哄潧
                        } else if (input[mid] < input[low]) {

                                // the input[mid] is smaller than the first element, then
                                // discard right part

                                high = mid;

                        } else {

                                // same

                                low++;

                        }
.1point3acres缃
                }

                return input[low] > input[high] ? input[low] : input[high];

        }
回复 支持 反对

使用道具 举报

readman 发表于 2015-10-5 23:48:24 | 显示全部楼层
yyboyz 发表于 2015-10-5 23:38
google 就爱考变种题. visit 1point3acres.com for more.
第一题:

这个是变种么?
以下代码为啥不行?
public static int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;

        while( l <= r) {
            if(l == r)
                return nums[l];
            int mid = (l + r) / 2;
            if(nums[mid] < nums[mid+1])
                l = mid + 1;
            else
                r = mid;
        }
        return -1;
    }. from: 1point3acres.com/bbs

补充内容 (2015-10-5 23:49):
哦- -  刚看到楼主回复
回复 支持 反对

使用道具 举报

readman 发表于 2015-10-5 23:57:29 | 显示全部楼层
readman 发表于 2015-10-5 23:48
这个是变种么?
以下代码为啥不行?
public static int findPeakElement(int[] nums) {

这个呢....1point3acres缃

public static int findPeakElement(int[] nums) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        int l = 0;. 1point3acres.com/bbs
        int r = nums.length - 1;

        while( l <= r) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            if(l == r)
                return nums[l];
            int mid = (l + r) / 2;. 鍥磋鎴戜滑@1point 3 acres
            if(nums[mid] > nums[l])
                l = mid;
            else
                r = mid;
        }
        return -1;
    }
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-6 01:56:42 | 显示全部楼层
其实第一题很简单,如果有重复的话,就跟面试官分析一下,说复杂度就达不到O(logn),因为有重复元素,如果两相邻的数比较不出此时是在递减,或者递增区间,此时只能局部的for loop一下直到分辨出中点是在递增或是递减(如果用二分查找的话),但实际上这时候worst case就是O(n)了,所以最简单的方法,直接for loop一次就好。
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-10-6 11:52:29 | 显示全部楼层
zxy_snow 发表于 2015-10-5 14:03
哈哈,第二题我在MS面试遇到过~
.鏈枃鍘熷垱鑷1point3acres璁哄潧
哈哈,并不难
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-10-6 11:54:53 | 显示全部楼层
goo 发表于 2015-10-5 21:16
如果有重复该怎么办呢?难道要while(num==nums) i++; 找到不重复的吗?

有一个题是find range,这个题有重复的情况下跟那个差不多,就是向左向右继续二分找到这个数结束的地方,然后继续判断。所以其实虽然是个挺简单的题但是写起来挺麻烦的。我开始用的你的方法面试官说不行~
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-10-6 11:55:30 | 显示全部楼层
bobzhang2004 发表于 2015-10-5 22:27
有重复的话。直接for loop?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
有重复的话继续Binary Search啊,只不过向左和向右的要分开写
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-10-6 11:55:41 | 显示全部楼层
yyboyz 发表于 2015-10-5 23:11
楼主你好 你是new grad吗? 面加州的还是纽约的?
. From 1point 3acres bbs
New Grad,加州
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-10-6 11:59:37 | 显示全部楼层
pengzewen37 发表于 2015-10-6 01:56. from: 1point3acres.com/bbs
其实第一题很简单,如果有重复的话,就跟面试官分析一下,说复杂度就达不到O(logn),因为有重复元素,如果两 ...

我是这么和面试官说的,面试官不太满意,其实可以继续二分查找的,对于左侧重复和右侧重复的分别写一个Binary Search找到边界然后继续比较就好了,这样下来其实还是Logn.因为你找到边界如果不符合的话可以按照这个更新左右边界继续找(跳过重复的部分)
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-10-6 13:13:51 | 显示全部楼层
是找peak element吗?
回复 支持 反对

使用道具 举报

yyboyz 发表于 2015-10-7 00:23:54 | 显示全部楼层
夜行码农耗子 发表于 2015-10-6 11:59
我是这么和面试官说的,面试官不太满意,其实可以继续二分查找的,对于左侧重复和右侧重复的分别写一个Bi ...

你好楼主,
我觉得你说的可能有误。

首先如果有重复元素 靠判断中点和左右两点是不能找到最大值的, e.g.,
55555555585
58555555555
这两个序列都符合要求(先增后减) 但你无法判断哪边该舍去

如果你说按照二分法去递归找左右两边
那么树的高度是lgN
每次都要搜索N个元素
复杂度是O(NlgN) >O(N) . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

很容易理解 就是merge sorting的模型
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 07:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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