Tuesday, March 29, 2005

Oldboy: Wierd-ass movie

Go watch this oddball movie, if you haven't already. If for no other reason than that you get to see a live octopus eaten. Also, almost randomly, there was an allusion to the 1999 wierdo-cult hit Being John Malkovich: A character mentions his discreet "7.5" floor business, where the anonymity of clients is top-priority. If you have seen BJM, you will recall that the porthole is in an office which is on floor 7.5. I was just wondering if 7.5 is standard nomenclature for discreet businesses, or if this was a deliberate reference to the other movie.

Monday, March 28, 2005

Addendum: More Questions

Random Walk (on-site)

  • Node is an element of a linked list of integers. Define Node, and implement the function:
    Node *addToEnd( Node *list, int val ).
  • In my implementation of addToNode(), I separately handled the case when the list is NULL. I was asked to improve the implementation to merge handling both cases. Hint: Use a Node ** variable.

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?

Book burning, and other noteworthy incidents

The United States is an awfully repressive place at times, especially for a country that is supposedly at the forefront of human advancement and progress. What prompts this particular whining of mine is the news that recently, Lynne Cheney, wife of Vice President Dick "I'm Not Dead, Yet" Cheney, ordered the burning of hundreds of books that supposedly cast some arcane aspect of American history in a bad light. I know, I know, this is old news, but I am still alarmed by Mrs Cheney's actions.

This new-age Savonarola, herself authress of a steamy civil-war era story about a lesbian couple, now out of print, also went on Fox News (that classy beacon of tv journalism, the fair and balanced news network) and proclaimed that the nation's history had to be looked at in a "non-cynical and inspiring light". Sure, forget about concertedly driving an entire native race to near-extinction, and the bondage of another for a hundred years, and there's only the Wizard of Oz left to tell in the (hi)story books.

This is also the country where people think the theory of evolution should not be taught in schools because it might be opposite to some people's fundamental religious beliefs and the theory of creationism. A documentary about volcanoes on Discovery Channel was also put on hold because of the same concerns. Television stations across the country refused to air the movie Saving Private Ryan, fearing indecency fines by the FCC.

We have a President who tries (and succeeds) to score cheap political points by speaking about promoting a "culture of life". This is the same guy who was governor of Texas, where more people are legally put to death every year, than does the rest of the country (This is a rant. I am not checking facts here, but you get the picture).

But these are only a few in a series of disturbing revelations I have come to have about this country. The image of the States as projected to the outside world is the one peddled by Hollow-wood (oops, Hollywood... that was actually a Freudian slip) and television. This is the image of a Godless, hedonistic, morally corrupt society. It wouldn't be a problem for me if this country was simply hedonistic, and morally corrupt. What is, is the fact that it is one of the most conservative of modern societies. A hypocritical, jingoistic majority, that is regularly whipped up by religious fervor of its clergy, where covert propaganda passes for news, and wimpy middle-ground politics is considered radical liberalism.

All the above would still not be a big concern if the country's foreign policy did not reflect its retrograde cultural and religious ideology. Like bestowing democracy on a country whose civilization is approximately five thousand years older than itself. I think below all the ideological and political rhetoric about the rationale for current foreign policy is ignorance and fear. Fear and uncertainty about people who are unlike its own. A people whose very idea of organized society is quite different from the one that is known here.