一亩三分地论坛

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

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

求问两道google常见面经题

[复制链接] |试试Instant~ |关注本帖
ssross 发表于 2015-12-5 06:29:35 | 显示全部楼层 |阅读模式

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

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

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

x
楼主太弱,最近在准备google的onsite,看到两道经常出现的题目。
1. quadtree。大概就是说一个黑白image,用的是quadtree表示的。黑的就是0,白的就是1。问求这个quadtree表示的image里黑像素的比例。
然后follow up就是求combine两个quad tree后产生一个新的image的quadtree,rule是就是只有两个images都是黑merge后才是黑,其他都是白。
. visit 1point3acres.com for more.
在网上看了看quadtree还是没太搞明白怎么做啊?求问众神有没有谁能再细讲下或者有没有自己写的一些code呢?

2. 一个string array。找出一个pair 字符串str1和str2,他们的长度乘积最大,并且两个字符串完全没有一样的字符。

看到别人的想法是把每个字符串变成一个26 bit的数字分别对应 a-z,出现了这位就是1反之就是0。这样只需要 str1 & str2 == 1就可以知道两个string有没有相同的char了。. more info on 1point3acres.com
但是还是因为楼主太弱,不太懂怎么把字符串变成一个26 bit的数字啊?或者这题还有什么其他的做法?
-google 1point3acres
求大神给点example code!!感激涕零!!!.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

1

查看全部评分

本帖被以下淘专辑推荐:

crisc3 发表于 2015-12-14 03:37:40 | 显示全部楼层
我来回答一下第一题

QuadTree的解释参考wiki: Quad Tree
这里简单解释一下 对于边长为2^n,大小2^n * 2^n的矩阵 一次分割会把它分成上下左右四个小矩阵,每个小矩阵的长度是原来边长的1/2, 所以Quad Tree最大的depth是n。另外有一点值得说明的是 如果Quad tree的一个Node里面包含的都是0,或者清一色都是1,那么不必再往下细分了。

给个例子: 矩阵
[0 0 1 0
0 0 0 1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1 1 0 0
1 1 0 0]
那么第一次细分 产生level1的四个node,为children[0] =  [[0,0][0,0]] , children[1] = [[1,0][0,1]], children[2] = [[1,1][1,1]] children[3] =  [[0,0][0,0]],只有children[1]需要继续细分。所以这个 QuadTree的表示应该如下:
          Root. 1point 3acres 璁哄潧
   /        |          |    \
c0        c1         c2   c3
       /   |   |  \
    c10 c11 c12 c13. from: 1point3acres.com/bbs
每个 Node 都是 QuadNode, 可见 QuadNode里面,你需要保存这个Node对应的边长2^(n-depth), 和它里面包含的0和1的个数,以此来计算这个 Node 是否包含清一色的0或者1, 以及它的子树children。同时说明下,如果这个 Node 是 leaf,那么children[i] = nullptr
struct QuadNode{. 1point3acres.com/bbs
    int len; //sub matrix size
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴    int numOfOnes;. From 1point 3acres bbs
    QuadNode* children[4];
    bool allZeros(); //return numOfOnes == 0;
    bool allOnes(); // return numOfOnes == len*len;. From 1point 3acres bbs
    bool isLeaf(); //return children[0] == nullptr;
}. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
其实 不需要numOfOnes,因为isLeaf()就说明了这个node不可再分,如果!allZeros() && isLeaf() 就说明了allOnes, 这里加入numOfOnes只是为了struct, 因为有时候会让你count合并之后1的个数
好,现在我们有2个Root Quad Node root, 求merge之后的root.我们只需要
大概写下function如下
QuadNode* merge(QuadNode* node1, QuadNode* node2){
    if(!node1 || !node2) return nullptr;
    int curLen = node1->len / 2;
    QuadNode* root = new QuadNode(curLen,0); // set len = curLen, numOfOnes = 0;
    if(node1 -> allZeros() || node2->allZeros())  return root;
    if(node1 -> isLeaf() && node2-> isLeaf() ){ // node1 and node2 are all sub matrices containing 1 only. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
           root->numOfOnes = node1->numOfOnes;
           return root;
    }
    if(node1->isLeaf() ){ root = deppCopy(node2); return root;}  //deep copy a quad tree node, this is easy, just a recursive function
    if(node2->isLeaf() ) { root = deppCopy(node1); return root;)}
    for(int i = 0; i < 4; i++){. more info on 1point3acres.com
         root->children[i] = merge(node1->children[i], node2->children[i]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
         root->numOfOnes += root->children[i]->numOfOnes;.1point3acres缃
    }
    return root;
}
这样就可以了。另外这里加入deepCopy函数其实也不必,因为merge就是一个deepCopy两个Node,只是为了思路清晰 所以这样写。. 1point 3acres 璁哄潧
可以把deep copy和merge函数写进一个函数里面。. 1point3acres.com/bbs

