l***h
发帖数: 96 | 1 上上周五去MTV onsite的，这周一HR说HC已经过了，等这周EC省材料，下周给我消息。
希望不要在最后一步出啥问题吧。
电面题目：
一位国人大哥，先在这里谢过啦，时间刚好45分钟，吐槽下Google docs上写程序好蛋
疼，什么时候可以搞个可以支持Vim的编辑器吧。。。。
Assume some binary (each pixel is either black or white ) images, have same
width and height, and the length is power of 2. Present it by quadtree:
divide the image into quarters, each quarter can be all back, all white or
mixed, subdivide the mixed ones… recurse.
+-------+---+---+
| | F | F |
| T +---+---+
| | T | T |
+---+---+---+---+
| F | T | |
+---+---+ F |
| F | T | |
+---+---+-------+
a) how to present this image
struct TreeNode {
TreeNode* upperLeft;
TreeNode* downLeft;
TreeNode* upperRight;
TreeNode* downRight;
int size;
bool pixel;
TreeNode(bool p, int s): pixel(p), size(s), upperLeft(NULL), downLeft(
NULL), upperRight(NULL), downRight(NULL){}
};
TreeNode* copy( TreeNode* root) {
if( !root)
return NULL;
TreeNode* r = new TreeNode( root->pixel, root->size);
r->upperLeft = copy( root->upperLeft);
r->upperRight = copy( root->upperRight);
r->downLeft = copy( root->downLeft);
r->downRight = copy( root->downRight);
return r;
}
b) count all the black pixels of this image
int getBlackPixels( TreeNode* root) {
if(!root)
return 0;
if( !root->upperLeft) {
if( root->pixel)
return root->size * root->size;
}
int sum = 0;
sum += getBlackPixels( root->upperLeft);
sum += getBlackPixels( root->downLeft);
sum += getBlackPixels( root->upperRight);
sum += getBlackPixels( root->downRight);
return sum;
}
c) merge two image( actually it's to "and" two image with same size since
all pixels are boolean)
TreeNode* merge( const TreeNode* image1, const TreeNode* image2) {
if( !image1->upperLeft && !image2->upperLeft) {
return new TreeNode(image1->pixel && image2->pixel, image1->size);
}
if( !image1->upperLeft) {
return mergeHelper(image1, image2);
}
if( !image2->upperLeft) {
return mergeHelper(image2, image1);
}
TreeNode* root = new TreeNode(image1->pixel, image1->size);
root->upperLeft = merge( image1->upperLeft, image2->upperLeft);
root->upperRight = merge( image1->upperRight, image2->upperRight);
root->downLeft = merge( image1->downLeft, image2->downLeft);
root->downRight = merge( image1->downRight, image2->downRight);
return root;
}
TreeNode* mergeHelper( TreeNode* image1, TreeNode* image2) {
if( !image1->pixel) {
return new TreeNode(image1->pixel, image1->size);
}
return copy(image2);
}
Onsite因为签了NDA，所以就不多说了吧，遇到两个白人，一个国人大姐，一位阿三，
感谢国人大姐的放水。 | s********9
发帖数: 586 | | e******0
发帖数: 291 | | f********e
发帖数: 91 | | c********e
发帖数: 186 | | u*****o
发帖数: 1224 | | l*********u
发帖数: 19053 | 7 bless
same
【在 l***h 的大作中提到】
: 上上周五去MTV onsite的，这周一HR说HC已经过了，等这周EC省材料，下周给我消息。
: 希望不要在最后一步出啥问题吧。
: 电面题目：
: 一位国人大哥，先在这里谢过啦，时间刚好45分钟，吐槽下Google docs上写程序好蛋
: 疼，什么时候可以搞个可以支持Vim的编辑器吧。。。。
: Assume some binary (each pixel is either black or white ) images, have same
: width and height, and the length is power of 2. Present it by quadtree:
: divide the image into quarters, each quarter can be all back, all white or
: mixed, subdivide the mixed ones… recurse.
: +-------+---+---+
| j*********6
发帖数: 407 | 8 lz肯定没问题的 加油~
顺便lz能不能解释一下题目？ 智商让人捉急 有点没看懂
还有那个图是什么意思？ | w**7
发帖数: 22 | 9 b) count all the black pixels of this image
int getBlackPixels( TreeNode* root) {
if(!root)
return 0;
if( !root->upperLeft) {
if( root->pixel)
return root->size * root->size;
}
int sum = 0;
sum += getBlackPixels( root->upperLeft);
sum += getBlackPixels( root->downLeft);
sum += getBlackPixels( root->upperRight);
sum += getBlackPixels( root->downRight);
return sum;
}
The code above does not look right. A node will have its pixel size only
when it has no child node. So a node's subnode shall be checked before you
return its size. | i***0
发帖数: 8469 | | | | l***h
发帖数: 96 | 11 You can judge on all four nodes and actually initially I did this way. But
the interviewer said you either have leaf nodes or nodes always with 4
children. Thus judging on 1 is sufficient.
【在 w**7 的大作中提到】
: b) count all the black pixels of this image
: int getBlackPixels( TreeNode* root) {
: if(!root)
: return 0;
: if( !root->upperLeft) {
: if( root->pixel)
: return root->size * root->size;
: }
: int sum = 0;
: sum += getBlackPixels( root->upperLeft);
| l***h
发帖数: 96 | 12 就是一个正方形黑白图片（边长是2的次方）用一个4叉树来表示～
【在 j*********6 的大作中提到】
: lz肯定没问题的 加油~
: 顺便lz能不能解释一下题目？ 智商让人捉急 有点没看懂
: 还有那个图是什么意思？
| c********e
发帖数: 186 | | B****c
发帖数: 538 | | x******1
发帖数: 155 | | f**********2
发帖数: 2401 | | c********p
发帖数: 1969 | | x*****0
发帖数: 452 | | l******a
发帖数: 64 | | b****f
发帖数: 138 | | T*****n
发帖数: 82 | | H*********s
发帖数: 2724 | 22 Gx gx!
【在 l***h 的大作中提到】
: 就是一个正方形黑白图片（边长是2的次方）用一个4叉树来表示～
|
|
