Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
I'm assuming by reverse you mean the following:
ex array (i'm using numbers here for the sake of the example):
arr = [1,2,3
4,5,6
7,8,9
Then the reversed array would like:
arr = [7,8,9
4,5,6
1,2,3
Am I correct in this assumption? If that's the case then you can just map the row and column index and swap the rows:
for(int i=0;i<array.length;i++){
int row = (i/columns); //use the fact that integer/integer is rounded down
int column = (i%columns);
flipped[i] = array[array.length-((columns*(row+1))-column)];
}
Reversing a matrix means reversing the rows? Like moving the rows at the bottom to the top? I thought it is like if A is a 2D array represented as [2,3,4,5,6,7] when num_rows=3 then reverse(A) is [3,2,5,4,7,6]. But how do we improve the solution for a large amount of data? It's going to take linear time anyway.
I am sure, this guy would have been rejected by Google. How can it hire someone who is unable to explain what 'reversing' a matrix means?
You know, I wonder whether GZ_Penny's questions really came from Google. They're certainly not his first-hand experience - there look to be ~50 questions and he doesn't understand them himself - and they're easier than, or seem to be easier than, the other Google questions I see. He might have just found a bunch of questions and dumped them all at once under 'Google'.
I would do a NxN matric multiplication, by taking the given matrix and multiplying it with a diagonal matrix which has NxN elements with diagonal 1. the char array placement has to taken care of here to get the multiplication right. i.e if you take char m[16] the it is a 4x4 matric if char m[4] it is a 2x2 matrix, so our diagonal matrix md[N] should have N as 16 or 4 depending on the other matrix, Then multiplay and add the appropriate column and row values. the end result will be a reversal of the matrix.
I think if A is a 2D array represented as [2,3,4,5,6,7] when num_rows=3 then reverse(A) is [3,2,5,4,7,6].
//initialize the char array into a 2D matrix of int type
public int[][] matrix= {{1,0,1,1},{0,1,1,1},{1,1,1,1}};
public char[] transpose()
{
StringBuilder sb = new StringBuilder();
for (int i=0; i<this.col; ++i)
{
for (int j=0; j<this.row; ++j)
{
sb.append(matrix[i][j]);
}
}
return sb.toString().toCharArray;
}
import org.junit.Test;
/**
* There's a matrix. Each element in the matirx is a bit (0 or 1). Write a
* method to reverse this matrix. The matrix is stored in a one dimensional char
* array. The length of each row is given.
*
* How do you improve your solution when handling large amount of data?
*
*
* Solution: As I understood, the matrix was flatten out to character array.
* Since the length of each row is given we can calculate how much char array
* has fully been filled, we can use negation to reverse bits directly.
*
* It may be possible that the last bucket(index) in char array may not be
* filled fully so it is necessary to be taken care of separately.
*
*/
public class ReverseMatrix {
@Test
public void testReverseMatrix() {
char[] arr = { '\u1010', '\uD130', '\u2100' };
int[] lengthOfRows = { 5, 7, 6, 9, 11, 3 };
// print the matrix in binary format
StringBuilder sb = new StringBuilder();
System.out.println("Before reversing char array: ");
for (int i = 0; i < arr.length; i++) {
int myInt = (int) arr[i];
String binary = Integer.toBinaryString(myInt);
binary = String.format("%16s", binary).replace(' ', '0');
System.out.printf("%c: 0x%x, %s%n", arr[i], myInt, binary);
sb.append(binary);
}
System.out.println(sb.toString());
// reverse the matrix
reverseMatrix(arr, lengthOfRows);
sb.setLength(0);
// print the matrix in binary format
System.out.println("\nAfter reversing char array: ");
for (int i = 0; i < arr.length; i++) {
int myInt = (int) arr[i];
String binary = Integer.toBinaryString(myInt);
binary = String.format("%16s", binary).replace(' ', '0');
System.out.printf("%c: 0x%x, %s%n", arr[i], myInt, binary);
sb.append(binary);
}
System.out.println(sb.toString());
}
/**
* Time complexity: O(n)
*
* @param arr
* @param lengthOfRow
*/
public void reverseMatrix(char[] arr, int[] lengthOfRow) {
final int NUMBER_BIT = Character.BYTES * 8;
int totalLength = 0;
int i;
// get the sum of all lengths
for (i = 0; i < lengthOfRow.length; i++) {
totalLength += lengthOfRow[i];
}
// negate (reverse bits) except last index
int len = Math.min(totalLength / NUMBER_BIT, arr.length - 1);
for (i = 0; i < len; i++) {
arr[i] = (char) ~arr[i];
}
if (i < arr.length) {
int shift = NUMBER_BIT - (totalLength % NUMBER_BIT);
arr[i] = (char) ((~(arr[arr.length - 1] >>> shift)) << shift);
}
}
}
Output:
Before reversing char array:
?: 0x1010, 0001000000010000
?: 0xd130, 1101000100110000
?: 0x2100, 0010000100000000
000100000001000011010001001100000010000100000000
After reversing char array:
?: 0xefef, 1110111111101111
?: 0x2ecf, 0010111011001111
?: 0xde80, 1101111010000000
111011111110111100101110110011111101111010000000
Can you please put some more light on what do you mean by reversing a matrix here ? Is it row-wise reversal or column-wise ? I apologize if this is intuitive and I am unable to figure it out.
- Amit Kumar Yadav January 17, 2014