In this months column, we feature a set of interview questions based on algorithms and data structures.
For the past few months, we have been discussing information retrieval and natural language processing, along with the algorithms associated with them. Some of our readers had written in requesting if we could discuss a practice set of questions in algorithms and data structures as it would help in preparing for campus interviews. Hence, in this months column, lets take a break from natural language processing and, instead, explore potential interview questions on algorithms and data structures.
1. You are given a circular list of n numbers that are strictly increasing. Since it is a circular list, the end of the list wraps over to the beginning of the list. You are given an arbitrary pointer to an element in the list. You need to find the minimum element in the list. To simplify things, you can assume that all the elements are distinct.
2. You are given an array of N integers. There are no duplicates in the array. Consider the subsets of this set, the cardinality of which is (N-1). There are (N-1) subsets of cardinality (N-1). For each such set, your program should output the product of the elements present in it. For instance, if you are given the array containing 10, 20, 30, 40, we have the three subsets: {10, 20, 30}, {20, 30, 40}, and {30, 40, 10}. The algorithm should output the three values 6000, 24000 and 12000. Can you come up with an O(N) algorithm for computing all the (N-1) products?
3. Given an NXN matrix of integers, where each row and each column is sorted independently, design an algorithm to search for an integer k. How many comparisons does your algorithm make before it can either find the integer or determine that the integer does not exist in the matrix?
4. You are given two strings: s and t. You need to determine whether t is a cyclic rotation of string s. For instance, string t is obtained by rotating each character of string s by k positions. For example, the string kite is a cyclic rotation of string teki. You are told that N is the maximum size of the string. Can you write code to determine this in O(N) time with constant additional storage?
5. Let A be a sorted array of integers. You are given an integer K. Write a program to determine whether there are two indices i’ and j such that A[i] + A[j] = K. Note that i’ and j need not be distinct. Can you do this in O(N) time?
6. Different sorting algorithms exhibit efficiency depending on the type of input data. ‘As an example, some algorithms behave well if the input data is almost sorted. As an example, consider insertion sort. When the data is mostly sorted, how many comparisons do you need to make for sorting it using insertion sort? Let us consider the situation in which we need to process a stream of integers. Each integer is at most 100 positions away from its correct sorted position. Can you design an algorithm to sort the integers that use only a constant amount of storage, independent of the number of integers processed?
7. You are given a sequence of n numbers whose values vary between 1 to n-2, with two of the numbers repeating twice. For instance, instead of having <5,2, 3, 4, 1>, you are given <2,1,3,2,1>. You need to find out the two numbers that each get repeated. Can you find the two numbers if you are told that you can only use extra storage of a constant size?
8. Assume that you are given a singly-linked list that does not contain a loop, and the last node of which has its next field set to NULL. How will you find the node that is Kth nodes away from the last node on the list?
9. Given that you are asked to design a dictionary data structure for integer data elements, which is expected to support, insert, delete and find operations, please compare the following data structures as potential candidates in terms of time complexity:
- Unsorted array
- Sorted array
- Unsorted singly linked list
- Sorted singly linked list
- Unsorted doubly linked list
- Sorted doubly linked list
- Binary search tree
- Hash table
- Binary heap
10. We are all familiar with merge-sort. Given an array of N integer elements, lets break up the array into two halves, sort each half separately and then merge the two sorted halves. This is a classic example of the divide and conquer approach, by which the problem is broken down into several sub-problems. Each is solved recursively, and then you combine the solutions for the sub-problems to solve the original problem. Is it always possible to design adivide and conquer algorithm to all problems? If not, what characteristics should a problem exhibit to be amenable to this approach? Can you give an example of a problem which is not amenable to the divide and conquer approach and explain why it is not suitable?
11. You are given a set A containing N integer elements and asked to solve the problem of finding the minimum in a given range of A. For instance, if A is {8, 2, 9, 5,1,4, 11, 3, 14}, the range minimum for A[1
5] is given by the element A[5], since A[5] is 1 and that is the minimum element in the range A[1..5]. Can you come up with an O(N) algorithm for solving the range minimum query if you are allowed to preprocess the set A?
12. Let A be a multi-set of integers consisting of N numbers. You are allowed to pick up two integers at a time. If both are even or both are odd, you discard both and insert an even integer. If not, you discard the even integer. Given that there are an even number of odd integers initially in A, can you tell whether the last integer will be even or odd? What is the reasoning behind your answer?
13. You have 100 doors in a row, all of which are initially closed. You make 100 passes over these doors starting with the first door. The first time when you make the pass, you visit every door and toggle the door (i.e., if the door is open, you close it. And if it is closed, you open it). During the second pass, you visit every second door (doors numbered 2, 4, 6,8
). During the third pass, you visit only every third door (doors marked 3, 6, 9, 12
). You repeat these passes until you finish all the 100 passes. Now can you determine what state each door is in, after the 100th pass? Which doors are open and which are closed?
14. The lowest common ancestor (LCA) of two nodes u and v in a binary search tree is defined as node A, which has both u and v as its descendants (note that a node can be its own descendant). Write an algorithm to find the lowest common ancestor of a binary search tree. Instead of writing a new algorithm for finding the LCA, if you are given the in-order traversal of the binary search tree along with the nodes u and v for which the LCA needs to be found, can you use the in-order traversal information to determine the LCA? Does this work in all cases? If so, explain why. If not, give a counter-example.
15. You are given an undirected graph G (V, E) where V represents the set of vertices and E represents the set of edges, and a weight function c(u,v), which associates a non-negative weight with the edges of the graph. A minimum weighted cycle in the graph is defined as the cycle, whose sum of edge weights is the minimum over all cycles in the graph. A maximum weighted cycle is one whose sum of edge weights is the maximum over all the cycles in the graph.
(i) Can you come up with an algorithm for finding the minimum weighted cycle? What is the complexity of your algorithm?
(ii) Can you come up with an algorithm for finding the maximum weighted cycle? What is the complexity of your algorithm? Can you come up with a polynomial time algorithm for this problem? If not, why not?
My must-read book for this month
This months book suggestion comes from one of our readers, Shruti, and her recommendation is very appropriate to this months column. She recommends an excellent resource for algorithmic problemsthe website containing a discussion on algorithms from Jeff Erickson, available at http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/. The link has pointers to lecture notes as well as additional exercises in algorithms and data structures. Thank you, Shruti, for sharing this link.
If you have a favourite programming book/article that you think is a must-read for every programmer, please do send me a note with the books name, and a short write-up on why you think it is useful so I can mention it in the column. This would help many readers who want to improve their software skills.
If you have any favourite programming questions/software topics that you would like to discuss on this forum, please send them to me, along with your solutions and feedback, at sandyasm_AT_yahoo_DOT_com. Till we meet again next month, happy programming!
