Browsing the archives for the interview tag

Implement strstr

Question: Implement strstr in Java. Find the first instance of a string in another string. Answer: public int Search(String haystack, String needle){ for(int i = 0; i < haystack.length(); i++ ) { for(int j = 0; j < needle.length() && i+j < haystack.length(); j++ ) { if(needle.charAt(j) != haystack.charAt(i+j)) { break; } else if (j […]

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 […]

Balanced Tree

Question: How would you check if a binary tree is balanced? Answer: A tree is considered balanced when the difference between the min depth and max depth does not exceed 1. Recursive algorithms always work well on trees, so here’s some code. int min_depth( Node * root ) { if( !root ) { return 0; […]

5 Comments

Queue Using Stacks

Question: How would you use stacks to implement a queue? Answer: So how could we go about doing this? What if we used two stacks and used one as the incoming stack and the other as the outgoing stack? A queue is a FIFO structure, so when we enqueue something, we need to make sure […]

3 Comments

Boxes of Money

Question: You are given b boxes and n dollar bills. The money has to be sealed in the b boxes in a way such that without thereafter opening a box, you can give someone a requested whole amount of dollars from 0 to n. How should b be related to n for this to happen? […]

3 Comments

Chasing Dogs

Question: There are four dogs each at the corner of a unit square. Each of the dogs starts chasing the dog in the clockwise direction. They all run at the same speed and continuously change their direction accordingly so that they are always heading straight towards the other dog. How long does it take for […]

5 Comments

Red and Blue Marbles

Question: You have 50 red marbles, 50 blue marbles and 2 jars. One of the jars is chosen at random and then one marble will be chosen from that jar at random. How would you maximize the chance of drawing a red marble? What is the probability of doing so? All 100 marbles should be […]

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

Burning Sticks

Question: You have two sticks and matchbox. Each stick takes exactly an hour to burn from one end to the other. The sticks are not identical and do not burn at a constant rate. As a result, two equal lengths of the stick would not necessarily burn in the same amount of time. ¬†How would […]

2 Comments