@pisskidney It is always encouraged to clarify and ask concepts and doubts you have. I did not know what a Toeplitz was until the interviewer explained it to me. It can be reasonable to expect that there will be very vague questions in which the candidate is expected to clarify every detail before solving.
varun44
@varun44
Posts made by varun44

RE: Google onsite interview questions

RE: Google onsite interview questions
@nidhirastogi @heidixia I am not a new grad, I have a good number of years of experience and a background in distributed systems, so I was very much expecting those kinds of questions. I was surprised as well when I was informed by the recruiter just before the day of the interview that google's "interviewing slate" whatever that may be, has changed and they weren't going to ask me any system design questions.
I have edited my post to highlight making sure of this with the recruiters so that this wasn't a one off instance.
Note: This interview was at the San Bruno Youtube office.

RE: Google onsite interview questions
Solution for 4:
Preprocess the matrix m[i][j] and have a second matrix wherein:sum[i][j] = sum[i][j1] + sum[i1][j]  sum[i1][j1] + m[i][j] whenever i1, j 1 are valid.
Then,
Query(row1, col1, row2, col2) =
Consider m[i][j]1 2 3 4 5 6 7 8 9
Then sum[i][j]
1 3 6 5 12 21 12 27 45
Now Query(1,1,2,2) = sum[2][2]  sum[0][2]  sum[2][0] + m[0][0] = 28
Query(1,1,2,1) = sum[2][1]  sum[2][0]  sum[0][1] + m[0][0]= 13
Query(2,1,2,1) = sum[2][1]  sum[1][1]  sum[2][0] + m[1][0] = 8Thus we can see a general algorithm for Query:
Assuming row2 >= row1 && col2 >= col1 Query(row1, col1, row2, col2) = sum[row2][col2] sum[row11][col1]  sum[row1][col1  1] + m[row1  1][col1  1], whenever row1 1 and col1  1 are valid. Thus query is O(1) operation
Similarly, update(x, y, val) will have to update the sum matrix as follows:
Let diff = m[x][y]  val
Apply diff to sum[i][j] = sum[i][j] + diff where i ranges from x to M  1(M being number of rows in m), j ranges from y to N  1(N being number of columns in N)
Update is O(MxN) order. 
Google onsite interview questions
I recently went through a Google interview and wanted to contribute the questions I faced.
Note: Google has apparently changed its interview slate, there weren't any system design interviews and all are coding questions. Might have to verify this clearly with your recruiters.
Given a contiguous sequence of numbers in which each number repeats thrice, there is exactly one missing number. Find the missing number.
eg: 11122333 : Missing number 2
11122233344455666 Missing number 5 
Given a compressed string in which a number followed by [] indicate how many times those characters occur, decompress the string
Eg. : a3[b2[c1[d]]]e will be decompressed as abcdcdbcdcdbcdcde.
Assume the string is well formed and number will always be followed by a []. 
Given a tree representation of a html parsed output, wherein every block is a node in the tree, find if two html docs contain the same text.
struct Node { string value; bool isMetadata; vector<Node*> children; };
For eg, consider the two documents
<html><head>sample</head><body>Hello world
</body></html> will be represented as Node1: value sample, children: <body> isMetadata: true Node2: value: <body> children:isMetadata: true Node3: value:
: children: Hello world isMetadata: true Node4: value Hello world isMetadata: false
and a second document
<html><body>Hello world</body></html>and both documents are equivalent since they contain the same data.
Note: the case of both documents fitting in memory is trivial, since it is just walking this tree list, consolidating data and comparing. As a follow up, solve the case where the whole documents may not be able to fit in memory.
 Given a 2D matrix M X N, support two operations:
Query(row1, col1, row2, col2) such that I get the sum of all numbers in the rectangle ((row1, col1), (row1, col2), (row2, col1), (row2, col2)) and
Update(row, col) to a new number
And query is a very frequent operation and update is a rare operation, so query should be really fast, but update can be slower.
Follow up: How would you solve this in a distributed fashion
 Verify if a given matrix is a Toeplitz matrix:
Follow up, assume that the whole matrix cannot be fit in memory and should be read from a file, assume that a few rows and all columns can be read in, how to verify?
