Google Phone Interview

I had my first Phone Interview for Internship with Google yesterday. I was shortlisted for the Interview by Google, based on my CV and aggregate percentage. I was pleasantly surprised 4 days back when I received a call from Google Bangalore Office informing me of the Interview. So I started preparing for the Technical Phone Interview by revising the fundas of Data Structures, Algorithms and Language subtleties.

I came across a very good resource for coding and programming practice: TopCoder which helped me a lot in getting the fundas right practically.

Finally yesterday evening the phone came, and I was a hell lot nervous. The interviewer was checking my Resume and exclaimed about my Internship Project at NEC HCL (last summer). He asked me about the details of the project, like what enhancements I did and how it helped, which I could very happily explain.....

Then to programming stuff, I was given a problem where I had a large Integer Array and a given sum 'k'. I had to determine whether any two numbers from the Array would add up to k. He gave me various scenarios like the Array is sorted, unsorted and lot of extra storage space or not etc. I used Hash Table for the extra storage space case. I tried using Binary Search method for the In-Place case but could not optimize it for sorted Array, so I asked a teeny weeny bit of Hint and then the "Two Pointers Method" struck. He seemed satisfied with the responses.

I had to write all the above stuff in terms of code and read it out to him, which was pretty exciting :)

Next came another Question, I had a Binary Search Tree, given two nodes, I had to find the Nearest Common Ancestor. It seemed easy and I came up with the solution in just a Minute. He then Twisted the question a bit and generalized the Tree to a General Binary Tree. I asked for availability of parent pointer and he gave me choice. I came up with a recursive O((lg N)^2) algorithm if parent pointer was available. (Just after the Interview, when I was discussing with my Friend, I just got a better optimum O(lg N) algo (See Comments); I better hope these divine thought come during Interviews).
Then as it was obvious, he asked for the general case of no parent pointer. Just few minutes of thinking and a recursive solution was there. (Which I again had to code and read out to him :) ) After his call for optimization, I just applied some Dynamic Programming ideas and Voila!!

So, this was my 1 Hour 13 mins. long Interview which I enjoyed every bit of. Hoping for Selection into Round 2!!!
Now my Mid Sems are just 2 days away and I have not even read a word....So, I better go and start with some DataBases......

Á la procháine, Au Revoir!

Image Data Hiding

Hi!
Many a times, you may be wishing to exchange or share some secret information. When you try encrypting your data, anybody can get suspicious that you are trying to share something secret.
But I have a very cool alternative to that. Why don't you hide all your data in a naive looking Image File and send that to your contact. Send him the required Security code and VIOLA!! he can get back your data as easily as possible....And in this case : Nobody even came to be slightly suspicious that you may be sending even a bit of data......

So, to entertain this fact, I created a C++ Program along with few of my friends Nipun and Mukul that serves this purpose very successfully. (Its Free but not Open Source)!!

Program Executable !

This Concept is very popularly known as Steganography - The art of hiding data in images.....!
Presently the program is in Natal stages and I will keep on updating it as and when we will add a new functionality to the program.

PLAN - We plan to change the platform to JAVA, so that it can be used in Windows platform, which will be very Cool looking rather than the DOS platform. We also plan to port it to Mobiles, so that you can send your precious SMSes using MMS (Seems costly, by think how lovely will it look, if you send an image to your LOVE, hiding "I Love YOU" in it ;) )....

So, Download the executable and check for yourself. But please leave your comments, on how you liked the program and what else you would like to see in it.