- Xorcism of Conventions -

My Google Interview - Part One!!!

2011-01-23T07:42:00.001Z

It's been a while that I have been thinking to write about this amazing experience, an opportunity to have a splendid interview with the 'Angelina Jolie' of Software Companies, Google. 'nother one to add to the list of interesting adventures, life obliges me to go through. Though I was not able to reach the destination, the journey was challenging enough!

I have been lucky enough to have encountered quite a number of good technical interviews, from both sides, as interviewee and interviewer. This experience changed my perspective of how an interview should be taken (hopefully, I will get the chance to apply this sometime in the future).

And now, onto the interview. Being over the phone, I was terrified. And writing runnable code on Google Docs while answering questions over the phone did not help at all. To be frank, I hate phone interviews. Physically seeing the interviewer in front of you eases up the process a lot. But I understand that they are unavoidable in the case of big companies, who receive so many CV's and sifting through the lot is difficult.

Enough said; I will get into the actual questions now. So I got the call from Bjorn, a software engineer at Google. He asked me the programming language in which I would like to write the code and I replied C++. I was asked three questions in a time span of around 75 minutes and they progressively became harder and harder. I was also asked to describe the time complexities for all the solutions I had suggested for these questions. I will try to describe the conversation as far as I can remember. These are my answers and if they seem wrong to you, please feel free to comment so.

Question 1) For a lottery of 90 numbers, how can I get 5 non-duplicate random numbers?

Me > Use a random function to retrieve characters
He > What about duplicates
Me > Put the seed in the random function as the previously retrieved number
He > No, changing the seed won't guarantee non-duplicates
Me > In that case, we can add the elements to a set and stop when the size is 5

Question 2) For an ASCII string, find the most repeating character?

Me > Create an integer array of size 128 to store ASCII values...we traverse the string once and increment the count for each character...
He > Consider that instead of ASCII, it's Unicode and the string is very short
Me > We can use a dictionary, so that each character is the key and so only those that are present have to be stored...
He > What if it's Unicode and the string is very very large, lying on different clusters...
Me > Use a distributed hash table for storing...split the string into different sets and calculate the counts and then combine the results
He > Then since it's Unicode, there is a chance that 65536 keys and values have to be sent across the network...
Me > Since we are sending only the count, it should be ok
He > What if we sent only the max count character from each machine...would that work...
Me > No, that would not work, as there can be characters low in number, but when combined could be the max...
He > So, what would you do...
Me > We could calculate a subset of the top counts to be sent across and so the probability of getting the top one would be high...
He > Yeah ok, deciding on such a subset would be a difficult task to do...so lets move on...

Phone disconnects...

Question 3) For a calendar, with start time and end time and 'n' appointments , how would I find the conflicting appointments?

Me > Crude solution...compare each appointment with each other...
He > Ok...so how to improve
Me > We can sort the list based on endtime so that all the adjacent appointments will be close together...
He > endtime or startime?
Phone disconnects....
Me > Both can be used
He > Could you write the code
Me > Ok...
Me > Ok, so then after sorting them, we could take an appointment, mark all the ones that have starttime within the starttime+1 hour...
He > Now, we don't have enough time..so could you tell me the complexities...
Me > I told for the sorting, it would be n log n and the comparison can go upto n^2...
He > n^2, in which case?
Me > If the appointments are different
He > Ok, then, so we are out of time...the recruiter will contact you with the feedback...

He then asked me whether I have something to ask him, which I did. We discussed about that for a while and then he hung up. So that was it. I definitely could have done better. I prepared for the wrong type of questions, based on my previous experiences. I did not know whether I had done well or not as there is a big difference being 'Good' and 'Google good' and it seemed to me that I hadn't done so. Nevertheless, it was the best interview of my life till that time.

But, the next day I got a mail from Google that made me EXTREMELY happy. It said ‘Congratulations!’ as they got the feedback from Bjorn and I can move on to the next round. And so that concludes my first Google interview. I will write about my next one which was the best interview of my life till date.

Angsana Resort

2010-04-30T19:22:00.000+01:00

First three pics courtesy of Divya and My Lumy...
Me, swimming and playing water polo at the time...did the processing though... :-)

Taco Bell at Mantri Mall...

2010-04-04T15:06:00.000+01:00

Apples Done...now Oranges

2010-04-04T14:38:00.000+01:00

