Thursday, December 4, 2014

Top List of Programming Interview Puzzles. Code Solution

Following list of programming puzzles and solution (MUST). This list has been prepared with my own voyage through various interviews at Microsoft, Symantec, Google, Adobe and Expedia etc. I have also been in talks with several friends of mine. And following is the list of top problems that seem to be asked in interviews.

Write a function to get the intersection point of two Linked Lists.
There are two singly linked lists in a system. By some programming error the end node of one of the linked list got linked into the second list, forming a inverted Y shaped list. Write a program to get the point where two linked list merge.


Lowest Common Ancestor in a Binary Search Tree.
Given values of two nodes in a Binary Search Tree, write a c program to find the Lowest Common Ancestor (LCA). You may assume that both the values exist in the tree.


String matching where one string contains wildcard characters
Given two strings where first string may contain wild card characters and second string is a normal string. Write a function that returns true if the two strings match. The following are allowed wild card characters in first string.


Anagram Substring Search (Or Search for all permutations)
Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] and its permutations (or anagrams) in txt[]. You may assume that n > m.  Expected time complexity is O(n)


Inorder Tree Traversal without recursion and without stack!
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.


Print all possible strings of length k that can be formed from a set of n characters
Given a set of characters and a positive integer k, print all possible strings of length k that can be formed from the given set.


Print all possible combinations of r elements in a given array of size n
Given an array of size n, generate and print all possible combinations of r elements in array. For example, if input array is {1, 2, 3, 4} and r is 2, then output should be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} and {3, 4}.


Check if a number is Palindrome
Given an integer, write a function that returns true if the given number is palindrome, else false. For example, 12321 is palindrome, but 1451 is not palindrome.


Data Structure for Dictionary and Spell Checker?
Which data structure can be used for efficiently building a word dictionary and Spell Checker?


Count number of binary strings without consecutive 1’s
Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s.


Shortest path with exactly k edges in a directed and weighted graph
Given a directed and two vertices ‘u’ and ‘v’ in it, find shortest path from ‘u’ to ‘v’ with exactly k edges on the path.


Count all possible walks from a source to a destination with exactly k edges
Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk.


--Take Care
And Best Of Luck  :)
Anwar Jamal

Saturday, June 21, 2014

Highest floor fall - Eggs not break Puzzle. It is a 100 floor building.

The Puzzle:

Determine the highest floor on a 100 floor building from which an egg may be dropped without breaking.

You are given two identical eggs, which you can drop from various floors of the building, to carry out your test.

Assume that, if the egg doesn't break after being dropped, it may be reused without suffering any loss of quality.
But if both eggs break before you have determined the highest floor, then you are over.

Find what is the least number of times you must drop the eggs in order to determine the highest floor?

Our Solution:

The answer is: 14

You drop the first egg from the 14th floor.
If it breaks, you can then determine the highest floor by dropping the second snooker ball no more than 13 times.
The above process would be to drop it from the 1st floor, and if it doesn't break, drop it from the 2nd floor, and if it still doesn't break, drop from the 3rd, etc
Hence, 13+1=14 chances

However, if the first egg survives the drop from the 14th floor, you then drop it from the 27th floor (14 + 13 = 27).
If it breaks, you can complete your test in no more than 12 drops with the second ball by dropping it between the floors 15 to 26.

Then, If from the 27th floor the first ball still doesn't break, the next floor to drop it from is the 39th (14 + 13 + 12 = 39).
If it breaks, drop the second ball from floors 28 to 38 (max 11 drops).

after the 39th floor should be the 50th floor (14+13+12+11),
then the 60th floor (14+13+12+11+10), and so on.

If the first ball survives 11 drops, you will be on the 99th floor. In that case, it only takes one more drop to complete the whole test.

So, this solves the puzzle.

Oh! stop. Think again!!!
You have just verified that 14 is the right answer. But how did one reached that answer?
Think again!!

String around the Earth circumference Puzzle. If add some length how much hight it rises?

