Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)];
        }

- Anonymous January 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wow major formatting errors :P but you get the jist

- Anonymous January 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Guy January 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- FactTeller January 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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'.

- JeffD February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Haneef.hawk21 January 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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].

- phalwe January 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree, that is how I would interpret this

- langeolli January 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If so, it sounds very easy. But how do we improve the solution for a large amount of data? It's going to take linear time anyway.

- Guy January 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Does it mean transpose of a matrix, if so January 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it should be sb.append(matrix[j][i]) for transpose...

- Sachin January 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys, he said specifically it's a matrix storing BITS. So reversing should mean reversing the bits.

- Anonymous January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I feel like a lot of info is missing in this question. Why would the question clarify that the matrix stores bits, for instance? That seems like a detail which would have a purpose in a short interview question.

- nilkn January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Hope December 27, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More