## Google Interview Questions

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

- 2of 2 votes
Given a equation in the form of "3x+4y+2=-5y+2x+10", simplify the equation to be in form "y=Ax+B", and return A,B. Also allow parenthesis to be in the equation. Ex. "3y-4x+(3-(2x-3y))=10y", result is "y =0.75 - 1.5x"

- 4of 4 votes
5th Round

Open-ended question What happens when you type a url in the browser and hit enter?

Second question Given an array of integers, print all the numbers that meet the following requirement - when the number is greater than every number on its left and smaller than every number on the right.

- 0of 2 votes
interviewed by senior engineer

Question Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters

Follow-up If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?

- 0of 0 votes
write a function to generate a random 4 digit unique even number, the four digits cannot be the same, 1234 is valid, but 1134 is not valid

- 0of 0 votes
Given a list of files. Return all the unique lines from all files.

- 0of 0 votes
You've escaped Commander Lambda's exploding space station along with numerous escape pods full of bunnies. But - oh no! - one of the escape pods has flown into a nearby nebula, causing you to lose track of it. You start monitoring the nebula, but unfortunately, just a moment too late to find where the pod went. However, you do find that the gas of the steadily expanding nebula follows a simple pattern, meaning that you should be able to determine the previous state of the gas and narrow down where you might find the pod.

From the scans of the nebula, you have found that it is very flat and distributed in distinct patches, so you can model it as a 2D grid. You find that the current existence of gas in a cell of the grid is determined exactly by its 4 nearby cells, specifically, (1) that cell, (2) the cell below it, (3) the cell to the right of it, and (4) the cell below and to the right of it. If, in the current state, exactly 1 of those 4 cells in the 2x2 block has gas, then it will also have gas in the next state. Otherwise, the cell will be empty in the next state.

For example, let's say the previous state of the grid (p) was:

.O..

..O.

...O

O...

To see how this grid will change to become the current grid (c) over the next time step, consider the 2x2 blocks of cells around each cell. Of the 2x2 block of [p[0][0], p[0][1], p[1][0], p[1][1]], only p[0][1] has gas in it, which means this 2x2 block would become cell c[0][0] with gas in the next time step:

.O -> O

..

Likewise, in the next 2x2 block to the right consisting of [p[0][1], p[0][2], p[1][1], p[1][2]], two of the containing cells have gas, so in the next state of the grid, c[0][1] will NOT have gas:

O. -> .

.O

Following this pattern to its conclusion, from the previous state p, the current state of the grid c will be:

O.O

.O.

O.O

Note that the resulting output will have 1 fewer row and column, since the bottom and rightmost cells do not have a cell below and to the right of them, respectively.

Write a function answer(g) where g is an array of array of bools saying whether there is gas in each cell (the current scan of the nebula), and return an int with the number of possible previous states that could have resulted in that grid after 1 time step. For instance, if the function were given the current state c above, it would deduce that the possible previous states were p (given above) as well as its horizontal and vertical reflections, and would return 4. The width of the grid will be between 3 and 50 inclusive, and the height of the grid will be between 3 and 9 inclusive. The answer will always be less than one billion (10^9).

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

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

- 0of 0 votes
For a string chemical formula like “C6H2(NO2)3CH3”, and output a map with key as element and value as its count.

element can have two chars, for example Fe2(SO4)3

public HashMap<Character, Integer> getCount(String chemicals){

}

- -3of 3 votes
Find the coordinates of the rectangle which is parallel to axis and has minimum area.

- 0of 0 votes
Suppose you have a stream of (timestamp, tag) events. You need to filter this stream (online), leaving only events with tags that haven't been already encountered in the last X seconds.

- 0of 0 votes
People enter and leave a room over the course of a day. Each person has a badge with a unique integer id, which is logged by the security system on enter/exit. Each log entry is an enter record (“E <id>”) or and leave record (“L <id>”) for the given badge id.

The room is empty at the beginning and ending of the day, and there are no other ways into or out of the room.

E: Enters the room

L: Leaves the room

Well formed log:

E 111

E 222

L 111

E 111

L 222

L 111

Question: You have a log and write a function to check is it the well formed log or not.

- -1of 1 vote
deleted