Monday, December 8, 2008

Top 10 interview questions of 2008

Hi all,


Feel free to add a comment with interesting technical questions that you received in interviews during this year.

At the end of the week i will collect the best ten of them and publish here.Also i would like you to share the company that interviewed you but this is not really necessary.

Due to small number of comments received the top is canceled this year.


Wednesday, December 3, 2008

Cycle detection in linked lists

Find if a linked list has a cycle given a pointer to it's first element.

There are several ways of solving this problem.

  • iterate over the list and insert elements into a hash table. We have a cycle if we insert the same element twice. This solution requires 0(n) time and 0(n) memory.

  • adapt the list to this particular situation. Insert a field that marks the node as visited or not. This solution has the drawback of modifying the list which is not always possible.

  • Floyd algorithm which will be presented below its an efficient and easy to understand algorithm and requires O(n) time and O(1) additional memory.


Also known as the tortoise and hare algorithm it uses two pointers a and b , where a moves two times faster than b.
The pseudocode for the algorithm is as follows:
 
a <- list_head
b <- list_head
do
a <- a.next.next
b <- b.next
while a <> b
//if there is a cycle then a will be equal at some point with b.

An immediate application of Floyd's algorithm is retrieving the element in the middle of a list without computing it's length.

Monday, December 1, 2008

GCC hacks in the Linux kernel

Discover GCC extensions for the C language here.
This article talks about functionality extensions that bring new functionality from GCC and about optimization extensions that are used for generating more efficient code.

One thing that it's easy to remember is using ranges with case statements.
So instead of:
  switch(level){
case 1:
case 2:
case 3: /* do something */
......
default: /* */
}
you can use:
  switch(level){
case 1..3: /* do something */
break;
}