一亩三分地论坛

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

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

G家电面,刷人品求onsite

[复制链接] |试试Instant~ |关注本帖
小小平民 发表于 2015-9-29 14:41:07 | 显示全部楼层 |阅读模式

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

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

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

x
两道题:
1. 给一个2D matrix,bool 型,初始状态是都是false,要求写一个flip函数,实现把其中一个element由false变成true。 要求是所有false element被翻转的概率相等。
-google 1point3acres
2. 给两个二叉树,A 和 B 。 要求判断A 是不是B 的子树。 子树的意思是: A 是 B的一部分: 例如:
    A
    1.鏈枃鍘熷垱鑷1point3acres璁哄潧
   2 3
   B. Waral 鍗氬鏈夋洿澶氭枃绔,
   0
. from: 1point3acres.com/bbs   1 4
2 3.1point3acres缃

A 就是B的子树。. from: 1point3acres.com/bbs

都做出来了,希望给onsite吧。. more info on 1point3acres.com
求点玉米啊~~

评分

2

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2015-10-1 22:09:04 | 显示全部楼层
我说一个flip()是O(M+N)时间的实现,空间复杂度是O(M)。其中M,N分别是矩阵的行列数。

一开始先创建一个长为M的cum数组。cum[i]代表“到第i行(含第i行)为止,矩阵中有多少个false”。比如大矩阵是:
0 1 0 0
1 0 0 1
0 0 1 0
那么cum数组就是
[3 5 9]
-google 1point3acres
我们用cum数组来决定下一个随机数出现在哪一行。比如对[3 5 9],我们先产生一个1~9之间的随机数,比如4,然后在cum中找“第一个大于等于4”的数字,是第二个数5。那么我们就在第二行产生随机数。然后,因为5和其前面的数3的差为2,说明这一行有2个false,那么我们再产生一个[1 2]间的随机数,比如1。 然后遍历第5行,直到找到第1个0为止。这一步花费O(N)时间

然后我们要更新cum数组,具体做法是把第二个数字和之后的数字都减1,最后cum变成[3 4 8]。这一步花费O(M)时间。

所以最后总时间是O(M+N),空间是cum数组消耗的O(M)。

. From 1point 3acres bbs

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

GatorAM 发表于 2015-11-23 14:56:26 | 显示全部楼层
第二题 用 identical tree + recursive searching

    private static boolean subTree(TreeNode root, TreeNode B){
        //Check whether B is a subtree of A
        if(root == null && B == null){
            return true;
        }else if(root == null || B == null){
            return false;
        }
        
        if(root.val == B.val && sameTree(root, B) == true){-google 1point3acres
            return true;
        }
        
        return subTree(root.left, B) || subTree(root.right, B);
        
    }.鏈枃鍘熷垱鑷1point3acres璁哄潧
   
   
    private static boolean sameTree(TreeNode A, TreeNode B){
        if(A == null && B == null). 1point 3acres 璁哄潧
            return true;
        
        if(A.val == B.val){
            return sameTree(A.left, B.left) && sameTree(A.right, B.right);
        }else{
            return false;
        }
        
    }
回复 支持 1 反对 0

使用道具 举报

 楼主| 小小平民 发表于 2015-9-30 07:22:25 | 显示全部楼层
hulahu 发表于 2015-9-30 05:19
求楼主贴第一题的code

我的代码,希望对你有帮助:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
MxN boolean matrix - initted to all false entries
flip() - flip one entry form false to true. [Each element should have equal probability of being flipped.]


void flip(vector<vector<bool>> & matrix) {
        int row = matrix.size();
        if (row == 0) return;
        int col = matrix.size();.1point3acres缃
        if (col == 0) return;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        vector<pair<int,int>> co;  // stores all the false elements’ coordinates
        for (int i=0;i<row;i++) {. 1point 3acres 璁哄潧
                for (int j=0;j<col;j++) {.1point3acres缃
                        if (matrix[j] == false) co.push_back(make_pair<i,j>);
}
}
        myFlip(matrix,co);
}.鏈枃鍘熷垱鑷1point3acres璁哄潧

void myFlip(vector<vector<bool>> & matrix, vector<pair<int,int>> & co) {
        int total = co.size();
        int ran = rand()%total;  // generate a number between 0 and total-1. 鍥磋鎴戜滑@1point 3 acres
        inr r = co[ran].first;
        int c = co[ran].second;.1point3acres缃
        matrix[r][c] = true;
        co.erase(co.begin() + ran);  // erase (r ,c) . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        return;. more info on 1point3acres.com
}

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| 小小平民 发表于 2015-9-30 03:02:17 | 显示全部楼层
hyliu0000 发表于 2015-9-29 23:27 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主,都是怎么做的这两题的?
. 1point 3acres 璁哄潧
说下我的思路啊,绝对不是最优:
Q1. 搞一个 unordered_set<pair<int,int>> coordinates 来存所有false element的坐标。然后产生一个[0,coordinates.size()-1]的随机数x,coordinates[x]就是我们要翻转的element啦。 存coordinates 要O(n) time and O(n) space. 随机数和翻转都是O(1),所以总的复杂度是O(n).

