Prepare IT Interviews

Question:  In a country where everyone wants a boy, each family continues having babies till they have a boy. After some time, what is the proportion of boys to girls in the country? (Assuming probability of having a boy or a girl is the same) Answer:  This is a very simple probability question in a software interview. This question might be a little old to be ever asked again but it is a good warm up. Assume there are C number of couples so there would be C boys. The number of girls can be calculated by the following method. Number of girls = 0*(Probability of 0 girls) + 1*(Probability of 1 girl) + 2*(Probability of 2 girls) + … Number of girls = 0*(C*1/2) + 1*(C*1/2*1/2) + 2*(C*1/2*1/2*1/2) + … Number of girls = 0 + C/4 + 2*C/8 + 3*C/16 + … Number of girls = C (using mathematical formulas; it becomes apparent if you just sum up the first 4-5 terms) The proportion of boys to girls is  1 : 1 .

Question:  You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer:  Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it? Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time. When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random functio...

Question:  Three ants are sitting at the three corners of an equilateral triangle. Each ant starts randomly picks a direction and starts to move along the edge of the triangle. What is the probability that none of the ants collide? Answer:  So let’s think this through. The ants can only avoid a collision if they all decide to move in the same direction (either clockwise or anti-clockwise). If the ants do not pick the same direction, there will definitely be a collision. Each ant has the option to either move clockwise or anti-clockwise. There is a one in two chance that an ant decides to pick a particular direction. Using simple probability calculations, we can determine the probability of no collision. P(No collision) = P(All ants go in a clockwise direction) + P( All ants go in an anti-clockwise direction) = 0.5 * 0.5 * 0.5 + 0.5 * 0.5 * 0.5 =  0.25

Question:  Is your machine little or big endian? Answer:  Let first take a look at the solution before we discuss about it. int isLittleEndian( void ) { unsigned int temp = 0x12345678; char * tempAddress = &temp; if( *tempAddress == 0x12 ) { return 0; // Indicating False } else { return 1; // Indicating True } } To answer this, you have to obviously know what little and big endian are. Also you need some basic understanding of variable assignments for data types of varying sizes. A major mistake which you could make is with the temp variable. When I was asked this question, I answered it by taking a fixed address for temp which is insanely dangerous (I know I was dumb). The address could have been used for something else or even been a reserved address for all you know. By creating a local variable, temp will be placed on the stack so we don’t have to worry about whether it will be safe or not.

Question:  How would you find a loop in a singly-linked list? Answer:  This is a very typical tech interview question that has a very elegant solution that runs in O(n) time and O(1) space. Also referred to as the “Tortoise and Hare Algorithm”,  the solution uses a fast pointer (traversing the list two items at a time) and a slow pointer (traversing the list one item at a time). If there is a loop, then the fast pointer will go around the loop twice as fast as the slow pointer. At one point, these two pointers will point to the same item. Here’s some code to make this clearer. bool hasLoop( Node *startNode ) { Node *slowNode, *fastNode; slowNode = fastNode = startNode; while( slowNode && fastNode && fastNode->next ) { if( slowNode == fastNode->next || slowNode == fastNode->next->next ) { return true; } slowNode = slowNode->next; fastNode = fastNode->next->next; ...

Question:  Reverse a Linked-list. Write code in C. Answer:  There are multiple ways to go about this. Let’s first look at a recursive solution. Node * reverse( Node * ptr , Node * previous) { Node * temp; if(ptr->next == NULL) { ptr->next = previous; return ptr; } else { temp = reverse(ptr->next, ptr); ptr->next = previous; return temp; } } reversedHead = reverse(head, NULL); Now for a non-recursive solution. Node * reverse( Node * ptr ) { Node * temp; Node * previous = NULL; while(ptr != NULL) { temp = ptr->next; ptr->next = previous; previous = ptr; ptr = temp; } return previous; } I personally prefer the non-recursive solution but it is always good to know both of them.

Question:  You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C. Answer:  To delete a node, you have to redirect the next pointer of the previous node to point to the next node instead of the current one. Since we don’t have a pointer to the previous node, we can’t redirect its next pointer. So what do we do? We can easily get away by moving the data from the next node into the current node and then deleting the next node.  This solution has O(1) runtime. Here’s some code to illustrate this simple logic. void deleteNode( Node * node ) { Node * temp = node->next; node->data = node->next->data; node->next = temp->next; free(temp); } Some things to consider. This method could pose potential problems. For instance, let’s consider we have a linked list A -> B -> C -> D and we are given a pointer to B to delete it. Theoretical...