大家参考一下 如果有错误欢迎指出

评分

2

查看全部评分

回复 支持 3 反对 0

使用道具 举报

reality 发表于 2015-12-5 06:48:54 | 显示全部楼层
同问第一题!第二题就是比如这个string是abc你就转成一个integrr:1110000000… 然后integers两两and
回复 支持 反对

使用道具 举报

 楼主| ssross 发表于 2015-12-5 06:52:42 | 显示全部楼层
reality 发表于 2015-12-5 06:48. visit 1point3acres.com for more.
同问第一题!第二题就是比如这个string是abc你就转成一个integrr:1110000000… 然后integers两两and
. 1point 3acres 璁哄潧
恩我知道要那样做。我就是不太明白怎么把它变成一个26位的int,然后每个bit每个bit的set值。
回复 支持 反对

使用道具 举报

reality 发表于 2015-12-5 07:23:32 | 显示全部楼层
ssross 发表于 2015-12-5 06:52
恩我知道要那样做。我就是不太明白怎么把它变成一个26位的int,然后每个bit每个bit的set值。

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷我是用最呆的方法。。。先建立个26位的array, 然后放把当前letter - ‘a’设为1.走完一遍以后,再把array转成一个integer。就比如说array是[1,1,0,0,0,。。。]最后把它转成110000。。就行了。。
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-12-5 07:44:17 | 显示全部楼层
1. 我也没具体写过,不过感觉跟leetcode same tree差不多,保持比较的两个nodes描述的是图里同一个区域就行。至于data structure,记得看到过一个比较nice的
enum NodeType{. from: 1point3acres.com/bbs
      WHITE, BLACK, MIXED. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}
public TreeNode{
     private NodeType;
     private TreeNode leftUp, leftDown, rightUp, rightDown;. 鍥磋鎴戜滑@1point 3 acres
}
不知道对不对,求指教!
. 1point 3acres 璁哄潧
2.
public int convert(String str){. from: 1point3acres.com/bbs
     int result=0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
     for(int i=0; i<str.length(); i++){
          int offset=str.charAt(i)-'a';
          result|=1<<offset;. Waral 鍗氬鏈夋洿澶氭枃绔,
     }
     return result;
}
并没有测试过。。。
回复 支持 反对

使用道具 举报

 楼主| ssross 发表于 2015-12-5 09:45:31 | 显示全部楼层
七夜雪 发表于 2015-12-5 07:44
1. 我也没具体写过,不过感觉跟leetcode same tree差不多,保持比较的两个nodes描述的是图里同一个区域就行 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
多谢大神指导!
亲测第二个正确。
回复 支持 反对

使用道具 举报

tianshaobo47 发表于 2015-12-12 14:01:11 | 显示全部楼层
帮顶一下,希望大牛回答一下第一题QuadTree解法
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-12-12 23:40:17 | 显示全部楼层
第一题没有看懂,能再讲解下什么quadtree啊,能稍微解释一下吗,要求啥子哦,能举个例子吗
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-12-28 00:49:57 | 显示全部楼层
crisc3 发表于 2015-12-14 03:37
我来回答一下第一题
. 鍥磋鎴戜滑@1point 3 acres
QuadTree的解释参考wiki: Quad Tree

想问下如果一个图不是2的偶次幂是不是就不能变成QuadTree了啊。。
回复 支持 反对

使用道具 举报

vivaroma 发表于 2015-12-28 01:44:47 | 显示全部楼层
其实就是把integer当成一个32位数组用。只用其中的26位每一位用来记录一个字母。. 鍥磋鎴戜滑@1point 3 acres

int result;

. visit 1point3acres.com for more.用一个for循环遍历str里每个字符: result |= 1 << ('str.charAt(i)' - 'a')  这样就对每一位赋值啦. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

一个str需要有对应这样一个int,所以要用一个数组 int result[]
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-31 04:15:02 | 显示全部楼层
crisc3 发表于 2015-12-14 03:37. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我来回答一下第一题

QuadTree的解释参考wiki: Quad Tree

deep copy为什么需要呢?如果一个是空,另一个不是空,应该就是直接返回空吧?
回复 支持 反对

使用道具 举报

dimi 发表于 2016-6-21 13:56:22 | 显示全部楼层
学习了。。。太牛了各位也
回复 支持 反对

使用道具 举报

sal12 发表于 2016-7-1 07:47:01 | 显示全部楼层
一个string array。找出一个pair 字符串str1和str2,他们的长度乘积最大,并且两个字符串完全没有一样的字符。

他们的长度乘积最大是什么意思?是指str1 + str2 的度是最吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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