In this month’s 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 month’s column, let’s 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