1. I have a tree, I give it to you. You have freedom of choosing any data structure but tree. You need to memorize the tree in that data structure. Once you done, i take my tree back. You need to reconstruct the tree. 🙂
How can you construct a tree if all node values are given? What else we require? Yes, we require the relationship between nodes. Any of the three tree traversals give us one relationship. But as we already know, for creating an unique tree of give nodes, we need at least two traversals of tree.
Bang! We are at solution. Store any two traversals of given tree in arrays and later reconstruct tree using those two traversals.
Construction of tree using in-order and preorder traversals is explained at Binary Search Tree : Build binary search tree given inorder and preorder traversal
2. I have a maze of size N x N characters. Also I have been given a dictionary which contains list of valid words. Ask is to find all words hidden in the maze. Adjacent characters of word can be either horizontally or vertically adjacent.
3.We have N files each having a size say Si. We have a total storage capacity of W bytes. For each file to be store the re-computation cost is Vi. Problem is to store as files on storage that combined size of all files is less than W and their re-computation value is maximum.
We can either store or leave the file. We cannot store partial file.
4. Implement a Least Recently Used cache algorithm.
5. We have N machines each having list of numbers in sorted order. We need to output all numbers from all machines in sorted order.
This is same problem as: We have N arrays of integers which are individually sorted. We need to combine all these arrays into a single array which contains all integers in sorted order. Same concept can be used in while flattening a list which has down and right pointers. Each list traversed by down pointers are sorted. Flattened list should be in sorted order. One solution for this problem is provided at link:Linked List : Merge two sorted linked lists
If you want to test this program on various inputs,here is ideone link : Merge
6. Print last N lines of a given log file.
This problem can be solved with simple application of queue data structure. For detail analysis and code see following link.
7. I have 22 players. Each player has a value associated with him. I need to divide them into two teams of eleven each, so that difference between overall values of teams is minimum.
This problem can be mapped to balanced partition of array problem.
Detail analysis and implementation is given in this post. Balanced partition problem
8.Given two river banks (visualization : two parallel lines), one bank has numbers written (1….n) in sorted order. On the other bank the numbers (1…n) are arranged randomly. A bridge can be formed from the ith point from bank 1 to ith point in bank 2. Find the max number of non-intersecting bridges you can form?
This is typical case of finding longest increasing subsequence in an array. Please go through following post for more details Dynamic Programming : Largest increasing sub sequence in an array
9. Given a room with N persons in it. A person X is friend with person Y if they are directly or indirectly friends. That is to say if A is friend of B and B is friend with C then A and C are also friends.
A group of friends is a group where any two persons are friends. Given a list of persons who are directly friends, find number of such groups.
This is typical application of connected components of a graph. For details please refer to this post : Graphs : Connected components
10. Given a dictionary like text file, find n top occurring words in it i.e. n words whose count is the maximum. Find N most frequently occurring words in file.
Where there is top or least to be found, heap are the best data structures. There we will use has map to aid counting of words. Find complete solution here :
Check out this section for more questions which can be easily solved using standard approach once we identify the concept.
If you have some interesting questions, leave me a comment or mail at email@example.com