House Robber | Dynamic Programming

Problem: You have n houses with certain amount of money stashed in each house. You can not steal any adjacent houses. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can steal. Solution: This is a simple dynamic programming problem. The key is Read More →

The Pill Problem | Hard Brain Teaser

Man and 3 Pill Puzzle

Puzzle: This is very hard brain teaser. A man has a medical condition that requires him to take two kinds of pills, call them P1 and P2. The man must take one P1 pill and one P2 pill each day, or he will die. If he takes more than 1 pill of the same kind Read More →

Rotate Matrix By 90 Degree

Problem description: Given an N X N integer matrix, rotate it bye 90 degrees in place.In-place means minimal extra memory to be used, i.e. don’t make a new array to copy into). Rotate clockwise means top-row becomes right-column, right column becomes bottom-row etc. eg. Solution: The idea is to do a “four-way” swap variable, we 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 →

Combination Sum Problem

Problem: Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2,…, ak) must Read More →

100 Blue Eyes Puzzle

Puzzle: This puzzle is one of the hardest puzzle in the world. If you are able to solve this, believe me you are genius. A group of people with assorted eye colors live on an island. They are all perfect logicians — if a conclusion can be logically deduced, they will do it instantly. No 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 →

Car Wheels Problem

Puzzle: A car has 4 tyres and 1 spare tyre. Each tyre can travel a maximum distance of 20000 kilometers before wearing off. What is the maximum distance the car can travel. You are allowed to change tyres (using the spare tyre) unlimited number of times. Note: All tyres are used upto their full strength. Read More →

Word Ladder Problem

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 →

How to Check if a given Number is Fibonacci number?

In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence: 1,1,2,3,5,8,13,21,34,55,89,144.. A simple way is to generate Fibonacci numbers until the generated number is greater than or equal to ‘x’. Following is an interesting property about Fibonacci numbers that can also be used to check if a given number Read More →