Google Interview Question
Software EngineersTeam: GFS
Country: India
Interview Type: Phone Interview
#include <vector>
using namespace std;
class ResizableBitmap
{
int iWidth, iHeight;
vector<unsigned char> vPixels;
vector<bool> vMask;
void ResizeVectors()
{
vPixels.resize(3 * iWidth * iHeight);
vMask.resize(3 * iWidth * iHeight);
}
public:
ResizableBitmap()
{
iWidth = 640;
iHeight = 480;
ResizeVectors();
}
ResizableBitmap(int& iW, int& iH)
{
iWidth = iW;
iHeight = iH;
ResizeVectors();
}
~ResizableBitmap()
{
vPixels.clear();
vMask.clear();
}
void CompareWithPreviousBitmap(const ResizableBitmap& PreviousBitmap);
void SomeOperation();
};
void ResizableBitmap::CompareWithPreviousBitmap(const ResizableBitmap& PreviousBitmap)
{
unsigned int i;
// There can be 2 cases:
// 1). Size is changed - the places that were added or substracted - are different
// 2). Size is the same - each pixel is compared with the previous one by "XOR"
if (PreviousBitmap.iWidth < iWidth)
{
// mark the new bitmap fragment as changed
}
if (PreviousBitmap.iHeight < iHeight)
{
// mark the new bitmap fragment as changed
}
if ((PreviousBitmap.iWidth == iWidth) && (PreviousBitmap.iHeight == iHeight))
{
for (i = 0; i < vPixels.size(); i++)
{
vMask[i] = (bool)(vPixels[i] ^ PreviousBitmap.vPixels[i]);
}
}
}
void ResizableBitmap::SomeOperation()
{
unsigned int i;
for (i = 0; i < vPixels.size(); i++)
{
if (vMask[i])
{
// do something only if the pixel is different than the previous one
}
}
}
If I understand correctly, Bitmap class is supposed to provide a diff(Btimap other) method that should output the diff?
- blckembr November 25, 2015Also, is the goal to minimize number of changed/removed/added bits in the diff?
For example, given two bitmaps {0,1,0,1,0,1} and {1,0,1,0,1,0}, should the diff be <Added: {0}, Removed: {5}> or <Changed {0-5}>?