Thursday, January 31, 2008

Remembering names of Indian states

If someone asked us, how many states is India divided into ? Probably most of us won't be able to answer that. Even worse, what if we are asked to enumerate them.

Here is a simple way to remember all the states:

Btw, India is divided into 28 states and six union territories (Andaman-Nicobar, Daman-Diu, Chandigarh, Delhi, Dadara-Nagar Haveli, Lakshadeep and Pondicherry)

I have 3 mnemonics (Also see mnemonic for Periodic table)

(Ignore vowels)
1. JK par game kar ke Tao West Bengal gaye
(Jammu Kashmir, Punjab Rajasthan, Gujarat Maharashtra, Karnataka Kerala, Tamil Nadu Andra Pradesh Orissa, West Bengal)

Goa is below Maharashtra :)

2. HP hara MAC jhab UP UK gaye
(Himachal Pradesh, Harayana, Madhya Pradesh Chattisgarh, Jharkhand Bihar,Uttar Pradesh, UttarKhand)

Sikkim separates 1,2 from 3

3. Arun & Megha Assam trip mi nagmani ko dekha
(Arunachal Pradesh, Meghalaya, Tripura, Mizoram, Nagaland Manipur)

Tuesday, January 22, 2008

Computer Problem Solving

I found this interesting pic about "How to be Computer Genius". Funny and sarcastic :)

Sunday, January 13, 2008

Microsoft Interview

I had an interview for internship at Microsoft. I was interviewed by SQL Server Analysis Services and SQL Server Reporting Services (I got offer from both :) ).

I was briefed by my recruitment coordinator at building 19. I had my interviews in building 34 and 35.

My interview questions were pretty easy. Here are some of them:
1. Write a program to create a balanced binary tree from a sorted array of integer.
>> Find the middle element. Make it root. recursively call the function for left and right subarray with root->left and root->right respectively.

2. Write a program to find angle between clock's minute and hour hand
>> assert(h >= 0 && m >=0)
return ( abs( 0.5*((h%12)*60 + m%60) - 6*(m%60)));

3. Consider there are 2 types of characters:
1byte character - has value less than 128
2 byte character - whose first byte has value >= 128
Given a random pointer in a byte array find the previous character

I was asked to solve the simpler version of the problem: i.e I was given the pointer to beginning of array.
>> Start from beginning of array till pointer (also keep track of prev character), if value <> 1 byte character. Goto next byte.
If value >= 128, => 2 byte character, move 2 bytes.

Lets assume if I was not given the begin pointer:
>> Assuming turing tape: the problem has atleast 1 non halting solution. Consider, tape filled with 128. :)

4. Given a string, reverse first n characters in each word of the string.
Eg: if string is "abcd ef"
and n =2 => o/p: "badc fe"
and if n =3 => o/p: "cbad ef" (if less than n characters, donot reverse)

5. Some probability based questions: 3 types of ball in bag with equal probability. Some of the atleast, atmax kind of questions. I am sure almost everyone has solved these type of questions in their undergrad.

6. Problem with Concurrent Reader, Exclusive Writer (CREW):
A writer may wait forever.
How to solve it?
Assign reader_priority = writer_priority = normal
When number of readers exceeds a threshold, --reader_priority
When writer writes and if reader_priority < normal, ++reader_priority

If reader_priority < norm, and if a reader comes, it will wait if there is writer waiting in the queue.

My suggestions:
Be confident. Revise Data Structures and Algorithms. Write few programs for practice.
Also talk to interviewer, clarify assumptions and state your algorithm before starting to write on the white board. Always check for boundary conditions (this is where most candidates get filtered).