Programming Interview

Print All Possible Words from Phone Digits

Print all possible words from phone number digits. This question is asked by companies like microsoft, google, facebook, Amazon. Lets see example input/output to understand this problem. For example if input number is 234, possible words which can be formed are (Alphabetical order): adg adh adi aeg aeh aei afg afh afi bdg bdh bdi Read More →

String Decode Problem

Problem: If a=1, b=2, c=3,….z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings. For example: Input: “1123″. You need to general all valid alphabet codes from this string. Output List aabc //a = 1, a = 1, b = 2, c = 3 Read More →

Dynamic Memory Allocation (Stack vs Heap)

The Stack What is the stack? It’s a special region of your computer’s memory that stores temporary variables created by each function (including the main() function). The stack is a “LIFO” (last in, first out) data structure, that is managed and optimized by the CPU quite closely. Every time a function declares a new variable, Read More →

Design of a Tinyurl Service

What is tinyurl? A tinyurl service compresses a long url into a short one. This saves space, and is useful for scenarios such as twitter or weibo, where each character counts. The down side is possible spam use. Concerns include longevity of a short url. i.e. “http://tiny.me/5ie0V2″. The highlight part can be any string with Read More →

Construct Binary Tree from Postorder and Inorder Traversal

Given postorder and inorder traversal of a tree, construct the binary tree. Solution: The post order array contains the elements in the order of post order traversal of the binary tree and we know that the last element in the post order traversal is the root of the binary tree. We can then search the Read More →

Construct Tree from given Preorder and Inorder Traversals

Given preorder and inorder traversal of a tree, construct the binary tree. Solution: The pre order array contains the elements in the order of pre order traversal of the binary tree and we know that the first element in the pre order traversal is the root of the binary tree. We can then search the Read More →

Flatten A Binary Tree to Linked List (In-place)

Problem: Given a binary tree, flatten it to a linked list in-place. For example, The flattened tree should look like: Solution: We can solve this problem recursively by doing a in-order traversal of the tree. Implementation:(Recursion) Non-Recursion, No Stack We can also solve the problem even without a stack: Each time when we prune a Read More →

Problem: Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: Only one letter can be changed at a time. Each intermediate word must exist in the dictionary For example, Given: start = “hit” end = “cog” dict = ["hot","dot","dog","lot","log"] As one shortest Read More →

Find the Missing Element in Arithmetic Progression

Problem: Find the missing number in an Arithmetic Progression. An Arithmetic Progression is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers. You are provided with consecutive elements of an Arithmetic Progression. There is however one hitch: exactly one number from the original series Read More →

Check if Binary Tree is Height Balanced?

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. The solution presented is a recursive. Find the height of left and right subtrees and check the difference of Read More →

Set every cell in matrix to 0 if that row or column contains a 0

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. This problem should be solved in place, i.e., no other array should be used. We can use the first column and the first row to track if a row/column should be set Read More →

Edit Distance – DP Problem

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Input: str1 = “cat”, str2 = “cut” Output: Read More →