CodeSport

In last month’s column, we had looked at Dynamic Software Updates (DSU), discussing the issues associated with patching an application dynamically. The problem was also related to the DSU problem. We considered the issue of modifications to data structures whose instances have already been created.

For instance, consider a linked list of objects that is created at application startup, and which is accessed throughout the lifetime of the application. Now the developer, as part of a defect fix, has added a new field to each object. Therefore, the DSU contains code which sets/gets the new field added. However, this newly added field is not a standalone variable; it is part of an existing data structure that has already been allocated by the application, and whose references are held in other objects.

The question was whether it is possible to perform a DSU in such a case. Two of our readers, P Selvaraj and R Harish, had written in with the correct answers to the question. Congrats to both of you. As you both have mentioned, a DSU system needs to provide a way for the developer to supply data migration routines.

In our example, the programmer would supply a data migration routine as part of the DSU, to copy the old linked list to the new linked list. This routine would be invoked as part of the DSU process, so that when dynamic patching is complete, the linked list is set up correctly with the data from the old linked list. Note that the linked list would be instantiated with the new type containing the new field added by the developer, and initialised appropriately, in the data migration routine.

We had a few requests from readers to provide a set of practice questions in C/C++, algorithms and
data structures. Hence, this month’s column features a few questions from these topics. Let’s start off
with a set of questions from C++.

1. What is the difference between a dynamic cast and typeid in C++? When would you choose to use one over the other?
2. What is compile-time polymorphism as against runtime polymorphism?
3. What is meant by partial specialisation of templates?
4. Consider the following snippet:

   class Employee {
       int emp_id;
       public:
       int get_emp_id();
       virtual void print_attributes();
   }
   class Manager: public Employee {
        int level;
        Employee* managed;
        public:
                   void print_attributes();
         }
          void foo (Employee* e){
                 (*e).print_attributes();
         }

   In the above code snippet, look at the function foo. What would be the version of the print_attributes that are called here?

5. We all know that const_cast can be used to cast away the constness of an object. Is there a bug in the following code?

   class Employee {…}
   const Employee e = {2, 10000};
   foo (&e);
   
   void foo (const Employee& e1)
   {
           Employee* e2 = const_cast<Employee*> e1;
           e2->set_emp_id (12);
   }

6. You have a group of items, each uniquely identified by its name. Each item has a price associated with it. The common queries are:
   1. Given the name of an item, you need to know whether it is present or not.
   2. You are asked to find the subgroup of items whose names start with letters of the alphabet between “m” and “s”.
   3. You are asked to find the total price of all the items you have.
   4. Given that I have another group of such items, I give my group of items to you to merge them with your group, and repeat the above queries (a) to (c).

   What is the STL data structure you would use to represent the group of items? Justify your use of the specific data structure.

7. Virtual destructors are supported in C++, so that based on the type of the object pointed to by the pointer/reference, the appropriate destructor can be called. Why doesn’t this argument hold true for supporting virtual constructors?
8. If you look at template definitions in standard STL headers, you would often see the term “traits”. For instance, basic_string is associated with character traits, and an iterator is associated with iterator traits. So what exactly are “traits”?
9. Different sorting algorithms exhibit efficiency depending on the type of input data. For instance, some algorithms behave well if the input data is almost sorted. As an example, consider an insertion sort, when the data is mostly sorted. How many comparisons do you need to make? Let us consider the situation in which we need to process a stream of integers. Each integer is, at the most, 100 positions away from its correct sorted position. Can you design an algorithm to sort the integers, which uses only a constant amount of storage, independent of the number of integers processed?
10. Given an NxN matrix of integers, where each row is sorted independently, 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 say that the integer does not exist in the matrix?
11. Given two strings “s1” and “s2”, design an algorithm to determine whether s1 is a cyclic rotation of the string s2.
12. You are given a list of points in a two-dimensional Cartesian plane. Each point is represented by its (x, y) coordinates. Find the two points among the N points which are closest to each other. Note that the distance between two points (x1, y1) and (x2, y2) is given by their Euclidean distance sqrt((x2-x1)^2 + (y1- y2)^2).
13. You are given a sentence consisting of a set of words. We would like to reverse this sentence at the word level. For instance, given the sentence, “sun rises in the east”, we would like to get “east the in rises sun”. Can you design an algorithm that runs in O(N) to reverse a given sentence
14. Consider the computer science department of your university. There are N professors who are willing to take on students for projects. There are N new students joining the department who are looking for projects. Each professor has his own ranked list of students, and each student has his own ranked set of professors. Design an algorithm that takes the preferences of the students and professors, and assigns a student to a professor so that all N students are paired with all N professors. The algorithm should not generate any pairs of students (s0, p0) and (s1, p1) such that student s0 prefers professor p1 ahead of professor p0, or professor p1 prefers student s0 ahead of s1. In that case, the current pairing is unstable, in that s0 would try to break out of his current pairing and pick up professor p1. So, too, would professor p1.
15. Consider that you are given a PCB on which there are electrical pins and wires running between the pins. There are N electrical pins and M wires that need to be placed on the PCB. Each wire runs between a pair of electrical pins. There are a set of pins located on the left side of the PCB and another set of pins located on the right side of the PCB. You need to check that all the wires run from left to right. No wire runs between two pins such that both the pins are situated on the left side. Similarly, no wire runs between two pins such that both the pins are situated on the right side. Can you check whether a given placement satisfies this condition? What is the complexity of your approach?

My must-read book for this month

This month’s must-read book is Effective STL by Scott Meyers. This is not a new book, but has been around for many years. However, I never got around to reading it till now, and found that many of my earlier development projects would have benefited if I had read this book earlier.

It gives a good summary of the different STL containers, detailing the choices available to developers. For instance, it discusses the scenarios under which the “vector” container would be a more appropriate choice than the “list” container. It also discusses various STL algorithms, and explains how not to reinvent the wheel.