Published 17 July 2012 07:23, Updated 18 July 2012 03:56

**
**

Via MyCareerStack comes a list of questions prospective Google employees should be able to answer if they want to work for the world’s most effective creator of search algorithms.

But be warned, unlike the Apple employment questions we’ve looked at before, some of these puzzles require serious maths skills.

Here’s a taste:

**1. MINIMUM COST FOR PAINTING A ROW OF HOUSES IN THREE DIFFERENT COLOURS**

There are N houses in a row. Each house can be painted in either Red, Green or Blue colour. The cost of colouring each house in each of the colours is different.

Find the colour of each house such that no two adjacent house have the same colour and the total cost of colouring all the houses is minimum.

The question intends to state that cost of painting any house in any colour is different, so if cost of painting House 1 in Red is say, X then the cost of painting House 2 in red will some other value Y. It can be considered each house has different dimensions and hence cost of painting in each colour is different, and the cost of paint for each house also varies.

You have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.

**3. FIND WHETHER A WORD CAN BE FORMED BY TWO WORDS IN A DICTIONARY**

Given a dictionary find out if a given word can be made by two words in dictionary. For eg. given “newspaper” you have to find if it can be made by two words. (news and paper in this case).

And, via Business Insider, the answers:

**1.** “This problem can be modelled as a “Dynamic Programming” problem, a method for efficiently solving a broad range of search and optimization problems.

“Here’s the line of code you’d use to answer it:

“C[i][c] = H[c] + min(C[i-1][x]) x belongs to {Red, Blue, Green} x belongs to c

“This function is the cost of painting the row of houses ending at the “ith” house so that house is painted in a colour “c.” (i is a placeholder for a number that goes up as the function computes.)

“‘c’ is chosen such that the previous house is not in the same colour.”

**2.** “You have to buy a stock before you can sell it. This little restriction actually completely changes the outcome of the problem. So now you have to track the minimum value’s index. Here’s the whole solution:

“To solve this problem efficiently, you would need to track the minimum value’s index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).”

**3.** “Say you have the word ‘newspaper’. You want to split the word in half, which would give you ‘newsp’ and ‘aper’. Then, check the dictionary. If there’s no result, you decrease the length of one of the words and increase the length of the other.

“When you do that to ‘newsp’ and ‘aper,’ you get ‘news’ and ‘paper’ — which end up in a dictionary.”

For all the Google questions and answers, go to MyCareerStack (registration required for answers). Or for an extended sample of questions and answers, go to Business Insider.

**READ NEXT:**

advertising

advertising

advertising

## Comments