## Google Interview Questions

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

- 1of 1 vote
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"

- 2of 2 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

- 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){

}

- -2of 2 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

- 0of 0 votes
* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

Given an array of Binary Tree Node, check if all of these nodes can form a binary tree?

Public boolean canForm(TreeNode[] nodes){

}

- 1of 1 vote
Phone Interview, New Grad - Software Developer

Imagine you are given 10,000 files each containing 1 Million integers. I would you sum all of them and give the final result?

---> Interviewer wanted to test scalability, distributed concepts.

He has written the basic code and wanted to improve upon that.

Here's the basic code.`public getSum(String[] file_names) { int sum = 0; for(String f: file_names) { sum = sum + sumOfFile(f); } return sum; }`

Questions:

What's wrong with above code? Ans: Integer overflow

How would you implement sumOfFile?

What if 'sumOfFile' takes lot of time to finish computing?

How do you fasten the program?

Overall scalability etc

- 2of 2 votes
Given a sorted array, find all the numbers that occur more than n/4 times.

- 0of 0 votes
Give a Runable interface, and then give a scheduler post method. This post is parallel, for example:

Method header:

public void post (Runable r) {};

Call 5 times:

Scheduler.post (r1);

Scheduler.post (r2);

Scheduler.post (r3);

Scheduler.post (r4);

Scheduler.post (r5);

The five runables are allocated to five threads and run at the same time. And then asked: how to achieve these five tasks one by one run,

- 1of 5 votes
In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.

Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),

check whether the student qualifies for the reward.

e.g.

@INPUT (String) "OLLAOOOLLO"

@RETURN (Boolean) False

The student does not qualify for reward because "LLA" means he was late for 3 times in a row.

@INPUT (String) "OLLOAOLLO"

@RETURN (Boolean) True

Follow-up:

If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.

- 0of 0 votes
In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.

Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time), check whether the student qualifies for the reward.

e.g.

@INPUT (String) "OLLAOOOLLO"

@RETURN (Boolean) False

The student does not qualify for reward because "LLA" means he was late for 3 times in a row.

@INPUT (String) "OLLOAOLLO"

@RETURN (Boolean) True

Follow-up:

If known the length of the attendance string is n, how many possible ways there is to attend school and make sure the student gets the reward.

- 4of 4 votes
Given an non-negative int array and target number, check if the target can be equal to the sum of non-negative multiples of the numbers in the array.

For example, I have three numbers 6,9,20. Ex: n = 47 then it can be determined that 47 = 9*3 + 20

n=23 then there are no combinations.

public boolean combinationSum(int[] nums, int target) {

}

- 0of 0 votes
Check if two given binary trees(expression trees with two characters 'a' and 'b' and obviously operators like +,-,*) are mathematically equivalent?

- 2of 2 votes
Find three non-overlap windows of size k in an int array, that together has a maximum sum

of the 3k entries.

example

int[] nums = [1,2,1,2,6,7,5,1]

k = 2

output

[1,2],[2,6],[7,5]

- 2of 2 votes
Given a list of words with lower and upper cases. Implement a function to find all Words that have the same unique character set .

For example:

May student students dog studentssess

god Cat act tab bat flow wolf lambs Amy Yam balms looped poodle john alice

output:

may amy

student students studentssess

dog god

cat act

tab bat

flow wolf

lambs balms

looped, poodle

- 2of 2 votes
Given an int array without repeated elements and a target, count the total number of subset that can be generated from the array such that min (subset) + max (subset) < target

public int countSubSet(int[] nums, int target){

}