The Puzzle:

The circumference of the Earth is approximately 40,000 km. There is a string circles the Earth, touching the ground at all locations.
Now if you add just 10 meters to its length, How far will it rise above the ground.

I know your guess would be that it will still graze the surface of earth. The raise would be infinitesimally small. But think again that could a fly,
an ant, or a man squeeze underneath it.

Let p be Pi=3.14159
Use the formula Circumference = 2 × p × R

Before Circumference = 2 × p × R
After Circumference + 10m = 2 × p × (R + Gap)

Subtracting the two:
10m = 2 × p × Gap

So, the Gap = 10m / (2 × p) = 1.6m approximately

So, a man could fit under it easily.

Voila!! This is amazing discovery. 

9999=4 8888=8 1919=? Numerical Counting Puzzle

Now there is a puzzle, which will shake you:
Solve the puzzle.

The puzzle needs you to calculate the number of circles in the numbers.

For instance - 9 has one circle in it. And then 8 has 2

Hence see as below:
9999=4 (each 9 has 1 circle)
8888=8 (each 8 has 2 circles so 2 x 4 = 8)
1816=3 (8 has one circle and 6 has 1 so 2)
1212=0 (no circles in 1 & 2)
Hence, 1919=2 ( 2 circles of the number 9)

I have also seen another solution. THough not a clean one, but still the logic doesnot smells so foul:
See, sum of 9999 is equal to 4. Therefore, each 9 is equivalent to 1.
See 1212 is equal to 0. So 1 and 2 are equivalent to 0.
Therefore, 1919 is (0+1+0+1), so it is equivalent to 2.


Thursday, May 22, 2014

9-5+5*0+3 simple Bodmas Illusion!!

I call this problem of 9-5+5*0+3 as a simple Bodmas Illusion!!

Like asking a grown up to recite nursery rhymes will cause him liitle efforts. But its not that he cannot do so or he has grown lesser in knowledge. It's just you forgot because you are not doing that often. And, then comes perception. Ideas on which you have not worked recently, and have only heard buzz words, will be not in much terms with you - Even if you believe you know it well. That's perception or simply I-Know-That-Stuff-Well syndrome. For instance just ask yourself how well you know about Big data or NLP or AWS or even cloud computing in that sense. Lol ;)

In the similar vein, I post you a simple puzzle today. What do you feel is answer to :

9 - 5 + 5 x 0 + 3 = ?

I myself posed this question over my WhatsApp group and found many giving correct answer. But I was amazed by many who gave wrong. Here, I am not talking about some completely vague answers like 0, 10 and 90. You won't imagine, I even had these responses. Yes! That's true!!

In any case, the most preferred answers were 1 and 7. To your surprise, 1 received the largest share of vote. However, the correct answer is 7.

People who came with 1 as answer did following:
Equation: 9-5+5x0+3=...? I believe the answer is 1, is that correct?

And, yes the keyword that they stood by was BODMAS Rule.

However, the correct answer being 7, needs other explanation. And, in any sense it should not violate Bodmas as well. You know its hard to shun whatever you learnt in childhood. God! Why don't we learn to love and love and love...

Anyways, the workflow for the correct answer is as follows;
5*0 is 0
So it becomes, 9-5+0+3
ie. 9-5+3
In algebra what we follow, we do arithmetic by the rule of BODMAS. But here, by bodmas it does not mean 9-(5+3). So, 1.
No, No. 1 is wrong answer. Because what we assumed here is an imaginary bracket, which never existed. Look, now you must have started feeling why the post is termed to be as Bodmas Illusion!!

In algebraic calculations and closed group mathematics which the world follows, we practice Right to left arithmetic. So even if you add first, it is -5+3 which is -2. At last 9-2 gives 7.

Or simply, 9-5+3 by right to left gives 4+3 hence 7.

Had the puzzle been so simple, it would have not come in my post. You can even type "9-5+5*0+3" on Google to see what it calculates.

Someone has learnt Bodmas again!!