## Google Interview Questions

- 0of 0 votes
Phone interview question from January.

We have a maze with three types of spaces:

1. Walls

2. Offices

3. Hallway space

Given a maze, determine which non-wall space would minimize the sum of all distances between that space and every office. You can only move up, down, left, and right.

(Edit: ChrisK described the problem more clearly than I did: "find the field that minimizes the sum of the shortest path[s] from this field to each office space.")

Example:`WWWWWWWW WWW O WW WWW OW WWW WWWW WO WWWW WWW WWWW WO W WWWWWWWW`

O = office, W = wall, spaces are hallway spaces

You can represent the maze however you want. That is, you can use any data structures you want, and you don't necessarily have to use O for office, W for Wall, and spaces for hallways.

(I'm not sure if you can actually start from an office space, but that should be a trivial issue because you can always just start a position adjacent to an office.)

- 3of 3 votes
1 year exp. Interviewed at Cambridge, MA

Round1

LC304. Follow-up: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.

Round2

Find out the area of a number of squares on a plane, an advanced version of LC223.

Had no clue on that problem at all so the interviewer kindly gave another one LC305.

Round3

Similar to LC393 but the interviewer made a slightly different rule for encoding.

Follow-up: decode with utf-16. It took quite a while for me to understand the rules.

Round4

Card game rule: the hand is drawn from a pack of cards (no jokers).

Play cards ONLY when they are

1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).

2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).

Find out whether the player is able to play the whole hand given.

e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.

[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.

- 1of 3 votes

- 0of 0 votes
Automation Testing Question:

How do you verify a search result list which changes consistently based on each search word and filters?

For example, how do you make sure that the list is sorted based on price or rating or etc without any identical list to compare with? Since providing an identical list as Test Input for each word is not the best approach.

- 0of 0 votes
How do you reverse the words in a linked list?

For ex, Convert " H-e-l-l-o- -W-o-r-l-d " (There is a space between the word), into " o-l-l-e-H- -d-l-r-o-W "

Write a Java code to use as less Space Complexity as possible. (So not too many spaces should be used)

Linked List Structure:`class Node { char val; Node next; }`

- 0of 0 votes
Balance a string with parentheses. "a(b)" -> "a(b)"; "(((((" -> ""; "(()())" -> "(()())"; ")ab(()" -> "ab()"; etc...

- 2of 2 votes
Google full-time phD candidate w/ work experience.

Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.

Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?

Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)

Q3.Longest holiday - Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.

Q4.

Design merchandising product data storage service

- 0of 0 votes
Question regarding largest possible sum of subarray of size K.

- 4of 4 votes
Google On-site in May

Create a class with a collection of integers.

Enable 3 APIs:

void append(int x),

int get(int idx),

void add_to_all(int x)，//add x to all numbers in collection

These methods should run in O(1) time.

Follow-up

In addition, implement

void multiply_to_all(int x)

The same required to run in O(1) time

- 0of 0 votes
Make 100 HTTP GET requests to http://en.wikipedia.org/wiki/Main_Page and print the following in Java

statistics for the response time to stdout:

• 10th, 50th, 90th, 95th, 99th Percentile

• Mean

• Standard Deviation

Your solution must be parallel. You must make at least N (say 10, but should be configurable)

requests at a time.

Explain design choices, known limitations and edge cases.

What challenges did you face? How would you improve the code if you had more time?

- 0of 0 votes
Find all the abbreviations of string:

eg

ABC

SOME Valid abbreviations are :

1BC

2C

3

A1C

AB1

A2

NOT VALID

11C(two numbers cannot occur continuously)

- 0of 0 votes
Given a method

public int getOccurence(int x,int y);

where y is always a single digit number.

So find the number of occurrences of number y in the range x

E.g.

if x=25,y=2

function should return 9(as 22 contains two occurrences of 2) - 2,12,20,21,22,23,24,25

- 0of 0 votes
Last Monday phone interview of G.

Given a vector/list of doubly linked list pointers (a pointer is the directed linkage of two nodes), count how many independent blocks of linked lists there are for the pointers given.

- 1of 1 vote
how to keep track of the sum in a sliding window for the data that are on disk

rather than memory

- 0of 0 votes
Insert a node in a complete binary tree efficiently.

it is not BST, it is just a regular binary tree

public TreeNode insert(TreeNode root, int val){

}

this my solution using bfs (O(n) time), is there any more efficient method?`import java.util.*; class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int val){ this.val = val; } } class Solution{ public TreeNode insertCompleteTree(TreeNode root, int val){ if(root == null){ return new TreeNode(val); } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ int size = q.size(); for(int i = 0; i < size; i++){ TreeNode cur = q.remove(); if(cur.left == null){ cur.left = new TreeNode(val); return root; }else{ q.add(cur.left); } if(cur.right == null){ cur.right = new TreeNode(val); return root; }else{ q.add(cur.right); } } } return null; } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null){ return res; } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ int size = q.size(); List<Integer> list = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode cur = q.remove(); list.add(cur.val); if(cur.left != null){ q.add(cur.left); } if(cur.right != null){ q.add(cur.right); } } res.add(list); } return res; } public static void main(String[] args){ Solution s = new Solution(); TreeNode root = null; int[] nums = {1, 2, 3, 4, 5, 6, 7}; for(int num : nums){ root = s.insertCompleteTree(root, num); System.out.println(s.levelOrder(root)); } } }`

