## Google Interview Questions

- 0of 0 votes
Given two object arrays of "id,weight" (sorted by weight), merge them together and create a one single array. If the "id"s are same values should be merged. Final resulting array should be sorted by weight. Result should be O(nlogn) in time complexity.

- 0of 0 votes
Given a dictionary and a string, find all the substrings that are valid words in dictionary.

I was thinking of a Trie solution but I'm not sure a Trie will work easily to match sub words that begin in the middle of the string.

- 0of 0 votes
Given a string return the longest palindrome that can be constructed by removing or shuffling characters.

Example:

'aha' -> 'aha'

'ttaatta' -> ' ttaaatt'

'abc' -> 'a' or 'b' or 'c'

'gggaaa' -> 'gaaag' or 'aggga'

Note if there are multiple correct answers you only need to return 1 palindrome.

- 0of 0 votes
A matrix is "Toepliz" if each descending diagonal from left to right is constant. Given an M x N matrix write the method isToepliz to determine if a matrix is Toepliz.

Example:

Input:

67892

46789

14678

01467

Output:

True

- 0of 0 votes
Find the index when slow and fast pointer meet in terms of n (length of list before cycle) and p ( length of loop in linked list).

Let me meeting index is q then we should be able to find value of q when we pass n& p , there shouldn't be any extra variable.

- 0of 0 votes
I was asked in an interview: You are given a dump file of IPv4 addresses. You are to find 4 most common occurring subnets. Lets say an IP address if of type a.b.c.d you have to find most common occurring four subnets of the form,

a.*.*.*

a.b.*.*

a.b.c.*

a.b.c.d

Here * matches anything.

My first solution was build an in memory hashtable. Given an IP address a.b.c.d split it as ["a","b","c","d"] and add "a", "a.b", "a.b.c", "a.b.c.d" to the hash table and count it. [There are optimizations possible like considering the entire IP address as a 32 bit unsigned integer and count it with masks and shifts]

Then the question got extended: "assume you can never hold everything in memory, how would you solve it?" Now, the very first solution that I could say was to do an external sort and then count it.

The next solution I gave was to split the IP addresses into buckets. The algorithm was,`while there is an IP IP <- an IP address a <- first quadruple push IP to bucket[a]`

The bucket which has maximum elements would give me the a.*.*.* solution. Now take each bucket and do the same. Even though this might give the correct result, in worst case I might end up having 255^4 buckets.

This is indeed an open ended question with more than one correct answer. What would be the best way to solve this?

- 1of 1 vote
GIven a list of words, and the number of rows and columns, return the number of words that can be fit into the rows and columns by stringing together each consecutive word. If the next word doesn't fit in the same line, it should move to the next line. Find an efficient solution for this. For eg.

List of words: { "Do", "Run" }

Number of columns: 9

Number of rows: 2

First row: "Do Run Do" (7 letters + 2 spaces fit into 9 columns)

Second row: "Run Do" (Only 2 words fit into 9 columns)

- 0of 0 votes
Write a program for skyyscrapper?

http://www.conceptispuzzles.com/index.aspx?uri=puzzle/skyscrapers/techniques

- 0of 0 votes
List of string that represent class names in CamelCaseNotation.

Write a function that given a List and a pattern returns the matching elements.

['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo']

H -> [HelloMars, HelloWorld, HelloWorldMars, HiHo]

HW -> [HelloWorld, HelloWorldMars]

Ho -> []

HeWorM -> [HelloWorldMars]

- 0of 0 votes
You have rating (0-10) of the hotels per user in this format:

scores = [

{'hotel_id': 1001, 'user_id': 501, 'score': 7},

{'hotel_id': 1001, 'user_id': 502, 'score': 7},

{'hotel_id': 1001, 'user_id': 503, 'score': 7},

{'hotel_id': 2001, 'user_id': 504, 'score': 10},

{'hotel_id': 3001, 'user_id': 505, 'score': 5},

{'hotel_id': 2001, 'user_id': 506, 'score': 5}

]

Any given hotel might have more than one score.

Implement a function, get_hotels(scores, min_avg_score) that returns a list of hotel ids that have average score equal to or higher than min_avg_score.

get_hotels(scores, 5) -> [1001, 2001, 3001]

get_hotels(scores, 7) -> [1001, 2001]

*/

How to solve this in C++ and Python?

- 5of 5 votes
You are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order.

Find number of 0-s in the given matrix.

Example:`0 0 1 0 1 1 1 1 1 Answer: 3 0 0 0 0 Answer: 4`

Update: Expected complexity is O(log(N)). The best I've seen in comments is still O(N).

Update2: Alright, guys, sorry for a bit of trolling. Obviously this is not possible to do faster than O(N). Here is why: take a diagonal (N, 1), (N-1, 2), ... (1, N). Suppose input matrix has all 0's above this diagonal and all 1's under this diagonal. So only diagonal elements vary. Clearly, diagonal elements do not depend on each other. So we have to analyze each diagonal element which is O(N).

Nice job, @gen-y-s :)

- -7of 7 votes
Given set of characters and a dictionary find the minimum length word that contains all the word from the given word

- 1of 1 vote
Given an array of n integers. MaxPrefix is defined as count of elements those are greater than the element and in the right side of array wrt to the element. Write a program to give the max of MaxPrefix Ex. Input 10 -4 6 2 8 9 4 Output is 5

