Browsing the archives for the tricky tag

Search in a sorted rotated array

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable. Answer: We can do a binary search with some modified checks. public int rotatedSearch(int[] values, int start, int end, int x){ if(values[start] == x){ return start; } else if(values[end] == x){ return end; } […]

Challenge – First Common Ancestor

Question: How would you find the first common ancestor of two nodes in a binary search tree? First as in the lowest in the tree. Another way to ask is to find the lowest common ancestor of two nodes. Challenge: Do you know the answer to this question? Post in the comments. Answers will be posted […]

The Fox and The Duck

Question: A duck that is being chased by a fox saves itself by sitting at the center of circular pond of radius r. The duck can fly from land but cannot fly from the water. Furthermore, the fox cannot swim. The fox is four times faster than the duck. Assuming that the duck and fox […]

2 Comments

10 Google Interview Puzzles

Here is a list of 10 puzzles which have been asked on a Google Interview. They are not in any specific order. Reverse a Linked-List Reverse a Linked-list. Write code in C. Answer Challenge – Equal Probability between 1 and 7 Write a method to generate a random number between 1 and 7, given a […]

Anagrams in an Array of Strings

Question: You are given an array of strings and you are asked to display all the anagrams within the array. For those who don’t know, two words are anagrams if they contain the same characters. Answer: The brute force solution would be to take each string and compare it to every other string in the […]

Three Switches

Question: You are standing outside a room next to three switches, all of which are off. Each switch operates a different light bulb in the room. The room door is closed, so you cannot see which switch operates which bulb. You are only allowed to go into the room once. Determine which switch operates which […]

0 Comments

Pick a Random Byte

Question: You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer: Since we can only store […]

6 Pirates Fight for 1 Gold Coin

Question: Six pirates discover a chest containing 1 gold coin. They decide to sit down and devise a distribution strategy. The pirates are ranked based on their experience (Pirate 1 to Pirate 6, where Pirate 6 is the most experienced). The most experienced pirate gets to propose a plan and then all the pirates vote […]

4 Comments

What’s Your Eye Color?

Question: On a certain island there are people with assorted eye colors. There are 100 people with blue eyes and 100 people with brown eyes. Since there are no mirrors on this island, no person knows the color of their own eyes. The people on the island are not allowed to talk or communicate with […]

9 Comments

Is Your Husband a Cheat?

Question: A certain town comprises of 100 married couples. Everyone in the town lives by the following rule: If a husband cheats on his wife, the husband is executed as soon as his wife finds out about him. All the women in the town only gossip about the husbands of other women. No woman ever tells […]

27 Comments