## Google Interview Question for Software Engineers

Country: UK
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

``````import 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_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)
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))``````

Comment hidden because of low score. Click to expand.
0

can you also explain what you are doing?

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is career cup book question

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.