Interview Corner

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

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

 

Solution
Whenever there are strings involved in question, think tries 🙂 And when there is a maze, think backtracking. Combine both and you get the solution.
For complete analysis and solution, have a look at post.Tries : Find words in maze

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.

Solution:
We have a capacity, value associated with the decision and we want to maximize the value. Sounds familiar? Yes, it is typical case of knapsack problem. Again since we cannot store partial file, its 0/1 knapsack problem. Further discussion on this is this post: Dynamic programming : 0-1 knapsack problem

4. Implement a Least Recently Used cache algorithm.

 

Basics of paging, various approaches for cache management, data structures and algorithms used are explained in post. Least Recently Used cache

 

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.

Solution
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

Non Flattened list
Well, we hitting three birds with one stone. Let’s look at the solution. What would be the first integer in the resultant array?
Yes it would be among first integers of given input array. We take minimum of all integers at first position of given input arrays. Now, how about second element? Second integer would be from integers which are left at first location, and integer at second position of array from which first integer was selected. Take minimum from these and put at second location. Similarly for the third and so on.
If you see we always want minimum of all candidates. What data structure gives minimum among all with good complexity? Yes, its min heap in O(1) time complexity. Detail analysis and implementation is at below post. Merging N sorted arrays in one

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.

Queues : Print last N lines of a file

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.

Solution:
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?

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

Solution
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 :

Find N most frequently occurring words in a file

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 jitsceait@gmail.com

  • Hafeez

    if there is a index page for every topic, that will be great.

    • http://algorithmsandme.com/ Jitendra Sangar

      I did not get it. Can you please explain what do you mean by index of every topic?

      • Hafeez

        Like for every data structure or a algorithm type, maintain a list of questions or problems. that will be helpful.

        • http://algorithmsandme.com/ Jitendra Sangar

          There is one menu option at the end : Collections(DS wise)
          There I am planning to provide index pages. Hope that helps!

  • Pingback: Merge sort implementation - Algorithms and Me()