Google Interview Question Software Engineers
Country: UK
Interview Type: In-Person
Expanded Java version. Input is specified as
int array[] - cast to byte[]
width - in pixels
height - in pixels
You must satisfy condition -> array.length = w*h/8;
void givenMonochromeMapOfBitsDrawDiagonalLine() throws Exception {
//
int w=8; int h=8;
byte input[]=convertIntArrayToByteArray(new int[]{0,0,0,0,0,0,0,0});
boolean twodim[][]=convertByteArrayToBitMap(input, w, h);
BitMapTwoDim bitmap=new BitMapTwoDim(twodim,w,h);
log(printBitMap(bitmap));
drawDiagonalLine(bitmap);
log(printBitMap(bitmap));
}
void drawDiagonalLine(BitMapTwoDim bitmap) {
// y=h-(h/w)*x; x[1..w], y[1..h]; diagonal line equation
for (int x = 0; x<bitmap.w; x++) {
int y=(int)(bitmap.h-(bitmap.h*x/bitmap.w));
if( y<1 ) { y=1; }
if( y>bitmap.h ) { y=bitmap.h; }
bitmap.bitmap[ bitmap.h-y ][ x ]=true;
}
}
class BitMapTwoDim {
int h, w;
boolean bitmap[][];
public BitMapTwoDim(boolean bitmap[][], int w, int h) {
this.w=w; this.h=h;
this.bitmap=bitmap;
}
}
String printBitMap(BitMapTwoDim d) {
StringBuilder sb=new StringBuilder();
for (int row = 0; row < d.h; row++) {
for (int col = 0; col < d.w; col++) {
if( d.bitmap[row][col] ) { sb.append("1"); }else{ sb.append("-"); }
}
sb.append("\n");
}
return sb.toString();
}
/** convert bitmap into expanded two dimensional array */
boolean[][] convertByteArrayToBitMap(byte b[], int w, int h) {
if( (w*h)!=b.length*8 ){ throw new RuntimeException("Mistmatch w=" + w + ", h=" + h + ", b.length=" + b.length); }
boolean[][] result=new boolean[h][w];
int row=0; int col=0; int bitused=0;
for (int i = 0; i < b.length; i++) {
for (int bit = 0; bit < 8; bit++) {
row=(int)Math.floor(bitused/w);
col=bitused - row*w; bitused++;
result[row][col]=is_set(b[i], bit);
}
}
return result;
}
/** compress two dimensional array into bitmap array of bytes */
byte[] convertBitMapToByteArray(boolean b[][], int w, int h) {
byte[] result=new byte[h*w];
for (int row = 0; row < h; row++) {
for (int col = 0; col < w; col++) {
int value=0;
for (int bit = 0; bit < 8; bit++) {
if( b[row][col] ){ value = value | (1<<(7-bit)); }
}
result[row*w+col]=(byte)value;
}
}
return result;
}
byte[] convertIntArrayToByteArray(int in[]) throws Exception{
byte b[]=new byte[in.length];
for (int i = 0; i < in.length; i++) {
b[i]=get_ByteFromInt(in[i]);
}
return b;
}
public byte get_ByteFromInt(int i) throws Exception {
byte res=0;
if( i>127 && i<256 ) { res =(byte) (256 - i); res *=(-1); }
if( i>=0 && i<=127 ) { res=(byte)i; }
else if( i<0 ) { throw new Exception("Invalid argument, i:=" + i); }
return res;
}
boolean is_set(int x, int b) {
return ((x & (1 << b)))==(1<<b) ? true: false;
}
void givenMonochromeMapOfBitsDrawDiagonalLine() throws Exception {
//
int w=8; int h=8;
byte input[]=convertIntArrayToByteArray(new int[]{0,0,0,0,0,0,0,0});
boolean twodim[][]=convertByteArrayToBitMap(input, w, h);
BitMapTwoDim bitmap=new BitMapTwoDim(twodim,w,h);
log(printBitMap(bitmap));
drawDiagonalLine(bitmap);
log(printBitMap(bitmap));
}
void drawDiagonalLine(BitMapTwoDim bitmap) {
// y=h-(h/w)*x; x[1..w], y[1..h]; diagonal line equation
for (int x = 1; x<=bitmap.w; x++) {
int y=(int)(bitmap.h-(bitmap.h*x/bitmap.w));
if( y<1 ) { y=1; }
if( y>bitmap.h ) { y=bitmap.h; }
bitmap.bitmap[ bitmap.h-y ][ x-1 ]=true;
}
}
class BitMapTwoDim {
int h, w;
boolean bitmap[][];
public BitMapTwoDim(boolean bitmap[][], int w, int h) {
this.w=w; this.h=h;
this.bitmap=bitmap;
}
}
String printBitMap(BitMapTwoDim d) {
StringBuilder sb=new StringBuilder();
for (int row = 0; row < d.h; row++) {
for (int col = 0; col < d.w; col++) {
if( d.bitmap[row][col] ) { sb.append("1"); }else{ sb.append("-"); }
}
sb.append("\n");
}
return sb.toString();
}
/** convert bitmap into expanded two dimensional array */
boolean[][] convertByteArrayToBitMap(byte b[], int w, int h) {
if( (w*h)!=b.length*8 ){ throw new RuntimeException("Mistmatch w=" + w + ", h=" + h + ", b.length=" + b.length); }
boolean[][] result=new boolean[h][w];
int row=0; int col=0; int bitused=0;
for (int i = 0; i < b.length; i++) {
for (int bit = 0; bit < 8; bit++) {
row=(int)Math.floor(bitused/w);
col=bitused - row*w; bitused++;
result[row][col]=is_set(b[i], bit);
}
}
return result;
}
/** compress two dimensional array into bitmap array of bytes */
byte[] convertBitMapToByteArray(boolean b[][], int w, int h) {
byte[] result=new byte[h*w];
for (int row = 0; row < h; row++) {
for (int col = 0; col < w; col++) {
int value=0;
for (int bit = 0; bit < 8; bit++) {
if( b[row][col] ){ value = value | (1<<(7-bit)); }
}
result[row*w+col]=(byte)value;
}
}
return result;
}
byte[] convertIntArrayToByteArray(int in[]) throws Exception{
byte b[]=new byte[in.length];
for (int i = 0; i < in.length; i++) {
b[i]=get_ByteFromInt(in[i]);
}
return b;
}
public byte get_ByteFromInt(int i) throws Exception {
byte res=0;
if( i>127 && i<256 ) { res =(byte) (256 - i); res *=(-1); }
if( i>=0 && i<=127 ) { res=(byte)i; }
else if( i<0 ) {
throw new Exception("Invalid argument, i:=" + i);
}
return res;
}
Let's assume that the organization of pixels is: a line of pixels (from left to right) is a consecutive sequence of bytes (each byte holding 8 pixels - bit 0 is the leftmost pixel, bit 7 the rightmost) and then lines are a consecutive sequence from top to bottom. It is important to ask the interviewer if this is the right assumption.
One can iterate pixel-by-pixel but this would potentially access the same byte multiple times. This can be improved by dividing drawing of the line into three parts: drawing the head - first byte of the line where only the high part of the bits is affected, then the body - the part of the line where a full bytes are affected, and finally the tail - last byte of the line where only the low part of the bits is affected.
- tested.candidate March 21, 2015import math def blank(width, height): return [0] * int(math.ceil(width * height / 8.0)) def line(bitmap, width, height, x1, x2, y): a_full = width * y + x1 z_full = width * y + x2 a_head = a_full >> 3 a_bits = a_full & 0x7 a_body = a_head + (1 if 0 != a_bits else 0) z_tail = z_full >> 3 z_bits = (z_full & 0x7) + 1 z_body = z_tail - (1 if 8 != z_bits else 0) # Head if a_head != a_body: bitmap[a_head] |= (0xFF << a_bits) & 0xFF # Body for i in range(a_body, z_body + 1): bitmap[i] = 0xFF # Tail if z_tail != z_body: bitmap[z_tail] |= ~(0xFF << z_bits) & 0xFF def hexed(bitmap): return ''.join(['%02X' % byte for byte in bitmap]) width = 32 height = 3 bitmap = blank(width, height) line(bitmap, width, height, 7, 22, 1) print(hexed(bitmap))