Google Interview Question Interns
Country: United States
Interview Type: Phone Interview
center=width/2; //to determine where the central line is
for (int j=0;j<height;j++{
for(int i=0;i<center;i++)
swap(bytes[i][j],bytes[width-1-i][j]);
}
We are given array of characters. Let there be n characters, each row has 8 bits. 8 bits of each char are to be flipped around its centre.
Ex:
0011 | 0101
will be flipped (swap the nibbles) to
0101 | 0011
---------------------------------------
Here, "flip" word may confuse us in that whether we have to swap the nibbles of a char byte or reverse the bytes of each char.
My take is with swapping the nibbles.
Call below function for each row of matrix
int reverse(int row[])
{
int end = sizeof(row)/sizeof(int) - 1;
int start = 0;
int temp;
while(start < end)
{
temp = row[start];
row[start] = row[end];
row[end] = temp;
start++;
end--;
}
}
char* flip(char* bytes, int width, int height) {
for (int i=0; i<height; i++) {
for (int j=0; j<width/2; j++) {
tmp = bytes[width*i+j];
bytes[width*i+j] = bytes[width*i + width - 1 - j];
bytes[width*i + width - 1 - j] = tmp;
}
}
return bytes;
}
For each row in the matrix, swap the extreme values (similar to reversing a string):
void flip(int[][] bitmap)
{
int rows = bitmap.length;
int cols = bitmap[0].length;
for (int i = 0; i < rows; i++) {
int L = 0;
int R = cols - 1;
while (L < R) {
int tmp = bitmap[i][L];
bitmap[i][L] = bitmap[i][R];
bitmap[i][R] = tmp;
}
}
}
#include <stdio.h>
void
flip_center(char *bytes, int width, int height)
{
int i = 0;
int j;
int first, last;
char temp;
for(j = 0; j < height; j++)
{
first = j * width;
last = (j +1) * width - 1;
for(i = 0; i < width/2; i++, first++, last--) {
/* flip first and last */
temp = bytes[first];
bytes[first] = bytes[last];
bytes[last] = temp;
}
}
}
int main()
{
char bytes[] = "0101011011110011";
flip_center(bytes, 8, 2);
printf("result %s\n", bytes);
}
first flip width/2 th bit for the first line. And for the second bit you need to flip width th position from the position you flipped first.
For example, if the width is 8, you need to flip 4th, 12th, 20th bit in the char array.
void FlipNth( char *ary, int nPos)
{
int bits = 1;
ary[nPos/8] ^= bits << nPos%8;
}
void flip( char *a, int w, int h)
{
for ( int i = 0 ; i < h; i++)
{
FlipNth( a, w/2 + i*w);
}
}
simply reverse each byte
this is for reversing one byte b
int i=0;
while(i<4){
if((b>>i)^(b>>(7-i))){
b^=((1<<i)|(1<<(7-i)))}
}
Do this for each row (XOR Swap)
void flip(char *data, int width) {
int current = 0;
while(current < width/2) {
data[current] = data[current] ^ data[width - current - 1];
data[width-current - 1] = data[current] ^ data[width - current - 1];
data[current] = data[current] ^ data[width - current - 1];
current ++;
}
}
Solution is to reverse every number in row and than reverse row:
def reverseNumb(numb):
result = 0
for i in xrange(63, -1, -1):
result += (numb & 1) << i
numb >>= 1
return result
def reverse(arr, width, height):
for i in xrange(height):
for k in xrange(width / 2):
leftInd = i * height + k
rightInd = i * height + width - k - 1
arr[leftInd], arr[rightInd] = reverseNumb(arr[rightInd]), reverseNumb(arr[leftInd])
if width % 2 != 0:
arr[width / 2 + 1] = reverseNumb(arr[width / 2 + 1])
def reverse_bits( num: int ) -> int:
reversedNum = 0
for i in range(7,-1,-1):
if num % 2 == 1:
reversedNum += 1 << i
num >>= 1
return reversedNum
def swap(index1: int, index2: int, bitmap: list):
bitmap[index1], bitmap[index2] = bitmap[index2], bitmap[index1]
def reverseNums( bitmap: list, width: int, height: int ) -> list:
# Time complexity: O(n) where n = number of items in list
# Space complexity: O(1)
print("Forward: ", bitmap)
BITS_PER_NUM = 8
bitmapLength = len(bitmap)
nums_per_row = width // BITS_PER_NUM
row_num = 1
# for each 16-bit number
for i in range(len(bitmap)):
# if our index is in the first half of each row
if i%nums_per_row < nums_per_row//2:
# swap the current index and its complementary index in the same row
swap(i,(row_num*nums_per_row-1)-i%nums_per_row,bitmap)
# keep track of row number to calculate ending index of each row
if (i+1) % nums_per_row == 0:
row_num += 1
# reverse the bits of each num
for i, num in enumerate(bitmap):
bitmap[i] = reverse_bits(bitmap[i])
print("\nReversed: ", bitMap)
return bitmap
def reverse_bits( num: int ) -> int:
reversedNum = 0
for i in range(7,-1,-1):
if num % 2 == 1:
reversedNum += 1 << i
num >>= 1
return reversedNum
def swap(index1: int, index2: int, bitmap: list):
bitmap[index1], bitmap[index2] = bitmap[index2], bitmap[index1]
def reverseNums( bitmap: list, width: int, height: int ) -> list:
# Time complexity: O(n) where n = number of items in list
# Space complexity: O(1)
print("Forward: ", bitmap)
BITS_PER_NUM = 8
bitmapLength = len(bitmap)
nums_per_row = width // BITS_PER_NUM
row_num = 1
# for each 16-bit number
for i in range(len(bitmap)):
# if our index is in the first half of each row
if i%nums_per_row < nums_per_row//2:
# swap the current index and its complementary index in the same row
swap(i,(row_num*nums_per_row-1)-i%nums_per_row,bitmap)
# keep track of row number to calculate ending index of each row
if (i+1) % nums_per_row == 0:
row_num += 1
# reverse the bits of each num
for i, num in enumerate(bitmap):
bitmap[i] = reverse_bits(bitmap[i])
print("\nReversed: ", bitMap)
return bitmap
def reverse_bits( num: int ) -> int:
reversedNum = 0
for i in range(7,-1,-1):
if num % 2 == 1:
reversedNum += 1 << i
num >>= 1
return reversedNum
def swap(index1: int, index2: int, bitmap: list):
bitmap[index1], bitmap[index2] = bitmap[index2], bitmap[index1]
def reverseNums( bitmap: list, width: int, height: int ) -> list:
# Time complexity: O(n) where n = number of items in list
# Space complexity: O(1)
print("Forward: ", bitmap)
BITS_PER_NUM = 8
bitmapLength = len(bitmap)
nums_per_row = width // BITS_PER_NUM
row_num = 1
# for each 16-bit number
for i in range(len(bitmap)):
# if our index is in the first half of each row
if i%nums_per_row < nums_per_row//2:
# swap the current index and its complementary index in the same row
swap(i,(row_num*nums_per_row-1)-i%nums_per_row,bitmap)
# keep track of row number to calculate ending index of each row
if (i+1) % nums_per_row == 0:
row_num += 1
# reverse the bits of each num
for i, num in enumerate(bitmap):
bitmap[i] = reverse_bits(bitmap[i])
print("\nReversed: ", bitMap)
return bitmap
#include <stdio.h>
#define row 6
#define col 2
void mirror_image(int array[6][2],int row1,int col1)
{
int index = (row1/2)-1;
int i,j,temp;
//printf("%d%d\n",row,col);
for(i=0;i<col1;i++)
{
for(j=0;j<(row1/2);j++)
{
temp = array[i][index-j];
array[i][index-j] = array[i][index+j+1];
array[i][index+j+1] = temp;
}
}
for(i=0;i<col1;i++)
{
for(j=0;j<row1;j++)
{
printf("%d",array[i][j]);
}
printf("\n");
}
}
int main()
{
int array[row][col];
int index_row,index_col;
for(index_col=0;index_col<col;index_col++)
{
for(index_row=0;index_row<row;index_row++)
{
scanf("%d",&array[index_row][index_col]);
}
}
mirror_image(array,row,col);
return 0;
}
def reverse_bits( num: int ) -> int:
reversedNum = 0
for i in range(7,-1,-1):
if num % 2 == 1:
reversedNum += 1 << i
num >>= 1
return reversedNum
def swap(index1: int, index2: int, bitmap: list):
bitmap[index1], bitmap[index2] = bitmap[index2], bitmap[index1]
def reverseNums( bitmap: list, width: int, height: int ) -> list:
# Time complexity: O(n) where n = number of items in list
# Space complexity: O(1)
print("Forward: ", bitmap)
BITS_PER_NUM = 8
bitmapLength = len(bitmap)
nums_per_row = width // BITS_PER_NUM
row_num = 1
# for each 16-bit number
for i in range(len(bitmap)):
# if our index is in the first half of each row
if i%nums_per_row < nums_per_row//2:
# swap the current index and its complementary index in the same row
swap(i,(row_num*nums_per_row-1)-i%nums_per_row,bitmap)
# keep track of row number to calculate ending index of each row
if (i+1) % nums_per_row == 0:
row_num += 1
# reverse the bits of each num
for i, num in enumerate(bitmap):
bitmap[i] = reverse_bits(bitmap[i])
print("\nReversed: ", bitMap)
return bitmap
public class MirroreBits {
static final byte MASK_LEFT = 15;// for 00001111
static final byte MASK_RIGHT = (byte) 240;// for 11110000
public static void main(String[] args) {
int number = 169;// Binary 1010-1001
byte actual = (byte) number;
byte leftPortion = (byte) (number & MASK_LEFT);//0000-1001
byte rightPortion = (byte) (number & MASK_RIGHT);//1010-0000
leftPortion = (byte) (leftPortion << 4);//1001-0000
leftPortion = (byte) (leftPortion & MASK_RIGHT);//1001-0000
rightPortion = (byte) (rightPortion >> 4);//1111-1010
rightPortion = (byte) (rightPortion & MASK_LEFT);//0000-1010
byte reversed = (byte) (leftPortion | rightPortion);//1001-1010
System.out.println(Binarify(actual));
System.out.println(Binarify(reversed));
}
//This Function is only printing byte into binary .
public static String Binarify(byte ByteToCheck) {
StringBuffer binaryCode = new StringBuffer();
byte[] reference = new byte[] { (byte) 0x80, 0x40, 0x20, 0x10, 0x08,
0x04, 0x02, 0x01 };
for (byte z = 0; z < 8; z++) {
// if bit z of byte a is set, append a 1 to binaryCode. Otherwise,
// append a 0 to binaryCode
if ((reference[z] & ByteToCheck) != 0) {
binaryCode.append("1");
} else {
binaryCode.append("0");
}
}
return binaryCode.toString();
}
}
First approach is to convert the input in a String array. Each line is an element of the array. Reverse each element in the array. Convert it back and return it.
- Kamy January 25, 2013