CodeSport

We have been discussing compiler optimisation over the last few columns. However, a couple of our readers reminded me that we used to feature a set of programming questions for our December column — and this time, I missed doing that. Thank you, Sunil and Shreya, for the timely reminder. Hence, in this month’s column, we will take a break from our discussion on inter-procedural optimisations and turn to discussing a few interview questions. Let’s start off with a few puzzles, followed by programming questions.

This month’s questions

1. 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 odd, 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?
2. There is a building with N floors. You are given M balls. You are told that there is an integer K < N such that if the ball is dropped from the floor K or any floor higher than K, it would break. But the ball would not break if you drop it from a floor below K. What is the minimum number of balls that you need to drop to determine K: (a) in the best-case scenario; (b) in the worst-case scenario?
3. 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, close it; if it is closed, open it). During the second pass, you visit every second door (doors numbered 2, 4, 6, 8…, and so on). 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?
4. You are given a coin and you have been told to use this for a coin-tossing experiment. You are told that the coin is weighted to come up heads more times than tails. Given such a biased coin, how can you get a fair coin toss?
5. You are given a sequence of numbers from 1 to n-1, with two of the numbers repeating twice. For instance, instead of <1,2,3,4,5>, you are given <1,2,2,3,3,4,5>. You need to find out the two numbers which are repeated. Can you find the two numbers if you are told that you can only use constant-size extra storage?
6. Three coworkers are discussing salary issues in their company. They want to know whether the average salary of an employee in their company is greater than the industry average. They have found the industry average salary from a magazine survey. For the average salary in their company, they decide to take the average of their salaries (they assume that they are the only three employees in the company). However, they do not want to disclose their salaries. How can they take the average without disclosing their salaries?
7. You are travelling on a road and have reached a junction where two paths diverge. One path will take you to your correct destination. However you do not know which is the correct path, and alas, there are no sign boards! However, a truth teller and a liar are standing at the junction to help/confuse you. The truth-teller will always answer any question you ask truthfully. The liar will always answer any question you ask falsely. Now, you are allowed to ask only one question. You do not know who the truth-teller is and who the liar is. What is the single question you can ask to help you find the correct road to your  destination?
8. A permutation of length N is a one-to-one onto mapping p from 0, 1, 2,…… -1 on to itself. A permutation can be applied to an array A of N integers. Π(A[i]) = A[Π(i)]. If you are allowed any amount of additional storage, how can you obtain the permutation of A given Π? If you are allowed to use only a constant amount of additional storage, how would your solution change?
9. We all know that the standard memory allocator function malloc is used for allocating memory in C programs. The size of the memory allocated in bytes is passed to malloc as a parameter. What would be the program behaviour if I pass zero as the parameter to malloc?
10. We are all familiar with signals such as SIGSEGV/SIGBUS, etc. I am a malicious user and I want to kill the programs of all users other than myself on the machine running Linux. Can I send a signal which will kill all other users’ processes?
11. Can one use a floating-point constant value as an enumeration constant in C programs?
12. Remember that functions allocate storage on the stack to hold the activation records. You are asked to write a function which will return its stack size. How can you do this?
13. Here is a small code snippet:

    int* foo(void* p)
    {
            p = p + 3;
            return (int*)p;
    }

    Can you identify any bug in the above code?

14. 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.
15. Given two strings s and t, write a program to find all occurrences of t in s. You are originally told that s contains a maximum of 1,000 characters. Now, after having written your program to solve the problem, the examiner tells you that he was wrong, and s can contain 100,000 characters. Do you need to rewrite your algorithm to solve the problem?
16. 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 a code to determine this in O(N) time with constant additional storage?
17. You are given a list of points in a two-dimensional Cartesian plane <X1, Y1>, <X2.Y2>….. <Xn, Yn>. You are asked to find the pair of points closest to each other in the Cartesian plane.
18. We typically use malloc and free to allocate/deallocate memory on the heap in C programs. However, in your case, you have been told that the dynamic memory has to be shared between two processes. Therefore, you need to do dynamic memory allocation on a shared memory segment, which can be shared between two processes. Can you write skeleton code to implement a dynamic memory allocator on a shared memory segment?
19. You are given a number N and asked to write a function to determine whether it is prime or not. Now that you have written the solution, you have been told to find that 10,000th prime number. Would it be more efficient to reuse your previous solution to solve this problem or would you create a new program to determine the 10,000th prime number? What is the runtime of your solution in either case?
20. You are given a stream of integers which come in as input. At any point of the input stream, you can be asked to determine the current maximum and the second largest number seen so far in the stream. Can you write a function to do this?

My ‘must-read book’ for this month

This month’s “must-read book” suggestion comes from one of our readers, Unnikrishnan, who recommends Introduction to Algorithms: A Creative Approach by Udi Manber. This book teaches you to examine each step in the algorithm design process and even takes you through the process of algorithm design by carefully crafted examples. Thank you, Unnikrishnan! I have not yet read the book but am hoping to do so in the coming months.