- 0of 0 votes
A table has some number of balls at various positions on a line segment.

All are moving with same speed in one or the other direction.

Wherever a collision occurs they change direction.

A ball falls from the edges of the table.

Find the time when all balls fall of the table

given initial position of each ball and speeds

- 0of 0 votes
`Suppose you have a 2-D grid. Each point is either land or water. There is also a start point and a goal. There are also keys that open up doors. Each key corresponds to one door. Implement a function that returns the shortest path from the start to the goal using land tiles, keys and open doors. Data Representation The board will be passed as an array of chars. A board can have the following tiles. 0 = Water 1 = Land 2 = Start 3 = Goal uppercase = door lowercase = key Example Maps (keys at each step are not required) `No doors` char[][] board1 = {{'0', '2', '1', '1', '1'}, {'0', '1', '0', '0', '1'}, {'0', '1', '0', '0', '3'}, {'0', '1', '0', '0', '1'}, {'0', '1', '1', '1', '1'}}; path : [0,1]->[0,2]->[0,3]->[0,4]->[1,4]->[2,4] `One door` char[][] board2 = {{'0', '2', '1', '1', '1'}, {'0', '1', 'a', '0', 'A'}, {'0', '1', '0', '0', '3'}, {'0', '1', '0', '0', '1'}, {'0', '1', '1', '1', '1'}}; path : [0,1]->[0,2]->[1,2]->[0,2]->[0,3]->[0,4]->[1,4]->[2,4]`

public List<int[]> solve(char[][] board) {

- 0of 0 votes
Given a large file with sentences and query string, design a system (Class, data structs, functions, etc) and algorithm to return the smallest window (start and end offsets) in the input file where the query words (in any order) are seen in the text file. What is the time complexity?

- 0of 0 votes
Given a binary tree, return all the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:

Given a binary tree`/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ 1 / \ 2 3 / \ 4 5 Return [4,2,1,3] and [5,2,1,3]. Public List<List<Integer>> getLongestPath(TreeNode root) { }`

- 1of 1 vote
Generate a random 4-digit even number : the adjacent 2 digits must be different.

public int getNumber(){

}

- 1of 1 vote
write a function that randomly return a random Fibonacci number in range [min, max)

public int getRandom (int min, int max){}

- 0of 0 votes
write a function that randomly return a random prime number in range [min, max)

public int getRandom (int min, int max){}

- 0of 0 votes
Given a large MxN matrix of 1s and 0s like this:

`1 1 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 ...`

Calculate the number of 1s in a given subset PxQ matrix. In effect, write a function:

`int ones(int startx, int starty, int len, int width);`

Looking for something better than O(n^2).

- 0of 0 votes
Find two strings are meta string or not

for eg:-

Converse

Conserve

are meta strings because if we swap s and v in the string both string will become equal. If swapping of more than one pair can be done then it is not a meta string

- 0of 0 votes
Find the median of a bst in O(n) time and O(1) space

- 0of 0 votes
Given a count and maxvalue, write a program to return count number of unique random integers between 0 and maxvalue.

- 0of 0 votes
tokenize string, "" and [] are token flags, such as

mytable "foo" [bar] "" [[[[]]].

"" Turned into ",]] turned into], [[not escaped

The results of the example given above:

mytable

foo

bar "

[[]

public List<String> tokenizestring(String s){

}

- 0of 0 votes
F (n) = 3n + 1 (if n is odd) or n / 2 (if n is even)

Collapse sequence refers to each number according to this formula

until the sequence becomes equal to 1,

Find the number (which is not greater than 10000), which will have the longest Collapse sequence.

public int getlongestCollapsesequence(int n){

}

- 0of 0 votes
Find the Lexicographic next word of the input word from a list of words

Example

Words list

[Cat, dog, cow, donkey, zebra, monkey],

input

duck

output

monkey

Input

dog

output

donkey

Can you use trie to solve it?

public String findNextWord(List<String> words, String input){

}

- 0of 0 votes
You are given an island which contains cliffs of various heights. A water droplet is placed on one of the cliffs. The water droplet always flows from higher height to lower height. Write a program that can calculate the lowest height cliff in the island that the water droplet can reach in the most efficient way you can think of. Example: if the droplet is placed on a cliff of height 5 and it is surrounded by cliffs of heights 6,3,2,2; it can flow to either of the cliffs of height 3,2,2 and then further flow from there.