一亩三分地论坛

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

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

这周二8月25日 G家onsite

[复制链接] |试试Instant~ |关注本帖
mhbkb 发表于 2015-8-29 05:33:32 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 sanguine 于 2015-9-3 22:13 编辑

去年三轮实习面挂了,一个月前hr主动联系,直接给了onsite, 别问我为啥,我也不知道。
1. 中东或者东欧人
   1.1 热身题  从root开始求树的longest increase sequence number length   简单的dfs解决,写出了个bug,坑爹.
   1.2 一个数组,可在数中间插入+或-,输出所有可能的结果。  如input:[1, 2, 3]  可能的结果是:1+2+3=6, 1+2-3=0, 1-2+3=2, 1-2-3=-4    先讲了个dfs解法, 复杂度2^n, 后来想到了dp解法,最优是n^3, 最坏还是2^n.. from: 1point3acres.com/bbs

2. 美国小白
   + + - - 面经题   先写List<String> nextMove(String input), 讨论了好久StringBuilder的实现; 再写boolean canWin(String input), 让写test case.

lunch是个加拿大华裔,小哥比较闷,不过聊了好多,工作生活学习都有聊。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3. 可能是个ABI,全程态度很一般,感觉要被他黑
   3.1 插一个char到一个string里,求出这个插入的char.  如: 'abcd', 'abcxd' 返回 'x'. 先讲了个HashMap的,要extra space. 后来讲了个可以把char加起来作差,小哥说也可以乘起来作除。 follow up是如果插入两个char,怎么求,把作差的和作除的结合起来就行,不需要extra space. 小哥很满意,但他没拍照,没拍照。。。
   3.2 popular number.  讨论了好久,小哥说还不错,但就留了5分钟让写个binary search left boundry 的code. 写完说应该没bug, 就拍了个照走了。

4. 一个工作5年的白人带一个白人小妹妹shadow
   题目是给两个RPC method: Collection<String> getAppIds(String userId);  Status deliverToLibray(String appId);
   要求写一个暴露给前端的方法: 根据userId把对应的appId都deliver到libray里.
   主要考:1,不同情况下的异常捕获,retry机制  2, 定义友好的返回Enum,通知用户  3. 多线程
   写了两大白板,面试官还挺满意.

总体上感觉,G家的面试官都很聪明,全程一直在互动,他们反映都很快,给的提示也很在点。这次onsite从他们身上能学到不少东东。


加分++++++. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


补充内容 (2015-9-3 12:04):
今天打电话说要不要考虑tools的职位,我说算了,别家的deadline要到了。。。    好郁闷,总体面得感觉很好,code也写了好多。   只有可能第三轮被三哥黑了。。。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

宝贝忆彼岸 发表于 2015-9-4 22:00:58 | 显示全部楼层
求lz 1.2题DP解法的思路
回复 支持 反对

使用道具 举报

lll_2013 发表于 2015-9-5 05:52:53 | 显示全部楼层
我感觉第1.2题可能可以建深度为n 的tree来实现dp,往左边表示+, 右边表示-。
回复 支持 反对

使用道具 举报

 楼主| mhbkb 发表于 2015-9-6 07:12:39 | 显示全部楼层
宝贝忆彼岸 发表于 2015-9-4 06:00
求lz 1.2题DP解法的思路

dp = dp[i-1] 加或减 A    这里的dp是HashSet, 每次迭代一遍dp[i-1]的HashSet.   如果数组是1,2,3,4,...n, 那么复杂度就是O(n^3); 如果数组类似1, 2, 4, 8, ..., 2^n,  那么复杂度就是O(2^n)
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-9-6 07:37:54 | 显示全部楼层
什么叫“tools的职位“?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-6 08:29:12 | 显示全部楼层
没拍照意味着什么?
回复 支持 反对

使用道具 举报

 楼主| mhbkb 发表于 2015-9-6 13:53:10 | 显示全部楼层
