Thursday, March 24, 2005

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:


    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?

1 comment:

Anonymous said...

Which company did you join finally?