The Hayaboosa!!!

2010-03-28T17:58:00.000+01:00

Our fearless companion... the fastest ride in Bangalore... The Hayaboosa!!!

The Great Vidhana Soudha

2010-03-27T20:35:00.000Z

Me & My Lumy...;) @ The Lalit Ashok

2010-03-27T20:00:00.000Z

Oracle(Sun) Tech Days 2010

2010-03-27T19:37:00.000Z

My first developer conference held at The Lalit Ashok, Bangalore...

Pehla Picture...

2010-03-27T19:20:00.000Z

My Panasonic Lumix DMZ-F35 !!!

2010-03-27T19:17:00.001Z

Yeah, I know... It's awesome... :)

A Walkthrough of My Surgery

2010-02-19T16:06:00.000Z

DISCLAIMER...Everything here is absolutely true..Read at your OWN risk...

Feb 9th 2010 - It begins...

8.30 am - In my suite -
A guy comes with a shaving set and says he wants to do "preparation"..That's what they call it...I started to lie on my stomach but then he told no it's to be
completely from the navel till the knees..
Ok fine.. So for the first time in my life, i am lying in my birth
suit in front of another person.. That too.. A guy..well what to do..
:-)

10.30 am - In my suite -
nurse comes in and gives me a gown that is completely open in the back
with only some strings.. Something similiar to what Shreya wore in
Shivaji..

11.00 am - In the pre-op room -
i am lying there in the gown and they tell me the surgery will be only
in the afternoon.. So a beautiful nurse comes by and asks me
questions.. And then she asks if "preparation" is done.. I say yes..
Does she believe me..Of course not.. She lifts up my gown and sees for
herself..After some time two nurses comes and repeat the entire
procedure.. I told them too i am prepared.. But they want to see for
themselves.. Ok fine.. What do i care.. :-)

3.30 pm - In the operation theatre -
there are six people.. One guy and 5 gals.. So the senior doc asks me
should they give me a general anesthetic or a spinal one.. I
remembered a dialogue from "House"( for those who don't know House is
a medical serial) and i said do what you think is best for me in the
current situation.. They said spinal.. I also thought if i am awake i
can see what is happening..
for the spinal they have to give an injection in the spinal cord.. I
was bent on my side and they tried to inject.. But it kept striking
the bone.. It was so painful.. After 13 injections on the 14 try they
got through to the spinal cord..
I was paralysed from waist down.. I could just feel the touching..
They then removed the cloth completely.. So i was lying stark naked in
front of 6 people.. They asked me where is the problem.. I told them
it's in the coccyx region..I was talkin with them asking doubts about
various machines and procedures.. Actually due to my guestions a nurse
had asked me whether i am working as a nurse.:-) ..Then the main
surgeon came and started hacking away..i was awake the whole time.. It
was awesome..

5.00 pm - In the post-op room -
here nothing much happened.. I kept trying to move my legs.. I could
feel them moving.. But when i look down they are not moving.. I was
then asked to pee in a bottle.. I then slept peacefully..

Feb 10th 2010 - the next day...

10.00 - In my suite -
i was brought back safely... :-)

That's all folks.. It seems that by pain endurance levels have
increased tremendously.. Probably due to watching all parts of SAW
:-) ..

Thank u for your kind attention...

The Looking Glass

2010-01-22T20:02:00.000Z

Unabridged... Might be a tad explicit for some!!!

Getting a man to love you is easy
Only be honest about your wants as
Woman. Stand nude before the glass with him
So that he sees himself the stronger one
And believes it so, and you so much more
Softer, younger, lovelier. Admit your
Admiration. Notice the perfection
Of his limbs, his eyes reddening under
The shower, the shy walk across the bathroom floor,
Dropping towels, and the jerky way he
Urinates. All the fond details that make
Him male and your only man. Gift him all,
Gift him what makes you woman, the scent of
Long hair, the musk of sweat between the breasts,
The warm shock of menstrual blood, and all your
Endless female hungers. Oh yes, getting
A man to love is easy, but living
Without him afterwards may have to be
Faced. A living without life when you move
Around, meeting strangers, with your eyes that
Gave up their search, with ears that hear only
His last voice calling out your name and your
Body which once under his touch had gleamed
Like burnished brass, now drab and destitute.

- Kamala Surayya / Madhavikutty