## Google Interview Questions

- 4of 4 votes

AnswersGiven a string return the longest palindrome that can be constructed by removing or shuffling characters.

- enkadi13 July 22, 2016 in United States

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.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

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

- enkadi13 July 22, 2016 in United States

Example:

Input:

67892

46789

14678

01467

Output:

True| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm Arrays - 0of 0 votes

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

- Deepak Agrawal July 16, 2016 in India

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.| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

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

- miscanon July 15, 2016 in United States

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

Google Intern Algorithm - 0of 2 votes

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

- rucknrull July 14, 2016 in United States

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)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswerWrite a program for skyyscrapper?

- CareerCupUser1 July 09, 2016 in United States

http://www.conceptispuzzles.com/index.aspx?uri=puzzle/skyscrapers/techniques| Report Duplicate | Flag | PURGE

Google SDE-3 Algorithm - 0of 0 votes

AnswersList of string that represent class names in CamelCaseNotation.

- lavankumarmuvalla July 07, 2016 in United States

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]| Report Duplicate | Flag | PURGE

Google String Manipulation - 2of 2 votes

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

- theconqueror July 07, 2016 in United States

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?| Report Duplicate | Flag | PURGE

Google Software Engineer - 6of 6 votes

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

- emb June 26, 2016 in United States

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 :)| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - -8of 8 votes

AnswersGiven set of characters and a dictionary find the minimum length word that contains all the word from the given word

- darklight June 19, 2016 in India| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersGiven 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

- darklight June 19, 2016 in India| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

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

- pushpinder2751 June 17, 2016 in United States| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 2of 2 votes

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

- ankit3600 June 14, 2016 in India

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.| Report Duplicate | Flag | PURGE

Google SDE-2 Algorithm - 0of 2 votes

AnswersA 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:

- emb June 06, 2016 in United States`[move(10), rotate(180), move(10)] -> answer is yes [move(10), rotate(45), move(10), rotate(-45), move(10), rotate(45)] - answer is no`

| Report Duplicate | Flag | PURGE

Google Software Developer Brain Teasers - 3of 3 votes

Answers# take an array and print non over lapping in order pairs. example:

- thegeek21 June 05, 2016 in United States`# [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)`

| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 2of 2 votes

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

- emb June 05, 2016 in United States| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 3of 3 votes

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

- testing@123 June 01, 2016 in United States| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - -3of 3 votes

AnswersWrite program that takes integer, deletes one of two consecutive digits and return greatest of all results.

- josearturodelosangeles June 01, 2016 in United States| Report Duplicate | Flag | PURGE

Google Applications Developer Coding - 0of 0 votes

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

- Ajay Kumar May 29, 2016 in United States for Google Docs

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| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

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

- theconqueror May 27, 2016 in India

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.| Report Duplicate | Flag | PURGE

Google Algorithm - 0of 0 votes

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

- geekofthegeeks May 23, 2016 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven a binary tree, find the largest subtree having atleast two other duplicate subtrees .

- geekofthegeeks May 22, 2016 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven the following decoder, write the encoder. (The encoder should be written to compress whenever possible):

- geekofthegeeks May 22, 2016 in United States

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| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

Answersgiven 2 strings A and B. generate all possible solutions when B is merged in A.

- JerryGoyal May 22, 2016 in India

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.| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 0of 4 votes

AnswersTake an example of the traditional Iterator interface which has the following methods

- lks May 17, 2016 in United States

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| Report Duplicate | Flag | PURGE

Google SDE-2 Coding - 0of 2 votes

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

- Dinkleberg May 09, 2016 in United States`public int getMaxSlices(List<Integer> pieSlices, int nPeople) { // return answer }`

| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - -15of 17 votes

AnswersIs Golang a good choice for coding interviews?

- amit April 20, 2016 in India| Report Duplicate | Flag | PURGE

Google Software Engineer - -16of 18 votes

AnswersDoes Google/Microsoft/Amazon/Facebook allow Golang in coding interviews?

- amit April 20, 2016 in India| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window