Technical interview questions

Here's a list of questions I was asked over the last two months, in the course of my job search. No solutions, nor a comment on the quality of questions, will be provided. So, don't bother asking.

Microsoft (on campus):

• Reverse a linked list.
  
• Given an array (positive and negative integers), find the contiguous subarray with the maximum sum.
  
• Implement:
  

  void *aligned_malloc( size_t size_in_bytes, int align );
  void *aligned_free( void *ptr_returned_by_aligned_malloc );

  
  aligned_malloc() is like malloc(), but takes an additional argument - align. If p is the pointer returned by aligned_malloc, then, ( p % align == 0 ).
  
• Find the minimum number of colors required to color a dodecahedron. Now, write an algorithm that does so.
  

NetApp (phone screen):

• When would you prefer hashing as your dictionary implementation?
  
• What is secondary hashing?
  
• Perfect hashing/universal hashing...
  
• How is the open() system call implemented in UNIX?
  
• The rest, I don't remember (its all a haze).
  

Caliber Consulting (phone):

• Given the function:
  

  
  void swap( char *p1, char *p2 ) {
    char *tmp;
    tmp = p1;
    p1 = p2;
    p2 = tmp;
  }
  

  
  what is the output of the following code:
  

  
  #include 
  
  int main() {
    char *s1 = "hello";
    char *s2 = "world";
    swap( s1, s2 );
    printf( "%s, %s\n", s1, s2 );
    return 0;
  }
  

  
  
• Implement strlen(), strcat()...
  
• What is the complexity of strcat() ?
  
• How would you change strcat(), given the following scenario:
  

  
  char src[VERYBIGNUMBER];  /* NULL initially */
  char *s1, *s2, ..., *sn;
  

  
  You need to place the strings s1, s2,..., sn into src using strcat(). Assume that src can accomodate all these strings. Note that normally, a single execution of strcat() takes O(l + m), where the lengths of the two strings are l and m. With that complexity, the above cascade of strcat()'s takes time proportional to:
  
  n*strlen(s1) + (n - 1) * strlen(s2) + ... + strlen(sn).
  
  Can you change the complexity to:
  
  strlen(s1) + strlen(s2) + ... + strlen(sn) ?
  
  
• Given that you had only upto the IP stack implemented on two machines. How would you go about establishing a session between them? Note - you obviously can't just use TCP! Also, no error correction, sequencing etc. are required, so you don't *need* to use TCP.
  
• With the same scenario as in the previous question, how would you implement a messaging client?
  
• What are virtual functions in C++?
  
• How would you implement virtual functions in a compiler?
  

Random Walk (pre-interview - on campus):

• Implement the factorial function.
  
• What is polymorphism?
  
• What are virtual functions?
  
• Talk about inner classes in Java.
  
• Difference between a button and a JButton
  
• 57 cents worth of money in 7 coins. How many of each do I have: 1c, 5c, 10c, 25c ?
  

Neuco (phone screen)

• What are virtual functions in C++?
  
• How does a typical C++ compiler implement virtual functions?
  
• How would you reproduce/simulate the object system of C++ in C?
  
• Given a C++ object and its method, how would you simulate with a C function, the calling of the C++ method?
  
• Suppose you are given a pointer to a function that takes a double between 0 and 1, and returns a double between 0 and 1. The function is continuous, and is zero at some point(s) in the interval. Write a procedure to find those zero-points. What is the complexity of the function, as a function of (a) precision, (b) accuracy ?
  

Random Walk (phone interview)

• What is the difference between the procedural and the object oriented approaches to programming?
  
• Elucidate the cornerstones of OOP.
  
• Suppose you had a Shape class. Its an abstract class that subclasses into concrete classes like a Point, Triangle, Square etc. How would you handle render()'ing a Shape instance...?
  
• Suppose an application program wants to render birds on the screen. Different birds are to have different functionalities (Ducks can quack(), Crows can fly() etc). Suggest a good design pattern to provide these functionalities to different instances, that repsects the paradigms: cohesion and loose coupling.
  
• What is the most prominent characteristic about multi-threaded programming? And why does multi-threaded prog have this characteristic?