CodeSport

Welcome to CodeSport! In this month’s column, we feature a medley of questions covering C/C++, data structures, algorithms and operating systems.

We close the year by featuring a bunch of questions based on the various topics we discussed in this column over the last 12 months. These questions require you to apply some of the concepts we covered through 2010 and should help readers in preparing for software interviews. Let’s get started with some easy questions first.

1. Given a stack data structure that allows these operations: push, pop, is_empty, and peek (returns the value of the topmost element without popping it), you are asked to write a code fragment to sort the elements of the stack in descending order. In other words, once the stack is sorted, the stack top should contain the maximum element, the element next to the top should be the second maximum and so on. Assume that the stack contains N integers. What is the complexity of your algorithm?
2. Given a directed graph G(V, E) where V is the set of vertices and E is the set of edges, you are asked to find if there exists a path between two given vertices (x,y). What would be the complexity of your solution? If you are given a set of vertex pairs and asked to find if there exists a path for each pair of vertices in the set, what would your approach to the problem be?
3. Given a DFS representation of a binary tree, with each vertex and its associated DFS number represented as (v,n) where v is the vertex ID and n is the corresponding DFS number of the vertex v, write an algorithm to give a BFS representation of the same binary tree. Assume that we number the root of the tree with the DFS number 1.
4. Given an undirected graph G(V, E) where V is the set of vertices and E is the set of edges, give an algorithm to determine whether the graph is 2-colourable. (By 2-colourable, we mean that the graph vertices can be coloured with 2 colours such that no two adjacent vertices have the same colour.)
5. Given a set S of N integers, write an algorithm to determine all the subsets of S. What is the complexity of your solution? If you are asked to find all the k-subsets (subsets with k members), what would your approach be?
6. Given a two-dimensional matrix (mxn) of integer elements, in which each row of the matrix and each column of the matrix is already sorted, give an algorithm to find if a number x is present in the matrix.
7. Write a small code snippet to find whether the system stack grows upward or downward on your system.
8. Given a set of cities, and the distances between the cities, you are asked to visit all the cities as part of a tour. Write a program which will ensure that you visit all cities, but travel the minimum number of miles overall in the course of your journey. What is the complexity of your solution?
9. Given an undirected graph G(V,E) where V is the set of vertices and E is the set of edges, write a program to determine whether it is a tree.
10. In C++ programs, when would you prefer to declare your class’ constructor, copy constructor and assignment operator as private functions?
11. We know that malloc and free are standard library functions for allocating and de-allocating memory dynamically in C programs. When we use free, we only pass the pointer to the memory to be deallocated as a parameter, and not the size of the memory block to be deallocated. How does the free library call determine what size the block to be deallocated should be? Give your implementations for malloc and free with an explanation.
12. What is the difference between linking a library statically with your application, versus linking it dynamically? Which is preferred, a statically linked library or a dynamically linked library? Justify your answer.
13. Let’s suppose that you have written an application, and it has been working perfectly on a 32-bit platform. Now you are asked to port your application to a 64-bit platform. What kind of coding changes would be needed?
14. You have written an application, and it has been working well on a little-endian platform. Now you are asked to port your application to a big-endian platform. Besides, your application also reads from files stored on disks, processes the data, and writes back data to disk in output files. What, if any, kind of coding changes would be needed?
15. We all have heard of paging and virtual memory. Does the operating system maintain a page table per process, or is there only one page table for all processes in the system? Explain your answer.
16. In a multiprocessor system with each processor having its own cache, how are the updates made by one processor to a location in its cache made visible to other processors? Does this require hardware support? If not, can you sketch what kind of software support would be needed from the operating system?
17. Given two threads running on two different processors, Thread A running on processor 1 updates the global variable X first, and then the global variable Y. Can thread B running on processor 2 see the updated value of Y before it sees the updated value of X? Explain your answer.
18. You are given three arrays A, B and C, each containing N distinct integers. You are asked to find out whether there exist three such integers a€A, b€B and c€C such that a + b + c = 0. What is the complexity of your solution? Would the complexity be the same if you are asked to repeat this problem for the two arrays, A and B only, such that there exist any two integers a€A and b€B for which a + b = 0?
19. Can you write to a memory location that is not present in the processor cache? If yes, how? If not, why not?
20. We all have used debuggers, and we know that we can set breakpoints to stop program execution at a particular program location. Can you explain how breakpoints are implemented? Does it require underlying hardware support?
21. What is meant by privileged instructions? In a virtualised system (system virtual machine, such as Xen/KVM/Hyper V), how are privileged instructions handled?
22. Given an array of N integers, which is mostly sorted, with very few elements being out of sort (the number of unsorted elements is k, where k << N), what sorting algorithm would you use to sort the array, and why?
23. Given a 32-bit representation of an integer, write a code snippet which, given a bit position k, prints the current bit value at that location, and then flips it.
24. What is the problem with the following code snippet?

    int* bar(int size)
    {
         int* p = alloca(size);
         return p;
    }
    void foo(int n)
    {
         int* myspace = bar(n);
         *myspace = 10;
         ..
    }

My ‘must read book’ for this month

This month, our reader Srividya K, recommends the book Concurrent Programming in Java by Doug Lea. Srividya says that this book helped him understand and apply concurrent programming techniques effectively in developing software for commercial projects.

He also cautions readers that this is not a book for beginners to Java. While on the subject of concurrency, there is an excellent article that discusses how efficiently a lock-free concurrent hash table can be implemented. It is available at as a PDF. This is a good read not just for Java programmers, but for anyone writing concurrent code.

It is also worth reading Cliff Click’s presentation on writing scalable non-blocking code for Java [PDF]. The code corresponding to the data structures discussed in his article is available on Sourceforge.

Feature image courtesy: Valerie Everett. reused under the terms of CC-BY-SA 2.0 License.