G家电面面经【已过HC，求祝福啊】# JobHunting - 待字闺中
l*h
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，所以就不多说了吧，遇到两个白人，一个国人大姐，一位阿三，
感谢国人大姐的放水。
希望不要在最后一步出啥问题吧。
电面题目：
一位国人大哥，先在这里谢过啦，时间刚好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，所以就不多说了吧，遇到两个白人，一个国人大姐，一位阿三，
感谢国人大姐的放水。
