interview questions

1. Write a function that computes the N-th fibonacci number.
2. Work in base 7: addition, multiplication, division.
3. You are given a tree as a list of edges, each described as a line "<from> <to>" in the input file. You are also given a set of interesting nodes from the console (cin). Find a common parent of the interesting nodes that is as far as possible from the tree's root.
4. Compare a linked list structure with an array. Example: ArrayList and LinkedList in Java.
5. Implement remove_if
6. Count the number of set bits in a 32b integer. Optimize for time/space.
7. Implement next_permutation.
8. Print the data in a binary tree level by level.
9. Write a function that generates all subsets of a set. Now write a function that generates all subsets for which the product of elements is less than a limit. Optimize for speed.
10. Compare two languages.
11. When should a destructor be virtual in C++? What is a "virtual constructor"?

Nice problem via some Microsoft blog (can't remember which): You are given an array with an even number N of integers. Suffle the array according to the rule A[i] = a[(i%2)(N/2) + i/2], where a[i] and A[i] are the values of the i-th location before and after the shuffle (zero-based index). Do it in O(N logN) time and O(1) space. Example: [0, 1, 2, 3, 4, 5] becomes [0, 3, 1, 4, 2, 5] NOTE: you do not know anything about the values in the array (i.e. 0, 1, 2,... are specific to this example)

This is an online software engineering journal. OO oriented and pretty interesting!

An nice article arguing that source code is the design. It is well written. I agree with the fact that low-level work might reveal problems in the high level design; this should lead to the refactor of the top-level design rather than doing local "hacking". I do not agree that formal proofs are inefficient.

As you might know from an earlier post I am not a fan of literate programming. I think it is a good tool for preparing documents that clearly present an algorithm or a data structure. But that's it. The code for a big (>10000 lines) program is not read like a book. Well, maybe like a reference book but, certainly, not like a literature work. It doesn't feel right to organize it into chapters, sections, paragraphs. However... When writing a public document (like an article, a book, etc.) it is almost required to read the document several times and scan for errors. Errors can be at various abstraction levels: conceptual, presentation style, phrase semantics, syntax, spelling. If the document is large you probably want to do this after finishing each section; and, in the end, once again for the whole document, this time looking for more abstract error types. What occured to me is that the above can be also said about code review sessions. So, although I think that a program's code should be more flexible than a book's format imposes, I do think that using good review practices helps.

This is a short entry about a specific scoping issue. Consider this code: struct A {int a}; struct B {int b;} If A == B there is a name clash. If a == b there is no name clash because a and b have different scopes. Programers are used to ensure A != B but not used to ensure a != b (they even find it strange in other programming languages: see Caml, Vera, etc.). Now consider this code: enum C { c }; enum D { d }; Now both C == D and c == d will cause a name clash. This is why some "coding style solution" is needed. An option is: enum C { C_c }; enum D { D_d }; Another option is: struct C { enum { c }; }; struct D { enum { d }; }; However the name of an enum (C/D) behaves like the name of a struct. It is one of the reasons most coding standards use the same case convention for enum and struct names.

Cloning and smart pointers

Let's suppose we have a hierarchy of classes that provides a "virtual copy constructor":

class A
{
public:
 // This function returns a pointer to a copy of this object
 virtual A* Clone() const;
};

class B : public A
{
public:
 A* Clone() const;
};

// class C : public A
// ...

We would like to let a smart pointer do the memory handling. Obtaining a copy of an object can be done like this:

MySmartPtr<A> a(new A());
MySmartPtr<A> b(a->Clone());

All is nice and clean. But what do you do if you want to call a function f and you want to send it a copy of a and you do not need (locally) a name for this copy?

// void f(MySmartPtr<A> x);
MySmartPtr<A> a(new A());
f(MySmartPtr<A>(a->Clone));

I have written MySmartPtr<A> because the constructor of a smart pointer is usually explicit: you don't want to acquire ownership without explicitly saying so. However the cloning method is a special case. Here you do want to obtain a smart pointer when you say "Clone". What to do?

One solution is to change the Clone methods to return MySmartPtr<A>. This is too intrusive. Classes that have a functionality related to, say, representing accounts or language constructs should not worry about memory handling. Better is to let the smart pointer act as a proxy for the Clone method.

template <typename T>
class MySmartPtr
{
 // ...
public:
 MySmartPtr<T> Clone() const
 {
  if (obj == NULL) return *this;
  else return MySmartPtr<T>(obj->Clone());
 }
};

The result is that you write:

MySmartPtr<A> a;
f(a.Clone());

This can be generalized by using a policy to specify the method by which the clone is obtained. In the code above it is always done by calling a method named "Clone". Again, this is unrealistic: we should not change classes to "fit" to our smart pointer. But I will not discuss this further.

Instead I want to discuss an alternative to the smart pointer member function, namely a friend function. If you have implemented the smart pointer methods in a separate file and you use explicit instantiation as a workaround for the lack of support for export then this solution might be of interest. When Clone is a member function then it is always instantiated and you cannot have smart pointers to classes that do not implement Clone (again, if you do not use policies with static assertions).

The friend function alternative looks like this:

template <typename T> class MySmartPtr;

template <typename T>
MySmartPtr<T> Clone(const MySmartPtr<T>& ptr)
{
 // do the same as in member function
}

template <typename T>
class MySmartPtr
{
public:
 friend MySmartPtr<T> Clone<T>(const MySmartPtr<T>& ptr);
 // ...
}

Now you type:

MySmartPtr<A> a;
f(Clone(a));

I've been very sketchy in this entry but I don't have much time :(