一亩三分地论坛

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

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

Google Youtube电面面经

[复制链接] |试试Instant~ |关注本帖
samurai_sz 发表于 2015-1-13 17:59:48 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Pass

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

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

x
问做过的一个project,hardest bug。然后是coding:
1. reverse characters in a string. 然后follow up是让每隔一位头尾对调,就是第二位和倒数第二位对调,第四位倒数第四位对调,以此类推。比如说 parent 这样做完以后是pnreat 如果是 ape这样做完以后还是ape
2. 一个complete binary tree,叶子节点和根节点都是0或者1,如果两个孩子都是1,父亲节点才是1,否则父亲节点是0. 给定一个叶子节点,将其修改成指定值val,让你update整个树. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Class Node {
    Node left, right, parent;
    int val;
}
void update(Node leaf, int val){}
第二题我写的是iterative的。写完她让我简化了一下,也就是什么时候就不需要再往上查看是否需要修改了。然后recruitor让我判断时间复杂度。这里average 平均复杂度有个数学问题在里面。best case O(1), worst O(logN), average O(2) = O(1). 写一下状态转换:
当前节点    另一个叶子节点   是否change. 1point3acres.com/bbs
1->0                1                  Y
0->1                1                  Y
1->0                0                  N
0->1                0                  N
所以每次需要修改的概率是50%,又因为自下而上的过程是满足乘法原理,所以总的修改次数期望是:
E(Change times) = 1 + (1/2) + (1/2)^2 + ...  ~= 2 所以是O(2) = O(1). 鍥磋鎴戜滑@1point 3 acres


评分

2

查看全部评分

z3581640 发表于 2015-1-13 22:33:41 | 显示全部楼层
楼主真大神,思路清晰,onsite走起
回复 支持 反对

使用道具 举报

kiviljc 发表于 2015-1-13 23:53:42 | 显示全部楼层
lz, 第二题要update整棵树的话所有的节点都需要遍历吧,,贴上一段代码,lz看一下,,
void updateToCBTree(TN *head){. 1point 3acres 璁哄潧
int left, right;
if(head->left!=NULL){
left = isOneOrZear(head->left);.1point3acres缃
right=isOneOrZear(head->right)       
}else{
                return ;
}
if(left==1&&right==1){
        head->val =1
}else{
        head->val=0;
. 1point3acres.com/bbs}
return ;. more info on 1point3acres.com

}
/*0 return false; 1return true*/. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
int isOneOrZear(TN *head){
int left, right;
if(head->left!=NULL){
             left = isOneOrZear(head->left);
        right=isOneOrZear(head->right);
}else{.1point3acres缃
        return head->val;
}       
if(left==1&&right==1){
        head->val =1
return 1;
}else{.1point3acres缃
        head->val=0;
        return 0;. 1point 3acres 璁哄潧
}. 鍥磋鎴戜滑@1point 3 acres
. from: 1point3acres.com/bbs
}


回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-1-14 01:37:32 | 显示全部楼层
kiviljc 发表于 2015-1-13 23:53. more info on 1point3acres.com
lz, 第二题要update整棵树的话所有的节点都需要遍历吧,,贴上一段代码,lz看一下,,
void updateToCBTre ...

你仔细看下原题。是有指向父亲节点的。而且给你的参数就已经是一个将要被更改的叶子节点了。所以很简单。不过你写的代码可以作为这题复杂点的follow up。我大致看了下针对root和无parent 指针也是对的
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-1-14 01:38:23 | 显示全部楼层
z3581640 发表于 2015-1-13 22:33
楼主真大神,思路清晰,onsite走起

哈哈。事实上我没分析出来复杂度。最后的那个期望是面试官跟我说的,应该是O(1)
。。。献丑了
回复 支持 反对

使用道具 举报

kiviljc 发表于 2015-1-14 02:09:12 | 显示全部楼层
samurai_sz 发表于 2015-1-14 01:37
你仔细看下原题。是有指向父亲节点的。而且给你的参数就已经是一个将要被更改的叶子节点了。所以很简单。 ...

sorry, 题没看对,,,,
是不是,,只要parents的值没变化的时候就停止递归了?
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-1-14 03:01:19 | 显示全部楼层
kiviljc 发表于 2015-1-14 02:09
sorry, 题没看对,,,,
是不是,,只要parents的值没变化的时候就停止递归了?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
是的
回复 支持 反对

使用道具 举报

BlackMamba 发表于 2015-1-14 06:27:02 | 显示全部楼层
请问一下第一题有没有限定是 reverse in-place?

补充内容 (2015-1-14 06:47):
第二题状态转换的第三个case: 当两个子叶节点都是0的时候,父亲节点也是1么?
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-1-14 17:16:33 | 显示全部楼层
BlackMamba 发表于 2015-1-14 06:27
请问一下第一题有没有限定是 reverse in-place?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-1-14 06:47):

他让我用c写。返回类型是void。
两个子节点是0的时候,父亲节点也是0.
回复 支持 反对

使用道具 举报

sosohu 发表于 2015-1-14 20:20:15 | 显示全部楼层
如果以前整个树的值都是1,然后修改叶子节点的值为0,难道不是会自下而上一直修改父节点到根节点么? 这样的话时间复杂度应该是O(lgn)?
回复 支持 反对

使用道具 举报

sosohu 发表于 2015-1-14 20:22:21 | 显示全部楼层
sosohu 发表于 2015-1-14 20:20. from: 1point3acres.com/bbs
如果以前整个树的值都是1,然后修改叶子节点的值为0,难道不是会自下而上一直修改父节点到根节点么? 这样的话 ...

噢, 看错了,是求平均复杂度
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 15:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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