## 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.

--> http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-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.

--> http://www.geeksforgeeks.org/wildcard-character-matching/

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)

--> http://www.geeksforgeeks.org/anagram-substring-search-search-permutations/

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.

--> http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

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.

--> http://www.geeksforgeeks.org/print-all-combinations-of-given-length/

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}.

--> http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

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.

--> http://www.geeksforgeeks.org/check-if-a-number-is-palindrome/

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

--> http://www.geeksforgeeks.org/data-structure-dictionary-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.

--> http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

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.

--> http://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/

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.

--> http://www.geeksforgeeks.org/count-possible-paths-source-destination-exactly-k-edges/

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