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.

Round 1:

• https://leetcode.com/problems/single-number-ii

Round 2:

• https://leetcode.com/problems/decode-string

Round 3:

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

  Explanation

  	struct Node {
  		   string value;
  		   bool isMetadata;
  		   vector<Node*> children;
  	};

  For eg, consider the two documents

  sample

  Hello world

  will be represented as Node1: value sample, children: isMetadata: true Node2: value: children:

  isMetadata: true Node3: value:

  : children: Hello world isMetadata: true Node4: value Hello world isMetadata: false

  and a second document

  Hello world

  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.

Round 4:

• 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

Round 5:

• https://leetcode.com/problems/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?