Archive for July, 2007|Monthly archive page

Dismal World

In Photojournalism, Photos on July 26, 2007 at 20:38

Some of the most striking and unforgettable photos. It really throws light on the courage and cruelty of the human soul.



Your potential. Our passion.

In Interview, Microsoft, Placement on July 24, 2007 at 15:40

I am now placed at Microsoft, IDC.

As part of the ongoing campus placement program in our college, Microsoft recently came hunting for CS/IT students for its’ Development Center in Hyderabad. The process ran its course over Wednesday and Thursday this week. The pre-placement talk was held Wednesday afternoon, and the final results were announced almost exactly 24 hours later. The process consisted of two written rounds, and three rounds of personal interview. I am reproducing the questions I was asked below.

Written Round 1

1. Find the median of a Binary Search Tree. You are passed the root of the tree, and you should return the median which is the middle element, if the number of elements is odd, or the average of the two middle elements if the number of elements is even.

2. Write a function to check if the two passed strings are anagrams of each other.

3. We want to implement the functions allocstring, freestring, concatestring, and stringlength. We need to optimize the functions in this order : stringlength, allocstring, freestring, concatestring, with stringlength requiring the most optimizations. We are also given that the memory consists of a buffer of fixed size. We have to design and describe a data structure which would enable the above operations to be performed in an efficient manner.

Written Round 2

In this round, we were taken to a room, and each student was assigned a supervisor. The question would be written on the board, and we must write “tight” code to solve the given problem. Before writing the code however, we had to describe our algorithm to our supervisor, and convince them that our algorithm is correct and would work. Tight codes basically means that we had to check all the boundary conditions of our algorithms, and make sure that no test case crashes our program.

1. Implement the function bool isRegex(char *reg, char *string); This function is passed two strings : a regular expression, consisting of the [a-z] and the * and ? characters. We had to check if the string matched the supplied regular expression. For example, if reg is a*b, and string is acbcb, we should return true. And if reg is a?b and string is accb, we return false.

2. Implement the function : node * add(node *l1, node *l2). The lists L1 and L2 are linked lists where each node of the linked list contains a single hexadecimal digit, represented as a char. The whole list thus represents a hexadecimal number. We had to add the two hex numbers represented in l1 and l2, and return the head of the linked list representing the answer.

Personal Interview 1

1. Given an array consisting of only 0s and 1s, sort it. He was looking for highly optimized algos.

2. Given that an array consists of only 0s, 1s, and 2s, sort it. Again, only very efficient code was accepted. Good old counting sort was sneered at. He wanted an algo to do this in one pass of the algorithm without using any extra space, and which performed the minimum number of manipulations of the array.

Personal Interview 2

1. Implement a Queue using a Stack ADT. He told me to write “tight” code for this as well. He wanted optimized methods for this, and asked me to enumerate different ways of optimizing this data structure, and to analyze each one. After I did that, he asked me whether my code would handle multiple simultaneous access to the data structure, and asked to handle that case as well.

2. You are given a binary tree where each node consists of a left pointer, a right pointer, and a sibling pointer. The left and right pointers are initially populated and the tree is a normal binary tree. He wanted a function to populate the sibling pointers such that they point to the node to the right of the current node in the tree, and which is on the same level. If there is no such node, the sibling pointer must be set to NULL. He again wanted an optimized solution, optimized for space.

Personal Interview 3

This guy was a through and through OS guy I think.

1. What is a process.

2. How is it different from a thread.

3. How is common data shared between threads.

4. Semaphores and other locking mechanisms.

5. Code for some of the locking mechanisms.

6. Design a data structure which will support the following operation : given a seven letter word, return all valid words which are anagrams of this word. He wanted a data structure which would be optimized for space, and another one optimized for time.

7. Write the code to implement the aforementioned function given the data structure.

8. How does malloc work?

9. How is heap space managed in a C/C++ environment.

10. Explain paging.

A bunch of other OS related questions.

Bored with your Windows Theme?

In Apple on July 3, 2007 at 17:09

This guy here tells you how to make plain old Windows look like Ubuntu which seems a bit pointless because 1)Ubuntu’s default theme sucks, and 2) you could just install Ubuntu instead.

Now, if you wanted to make Windows look like Mac OS X, thats a noble goal. First, OS X looks amazing (no, really), and second, you can’t install it on anything other than Apple hardware.

I’ve done this with my Windows (erm…yes…I use Windows, but more about that in another post). Check out how it looks here. I used a couple of msstyles to achieve this look,namely, OS X Tiger (imaginative name, I know) and SS4. A simple Google search will yield these styles. Next, copy the file into the C:\Windows\Resources\Themes\ directory, where C: is the partition on which Windows is installed. Next go to Control Panel -> Display -> Appearance and select the style you downloaded in the Windows and Buttons drop down menu, and, viola. Mac OS X on your computer!

Post your own screenshots in the comments, or recommend any other style that you like.

Wow, its big

In Uncategorized on July 3, 2007 at 00:39

The IceCube Neutrino Detector is embedded in two and a half kilometers of ice in Antarctica. Surely that can’t be good for global warming?


In General on July 2, 2007 at 23:58

iWant an iPhone.

*Sigh*. Maybe after I start earning.

Internship at Sun

In internship, java, sun on July 2, 2007 at 16:51

I recently wound up an internship at Sun Microsystems. It was a couple of months long, and I worked on many things including databases and data mashups. It involved writing Java code to fetch data from various sources and dump it into a central database. The project was open source, so the code should be publicly available somewhere.

A couple of pictures of Sun Microsystems are up here.