Q2. 先深度优先搜索 Ta, 找到和Tb root->val 相等的Treee A 中的节点。
    然后写一个判断两个数是否是identical的函数。step 是O(n)
    step 2 是 O(n) 最后还是O(n*k)  k是A 中和B root->val相等的节点数
    一个小trick是可能有重复元素,这样的话,step1就要存多个节点,不能找到一个节点就返回,所以最后用一个容器来存。
回复 支持 1 反对 0

使用道具 举报

wyx63953 发表于 2015-9-29 15:34:27 | 显示全部楼层
祝楼主一鼓作气,拿到Offer
回复 支持 0 反对 1

使用道具 举报

nothingtrouble 发表于 2015-10-1 02:25:11 | 显示全部楼层
Linzertorte 发表于 2015-10-1 01:55
这里的二维转一维非常简单(i,j)->i*m+j

第一题,我们考虑一维的情况.数组size  为5, 某一次的情况下 [0,1 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
说的是segment tree吗? 能不能展开说说
回复 支持 1 反对 0

使用道具 举报

LifeGoesOn 发表于 2015-9-29 15:15:25 | 显示全部楼层
For question 1, given matrix m * n, just need to get the coordinate with random(0, m) and random(0, n) ? Any tricks here?
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-9-29 15:20:51 | 显示全部楼层
LifeGoesOn 发表于 2015-9-29 15:15
For question 1, given matrix m * n, just need to get the coordinate with random(0, m) and random(0,  ...

Or you mean the method flip() will be called many times on one matrix. many elements in the matrix have been flipped already in previous calls?
回复 支持 反对

使用道具 举报

 楼主| 小小平民 发表于 2015-9-29 15:54:52 | 显示全部楼层
LifeGoesOn 发表于 2015-9-29 15:15
For question 1, given matrix m * n, just need to get the coordinate with random(0, m) and random(0,  ...

Yes, flip will be called repeatedly
回复 支持 反对

使用道具 举报

 楼主| 小小平民 发表于 2015-9-29 15:55:12 | 显示全部楼层
wyx63953 发表于 2015-9-29 15:34
祝楼主一鼓作气,拿到Offer

谢谢,最喜欢听别人对我说这个了
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-9-29 16:26:36 | 显示全部楼层
这两题我都不会。。。。。。。

说说复杂度吧
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-9-29 23:27:12 | 显示全部楼层
楼主,都是怎么做的这两题的?
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-9-29 23:41:32 | 显示全部楼层
1. 应该是random with blacklist,2维转1维,(i,j)->(i*n+j)
不知道有没有更好地办法,因为当blacklist也就是选过的值增多的时候,复杂度可以到O(mn),
.鐣欏璁哄潧-涓浜-涓夊垎鍦
2. 第二题很有意思,像是之前面经上面发的find identical subtree。这个可能是简化版,recursive应该可以做。
回复 支持 反对

使用道具 举报

wzhwawhxm 发表于 2015-9-30 01:00:54 | 显示全部楼层
question 2, inorder traverse the two trees and make them to two arrays. compare the two arrays.
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-9-30 01:05:17 | 显示全部楼层
wzhwawhxm 发表于 2015-9-30 01:00. 1point3acres.com/bbs
question 2, inorder traverse the two trees and make them to two arrays. compare the two arrays.

inorder怎么保证identical?比较aray也是比较麻烦的吧
回复 支持 反对

使用道具 举报

wzhwawhxm 发表于 2015-9-30 01:53:33 | 显示全部楼层
inorder可以identical啊,把null表示出来就行了, time complexity is O(kn)
回复 支持 反对

使用道具 举报

 楼主| 小小平民 发表于 2015-9-30 03:03:11 | 显示全部楼层
nothingtrouble 发表于 2015-9-29 23:41
1. 应该是random with blacklist,2维转1维,(i,j)->(i*n+j)
不知道有没有更好地办法,因为当blacklist也 ...

恩,第二题我是用recursive做的,考官没让分析复杂度也没让优化,很奇怪
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-9-30 04:14:41 | 显示全部楼层
wzhwawhxm 发表于 2015-9-30 01:53
inorder可以identical啊,把null表示出来就行了, time complexity is O(kn)

恩,这样是可以的,其实可以把inorder concat成string,然后比较hash value.
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-9-30 04:27:19 | 显示全部楼层
小小平民 发表于 2015-9-30 03:02
说下我的思路啊,绝对不是最优:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Q1. 搞一个 unordered_set coordinates 来存所有false element的坐标。 ...

第一次应该是空间复杂度是O(mn)吧,因为是2D matrix呀,还有好像楼主没有重复调用似的,如果有重复调用,那么已经被翻转的需要从set里面去除吧,那这样产生的随机数还对么。
. visit 1point3acres.com for more.
我觉得这道题更像是reservoir sampling.
回复 支持 反对

使用道具 举报

wzhwawhxm 发表于 2015-9-30 04:27:52 | 显示全部楼层
想了下,这题用recursion可以到O(n),更好点
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-9-30 04:50:38 | 显示全部楼层
wzhwawhxm 发表于 2015-9-30 04:27 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
想了下,这题用recursion可以到O(n),更好点

哪题呢?1或2?能稍微讲讲思路么?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-30 05:19:04 | 显示全部楼层
求楼主贴第一题的code
回复 支持 反对

使用道具 举报

哆啦嗦 发表于 2015-9-30 05:31:16 | 显示全部楼层
看g家面试题,完全觉得自己太弱了。。。
贴代码啊!楼主!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 13:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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