- 1of 1 vote
Write a class to take in a large arbitrary number, also provide a function to increment the number. The number will be passed on as an array of integers.

- 2of 2 votes
Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c).

Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above.

Note: all coordinates are real numbers

(a,b)

|----------------------------------------------|

|.......................................................|end

|.......................................................|

|start................................................|

|.......................................................|

|----------------------------------------------|(c,d)

Edit: You have to avoid sensors.

Also u can move in any direction any time.

- 0of 0 votes
Let "t" be a good number if "t" can be written as sum of 2 cubes in at least 2 distinct ways. Given n, write a method which prints all good numbers up to and including n.

- 0of 2 votes
A robot on a plane has 2 types of commands:

1. move forward by X units (X is integer 0 <= X <= 10000 )

2. rotate by X degrees (X is integer in range [-180, 180] )

A robot looks like`def robot(commands): while True: for command in commands: execute(command)`

Given a list of commands (of size <= 10000) tell if it's possible to build a wall around the robot such that he will never touch it.

Example:`[move(10), rotate(180), move(10)] -> answer is yes [move(10), rotate(45), move(10), rotate(-45), move(10), rotate(45)] - answer is no`

- 3of 3 votes
# take an array and print non over lapping in order pairs. example:

`# [1,2,3,4] => input # output below is in order combination # (1234) # (1)(234) # (1)(23)(4) # (1)(2)(34) # (12)(34) # (12)(3)(4) # (123)(4) # (1)(2)(3)(4)`

- 2of 2 votes
You are given a range [first, last], initially white. You need to paint it black.

For this purpose you have a set of triples

[(f, l, cost), ...] - where each triple means that you can paint range [f, l] for `cost` coins (limitations: cost is floating point >= 0, f, l, first, last are integers).

Find minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible

Example:`[first, last] = [0, 5] and set of triples is [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]`

Clearly the answer is to take [0, 4, 1] and [2, 5, 1] - the total cost will be 2.

Another example:`[first, last] = [0, 5] triples are [[1,4, 10], [2, 5, 6]]`

answer is -1, because it's impossible to color whole range.

- 1of 1 vote
Given an array of length N and an integer K, sort the array as much as possible such that no element travels more than k positions to its left - an element however can travel as much as it likes to its right.

- -3of 3 votes
Write program that takes integer, deletes one of two consecutive digits and return greatest of all results.

- 0of 0 votes
Given deck of cards let se 50 cards, now all are thrown on a table, after throwing some cards of them are now with face up and some are with face down, tell the probability of sum of all the face up cards is divisible by 7.

Assume cards from 1 to 10, Answer should be generic so that we can get results for any number of cards, don't compare cards with playing cards, cards can be numbered from 1 to n

- 0of 0 votes
Given k - which is the number of bits, print all the possible combinations of numbers formed by printing all numbers with one bit set, followed by two bits set, ... upto the point when all k-bits are set. They must be sorted according to the number of bits set, if two numbers have the same number of bits set then they should be placed as per their value.

For example if K=3

Output:

000, 001, 010, 100,101, 110, 011, 111

0 bits set, followed by 1 bits set followed by 2 bits set followed by 3 bits set.

- 0of 0 votes
Given a graph and a source node and destination node, find the number of shortest paths present between source and destination. Hint: Use BFS

- 0of 0 votes
Given an MxN matrix, determine whether a path can be drawn through every node in the matrix such that the end node is next to the start node, and each node is only touched once.

- 0of 0 votes
Given a binary tree, find the largest subtree having atleast two other duplicate subtrees .

- 0of 0 votes
Given the following decoder, write the encoder. (The encoder should be written to compress whenever possible):

p14a8xkpq -> p14akkkkkkkkpq

(8xk gets decoded to kkkkkkkk. The only other requirement is that encodings be unambiguous)

Note that the String can have any possible ascii character

- 0of 0 votes
given 2 strings A and B. generate all possible solutions when B is merged in A.

Ex: A = "hey"

B: "sam"

then solutions are :

heysam,hseaym,hesaym,sahemy etc.

notice that order should be the same for both of strings while merging.

- -2of 2 votes
Take an example of the traditional Iterator interface which has the following methods

Interface Iterator<E>{

public boolean hasNext() {}

public E next() {}

public E remove() {}

}

You are given a list of iterators. You have to design a InterleaveIterator class which implements this

interface and implement the methods:

hasNext() and next()

such that these 2 methods returns interleaved values for the list of iterators:

Implement:

class InterleaveIterator<E> implements Iterator<E>{

@override

public boolean hasNext() {}

@override

public E next() {}

}

Example:

ArrayList<Integer> i1 = [1,2,3,4,5].iterator()

List<Node> i2 = [n1,n2].iterator()

Collection<E> i3 = [e1,e2,e3].iterator()

next() method of InterleaveIterator, should return in this sequence [1,n1,e1,2,n2,e3,3,e3,4,5]

Make this InterleaveIterator class generic and make sure that the class can accept a list of iterators

and interleave them

- 0of 0 votes
Given a list of pies (and the number of slices in each pie) calculate the maximum number of slices that nPeople could receive if each person got the same amount of slices and did not get slices from more than 1 pie.

`public int getMaxSlices(List<Integer> pieSlices, int nPeople) { // return answer }`