Some Algorithm questions

From WikiEducator
Jump to: navigation, search

                                                                 Interview Questions
1. Find two strings are anagrams or not, two strings are said to be anagrams if they contain the same characters, ex: cadab and aabdc are anagrams.  

2. There are 1000 bottles and in which one is poison. We have 10 people on whom we can try these bottles. How to find out which bottle is poison.

3. Problem: You have 100 doors in a row that are all initially closed. You make 100 passes by the doors. The first time through, you visit every door and toggle the door (if the door is closed, you open it; if it is open, you close it). The second time you only visit every 2nd door (door #2, #4, #6, ...). The third time, every 3rd door (door #3, #6, #9, ...), etc, until you only visit the 100th door.

Question: What state are the doors in after the last pass? Which are open, which are closed?

4.Find if there exists sum = k in a sorted array in O(n).

5.find the circular order of a string, ex: abcdef, for k=3 the circular order for that string is defabc.

6.Sorting an array of size n with three different number in O(n) time?

7. There are 2n+2 number in which n number repeated twice, find other two distinguish numbers?
   O(1) space and O(n) time.

8. Implement a queue with O(1) MAX element and as usual O(1) for enQ and dQ?

9. There are 50 balls, half of them are red and others are blue. How to distrubute them into two bags so that to maximize the probability of getting red balls.

10. Binary tree qns

11. Implement a queue using stack

12. Implement a stack to get Max element with complexity O(1)

13. There are three buckets which are marked as Red, Blue and R&B. Its known that every bucket is wrongly labeled. In how many number of minimum picks we can label them correctly.

14. 5 pirates problem: There are 5 people who are greedy in nature. There are 100 gold coins.  To distribute these coins they follow this strategy:  The eldest pirate proposes an allocation. All pirates (including the eldest) then vote on the proposal. If he gets >=50% votes then the coins are divided in the way suggested. If not, then the eldest pirate will be killed and the next eldest amongst the remaining pirates proposes a new allocation. So what would be the optimal distibution of coins.

15. Some logical qns:

  Do let me know if  u need ans for any of these qns