rhett.lhy 发表于 2015-9-5 15:37
什么叫“tools的职位“?

听说是以前的SEDT  就是Test
回复 支持 反对

使用道具 举报

 楼主| mhbkb 发表于 2015-9-6 13:53:31 | 显示全部楼层
jiebour 发表于 2015-9-5 16:29
没拍照意味着什么?
. 1point 3acres 璁哄潧
意味着前20min, 第一题白做。。。
回复 支持 反对

使用道具 举报

SDU_Phonism 发表于 2015-9-6 22:56:37 | 显示全部楼层
mhbkb 发表于 2015-9-6 07:12-google 1point3acres
dp = dp 加或减 A    这里的dp是HashSet, 每次迭代一遍dp的HashSet.   如果数组是1,2,3,4,...n, 那么复杂 ...
.1point3acres缃
其实复杂度就是O(解集的个数*n)吧。
回复 支持 反对

使用道具 举报

 楼主| mhbkb 发表于 2015-9-7 01:43:37 | 显示全部楼层
SDU_Phonism 发表于 2015-9-6 06:56
其实复杂度就是O(解集的个数*n)吧。

对, 面试官要个范围
回复 支持 反对

使用道具 举报

randyzhao 发表于 2015-9-8 03:02:34 | 显示全部楼层
感觉不是很明白3.1的输入是什么?从左到右扫一遍看哪个位置上的char不一样为啥不行?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-8 03:54:06 | 显示全部楼层
randyzhao 发表于 2015-9-8 03:02
感觉不是很明白3.1的输入是什么?从左到右扫一遍看哪个位置上的char不一样为啥不行?

跟你有绝对同样的感觉,但是要注意下corner case!
什么加法,乘法啊?给你长度为10000的字符串,敢乘嘛?直接overflow!
回复 支持 反对

使用道具 举报

AndyLiu0429 发表于 2015-9-8 04:16:27 | 显示全部楼层
mhbkb 发表于 2015-9-6 07:12
dp = dp 加或减 A    这里的dp是HashSet, 每次迭代一遍dp的HashSet.   如果数组是1,2,3,4,...n, 那么复杂 ...

这个n代表啥意思?
每次迭代一遍dp[i-1]的HashSet.   如果数组是1,2,3,4,...n, 那么复杂度就是O(n^3)
;这个n应该指数组长度?
如果数组类似1, 2, 4, 8, ..., 2^n,  那么复杂度就是O(2^n)
,这个n是log(数组长度)?
回复 支持 反对

使用道具 举报

zzwzhong698800 发表于 2015-9-8 21:52:00 | 显示全部楼层
难道就是这样两重循环?. Waral 鍗氬鏈夋洿澶氭枃绔,
求指教,怎么降复杂度呢?把结果用set存起来了,算不算降复杂度呢?
class Solution-google 1point3acres
{
public:
        vector<int> calculate(vector<int> arr)
        {
                if(arr.size() < 2).鐣欏璁哄潧-涓浜-涓夊垎鍦
                        return vector<int>();

                vector<int> res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                set<int> cur;
                cur.insert(arr[0]);
                for(int i = 1; i < arr.size(); i++)
                { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        set<int> next;
                        set<int>::iterator setItr = cur.begin();
                        for(; setItr != cur.end(); setItr++). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        {
                                int d = *setItr;
                                int plusRes = d + arr;. 鍥磋鎴戜滑@1point 3 acres
                                int subRes = d - arr;
                                next.insert(plusRes);
                                next.insert(subRes);
                        }
                        cur.clear();
                        cur = next;
                }

                set<int>::iterator setItr = cur.begin();
                for(; setItr != cur.end(); setItr++)
                        res.push_back(*setItr);
                return res;
        }
};
回复 支持 反对

使用道具 举报

faustine 发表于 2015-9-17 16:05:26 | 显示全部楼层
二面 什么是 “+ + - - 面经题”
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 12:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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