Google Zurich Interview Experience

TDLR: If you are interviewing for Google, please add C++ STL or Java core library to your preparation material.

I have been rejected by Google on April 5th for the second time in my life. This time I was very positive about the interview, which made it hurt even more when I saw the mail from the recruiter. Anyway going back to the beginning, just like most engineers I applied to Google multiple times and on February 16th 2016, I received a mail from a recruiter at Google Zurich asking if I would be interested in the position "Software Engineer" and if we could have a small chat on 18th. I replied as soon as I can saying that 18th sounds perfect. This wasn't an interview and he just told me about the interview procedure and asked me for couple of time slots for the phone interview. I decided for 29th February as it would give me enough time to prepare.

On 29th I got a hangout call at exactly 3pm and the interviewer introduced himself. He pronounced my name correctly and said the generally people in US say veejay instead of vijay, which is true! We went through only one question and it was little tricky, but not hard. I asked him questions before jumping into the solutions. After that we had around 5 minutes left and I asked him about Zurich in general and projects in Google Zurich.

Although I was very positive about the interview, I was tensed if I would get a call back or not. On March 2nd, I received a mail from the recruiter for an onsite interview at Google Zurich. I was very excited and fixed 30th March, so that I can prepare well again. After that I received required documents for the visa process and it took almost 3 weeks for my visa to arrive. Arrangements from Google HR were super quick. They arranged my flight to Zurich from Mumbai on 29th March and stay in Zurich on 29th and 30th March.

Finally on 29th March, I reached Zurich and checked into the hotel well before the check-in time. The hotel staff were really helpful and hotel room itself was very cozy. The best thing about the hotel was that it was 50 steps from Google Zurich office. I went to a restaurant in the evening for dinner and rested well that night. On 30th, I reached Google 10 minutes before and entered my recruiter's name in the visitor machine along with my details. He came down with in 5 minutes with my visitor's tag and escorted me to the interview room shortly. I had a bit of coffee to get rid of any lethargy before the long day of stressful interviews.

First interviewer arrived soon and after 5 minutes of explaining me about the interview process we got into the first question. The question was very easy and after answering with an algorithm, he modified the question slightly to make it hard and after few moments I changed my algorithm to work the new constraints. He again modified and the problem became tricky. Within few minutes, I suggested an algorithm with which he seemed happy. He asked me to code for the very first question and I implemented the algorithm in few minutes. We were left with little time and he asked me if I had any questions for him. I asked about his work and Zurich. Before he can finish answering, second interviewer was ready.

Second interviewer started with a well known question regarding Fibonacci numbers, slightly modified. I quickly understood the trap and instead of going with matrix multiplication, I went with pre-computation which made the complexity O(1). He looked satisfied and asked me to code. This is where I made my first mistake. I needed an array with dynamic length, without zero initialization. So instead of new int[n](), I wrote new int(n). I realized that mistake later in the evening, but thought it was too minor. After the coding it was time for questions and I asked him if there is any improvement we can make. He said that other than small improvements like using a constant length array, the code looked good. Then I asked him about his projects and YouTube, which he works on.

Third interview was open ended and was about performance improvement and debugging code. We started with a very basic algorithm problem and after coding the solution, the discussion continued towards performance in general. For performance optimization, I told the interviewer that I will look at high level algorithm followed by a profiling to check disk seeks, cache misses, buggy code and others like locking issues. Again it was the questions time and I was actually running out of them. I asked if it is easy to switch between projects and how often people do that. She told me that it is not often, but people do switch between projects and sometimes without any experience in the new field.

After that I had lunch with another Software Engineer and he showed me around. I loved the place, specially the lounge on the top floor, which has a beautiful view of the Alps! We talked about Zurich and trekking in Switzerland. As I had an extra day in Zurich, He suggested a near by place called Uetliberg. I actually went there the next day and the route and the view from the top were beautiful. After lunch we came back to a new room, where my next interviews were scheduled. We were waiting for the next interviewer and since I knew that the next round was system design, I was already nervous and was reading from my notes.

Next interviewer showed up at the exact scheduled time and within a minute, he was done with the introduction and gave me a design question. The question was designing a single system for a task rather than a network. After asking relevant questions about cache and storage capacity, I started off with a mathematical error while computing the bandwidth needed. After that we moved on to the main problem and while designing it, I was stuck twice and he gave some clues. We were in the middle of it, when the next interviewer showed up. Previous interviewer wished me luck and I am still unsure how it went.

Fifth Interview was again an algorithm centric one and the question wasn't hard. Although I took around 5-10 minutes after he modified the question the second time, I solved it in time and he looked happy. Then the horror followed. I designed a BST of strings with an integer attached each string. I wrote dummy functions like search and insert and told him that I can implement them if he wants. After I am done with coding, he went through my resume and asked me if I ever worked with STL. I told him that I only used that for coding competitions and that I recently moved to C++ even for those competitions. He told me that I dont need to implement BST and the whole thing can be implemented with a class in STL and asked me if I know which one. I took a minute and answered map. He said okay and asked me if I have any questions. I didn't think much of this and asked him some questions related to maps and connection between Google and Acedemia.

The last interviewer escorted me to the front door as per their protocol and wished me luck. I was very happy that I answered all the algorithmic questions and I read it somewhere that Google generally hires if 4/5 engineers say yes. So I thought a negative review on System Design round would be fine as others went really well. After spending one more day in Zurich walking around the city and hiking across Uetliberg, I returned to Mumbai on 2nd April.

Within 5 days after the interview, I received the mail from the recruiter saying that they will not be proceeding further with my application. The reason given was "As to the rationale, although your knowledge of Algorithms and Data Structure was really good, the panel thought there was still room for improvement in your coding abilities". Despite being sad that I missed the golden opportunity once again, I am little more confident about my problem solving skills. Although I am little ashamed to admit, I have never worked on a C++ project and I always used cplusplus.com for STL classes and their functions in coding competitions. At my work I use embedded C entirely and C for linux drivers. My other projects are web based and I use PHP, SQL, HTML and JS.

Overall, I really enjoyed the whole experience, thanks to the recruiter, HR and the Engineers. I hope to go back someday and claim my space at Google Zurich :)

PS: I did not discover anything here. My recruiter sent me a list of things I should work on and I prepared for everything but STL. Do not make that mistake. Good luck :)

The Banach–Tarski Paradox

This post is the sum of the thoughts I had watching this great video.

Although it seems very convincing, you cannot divide infinity. When you take an object as infinite set of points(and lines connecting them to the centre), you can always divide into two, or any finite number, and say each one has infinite points again and thus it is same as the original.

In short, Banach–Tarski Paradox is the physical version of the following argument. On a number line, number of real numbers between 0 and 1(uncountably infinite, just like the points on the sphere) is equal to real numbers between 0 and 2. But this doesn't prove that 1 = 2. Similarly just because you ended up with same number of, 'infinite', points you cannot make the conclusion that you have the whole object.

But are we sure that 1 is indeed not equal to 2? Actually you can say, mathematically, it is plausible and we cannot prove it one way or the another. You can argue that 1 is clearly not equal to 2 because by definition they are different, but as stated before, one can argue that since there are equal number of rational/real numbers between 0 and 1 and between 0 to 2, 1 and 2 are actually equal. Well, at least the physical world seems to contradict this as we cannot make two objects from one object.

One explanation for this phenomenon can be that the world we live in is not continuous and if we were to draw xyz axes in the real world, we know the number next to zero to be planck's length. So there is an upper limit to the number of points on any plane of a finite area and thus there are no infinite number of points on the surface of the sphere(or any physical object) and you cannot make the assumption, at 16:34, that the number of elements in the sets after rotating right would be equal to original number of points(they would be one fourth).

So, if there is a universe, which is continuous, it is plausible that we could make two objects from nothing but one. To sum it up, the proof that Banach-Tarski Paradox doesn't hold true is that Banach-Tarski Paradox doesn't hold true. Quite a paradox!

Motorcycle Diaries

Recently I toured Sikkim alone on a motorcycle and North East India using public transportation. There is nothing like being on a bike with your knees feeling the breeze and you owning the ride and the road. I think that is as close as we can get to being truly free!
Following is the journal I kept through the first half of my journey(pics).

day 4
I reached Siliguri in the early morning around 6, right on time, but only to wait for the stupid taxi to get loaded with people which left for Darjeeling only by 7. It was almost 11 when we reached Darjeeling and the town gave me the best welcome I could wish for the trip. Even those movies didn't do justice to the beautiful town and I was, like every one else, in love with it. Even the way to the town was splendid on that cold and sunny day with lots of ghat roads and tea estates all around.
I met gautam at 11:30 and after all the paperwork it was already 2:30 when I got my hands on the machine, made like a gun, BULLET CLASSIC 500.
I had mixed feelings when I started the ride. On one hand, I enjoyed the power at my hands and on the other, I was scared. It was the first time I was going to be alone. Not traveling alone, but being alone for 5 days in an unknown land and I was little afraid of what's to come.
It took little time to get used to the power of the bike as I never rode a heavy motorcycle before.
It was a rocky road to Jorethang and I almost lost control at one place and rear tyre slipped at another, but still I enjoyed the ride. I reached Jorethang around 5:30 and it was dark already. There was no power in the town when I rode in. I got myself a small room for 250 bucks, came out for a walk after settling in and I couldn't see a damn thing.It was as dark as dark gets! Luckily within 5 min whole town lighted up.But still I felt little shaky that night and tried to keep myself busy unpacking stuff and browsing web.As I didn't get any sleep on the train last night and got so tired from the ride, I slept at around 9.Actually it was after ages, I slept before 11.


day 5
Woke up around 8 in the morning and it was sunny, but still cold. The breeze somehow made everything clear. Long sleep helped me rejuvenate my senses and I was looking forward to the ride so badly. I skipped the shower as it was cold already and started the ride by 9. The ride was a bliss with the breeze and the power of a bullet on a curvy ghat roads. Sikkim roads were better than any other ghat roads I have seen and I think that is one of the reasons why Sikkim is one of the best destinations in India for the heavy bikers. On the way to Namchi, luggage bag almost fell down due to loose ropes at one place. I quickly stopped the bike and removed all the ropes to tie it properly again. Once I started again, I couldn't help myself thinking what could've happened if the bag snapped and I made a point to take more time if required to set little things right. I reached Namchi at around 10:30 and went straight uphill to chardham(siddeshwar dham). As I skipped the shower in the morning, I wanted to take a room just for the shower and there was only 1 hotel on the hill with 2200/day and no hour basis. The only options were entering the dham without a shower or going back to Namchi, 7 kms.
So as I entered Namchi, luckily I saw a sikkim tourism help desk.I went straight to the officer sitting there and explained. He there dialed some one and talked for about 2 min before telling me to follow a guy. I thanked him and followed the guy to the guest room. it was a big room with all the furniture and the only thing I was thinking was what the rent could be. I took shower and tied the luggage properly this time. Gave a 50(that's it, no rent) to the attender there and left merrily.
Chardham is on the top of a hill with a huge idol of Shiva surrounded by small temples with idols from four dhams. The grandeur of the place cannot be described in words. Even after staying there for 3 hours I felt like less. Once I was done taking pictures of the place, I grabbed some food and left for Samdruptse. It was around 8km from Namchi. Even that place was profounding. I met some a couple from Europe there, who actually hired the bike from same guy, Gautam. After exchanging info about our trips and routes,I started for PELLING, the place to view Kangchenjunga from! Road was pretty bad and perhaps the worst in the whole trip and It became pretty dark quickly on the way.
That day I had to break the one rule I had before starting the trip, NEVER RIDE IN THE DARK.
I reached Pelling by 8:30 and it was freezing, I think it was the coldest place I have ever been to.
In Pune no one dares to go out afternoon in mid march and in pelling temperature must have been less than 5 celsius! After going to 4-5 places, I got a room for 300 after promising to get out by 10 in the morning. It was a pretty cozy room and the windows and balcony were for the perfect view of kanchenjunga! Attendant got me hot tea and snacks within 5 min. I threw the stuff randomly and was going through videos and pics when the guy called me for a hot dinner with home made mutton, delicious! I went to sleep, before 11 again, thinking about what to expect in the morning and how magnificent the view will be!


day 6
I set the alarm for 5:30 the last day to get the first glimpse of the beautiful rock. It was so cold that I did not want to open my eyes! Cursing heavens, opened my eyes with great difficulty only to find it was pretty cloudy. It looked like it would take at least an hour for the clouds to get clear and so I went back to sleep. I checked back 3 times with no luck before getting up at 8:30. I took shower and finished breakfast by 10 and still it was cloudy.
"That's it", he said. "Today it wont clear up". The words sounded pretty harsh and I did not want to stay as I had to go to Gangtok to cover east sikkim. I started for Yuksom, from which I can go back to Legship to finish west district and then to Gangtok.I planned for some stops and the first one was Darap village. Although there was nothing fascinating about it, the view of village from the top was beautiful with all the greenery. Then there was one waterfalls,which hardly qualifies as one and I did not even stop there. Then there was Ketchiperi Lake, it was 10 km detour and the road was pretty bad, but the place was worth it.
The lake was on 5,600ft and people call it 'the wishing lake'. Although I didn't wish for anything, I found the lake and the view so serene. There was no rush of any sort or any pressure from the work.
For the first time I felt disconnected and FREE! I was just thinking about the beauty of the place and nothing else. I spent a while sitting on a bench enjoying the view and I loved every second of it.
Before leaving the place, I clicked few pictures and bought some stuff from souvenir shop.
I reached Kanchenjunga falls within an hour. As I just stopped, a guy with a camera asked me for a pic and shouted on his son to stand next to me. Then a lady dropped his 5-6 yr old son on the petrol tank and asked her husband to take a pic without caring to ask my permission.Once done with the clicks, they started asking regular where/why/how questions. Although I kind of felt proud, it was kind of embarrassing. After they bid me adieu, I grabbed a cup of tea and started climbing stairs. 50 odd steps later I was able to see the beautiful falls with water hitting the base with sheer force and the weather quietly complimented the view.
It was drizzling when I started from there and before I know it, I was all wet. I had to stop somewhere. Luckily I decided to stop at Yuksom. It is a popular starting point for kanchendzonga treks of 6-8 days. I got a room for 400 bucks and settled in. It was 3 in the afternoon and I felt like I wasted the whole day. That night,I met a chinese girl and an australian guy in the restaurant near by and when I asked her how many days was she planning to roam in India, she said, in a mixed accent, " may be 4 months, may be 6 months or perhaps a year(laughs watching me surprised), I got a long visa". It made me think why we, Indians, hesitate to travel like that. Of course even we go abroad for holidays, but we go for a week or a month at maximum, check all the popular destinations, most of which will be shopping centers, and come back to boring work. Of course our generation is looking at life differently and I see people leaving jobs to do what they love.
Anyway, coming back to Yuksom, rain did not stop the whole day and even that night. Temperatures were pretty low and worst of all my clothes were still wet. Strangely, i couldn't sleep that night, so I watched the movie 'Anonymous'. It was hard to breathe because of the height and low temperatures.
I think I slept around 2 that night.

day 7
It was sunny in the morning and I was never so happy to see the sun.I quickly hung my clothes outside and went to see the Yuksom coronation throne. I found out that Yuksom was actually the first capital of Sikkim and it was beautiful with snowtop hills surrounded with greenery everywhere. I started at 10:30 and thought if I could go back to Yangtey, near pelling, I may able to catch the glimpse of the big rock. It was already 2 when I reached yangtey and the viewpoint from the resort(forgot the name) was perfect, better than pelling. But, it was again cloudy and I couldn't! I couldn't see the kanchendzonga range. Although disappointed, I ordered food and was clicking pictures in the lawn when Mr. sharma started the usual questionnaire. Once I duly answered everything, he said something to the clerk in their language and told me then that he gonna pay for my food.I gave up refusing when he said he is a fan of adventurous guys like me. With great difficulty I managed from laughing aloud and thanked him. He also asked me to call him before I visit sikkim again and he would plan the whole trip.
After the lunch, I started for Gangtok and the roads were the best I had till now. It had dangerous turns and road was so good that the turns became little more dangerous. It was the day of bullet and bullet alone! Words cannot do justice to the power you feel when you bend the bike to turn with a perfect speed in hairpins or on a curvy plain road. The only stop after that was Ravangla and Buddha park there is a must visit. Again, it was on a hilltop with a huge Buddha idol and clouds to compliment it. I reached Gangtok in the evening and took a room near Sikkim Manipal college. It was only later I found out that Harsh's friend is actually from that college and he had no problem dropping by. So, we discussed what all places I could go to next day and I found out that actually there are many places to visit in east and north sikkim and some of which are nathula pass, tsongo lake and baba mandir on indo china border. These are all in the east sikkim and are like 50-60 km from gangtok. So, I decide to go for it the next day. Again, I couldn't sleep properly. I felt sick in the stomach and for the first time in the trip I had to take out my first aid box to have a crocin only to sleep very late.

day 8
I got up around 7 and went to permit office by 8, only to find they only give permit for cars and cabs there. I had to wait like an hour to meet a lady, who in turn told me to get the permit from home dept.
So, I went to home dept. office and after a while I found the corresponding officer, Mrs. Rohini Pradhan. She asked a girl to tell me all the procedure and I filled the form within 10 minutes.
It was already 11:30 when she was about to sign the permit and she saw that bike is on the name of pranay and authorization letter was given by Gautam. So, I called up Gautam and it was more than 2 hours after which we had something to show to the officer. She went through the permit very quick after telling me to avoid Nathula pass and come back from tsomgo lake itself as it was pretty late.
I was all pumped up when she dropped a bomb saying road was closed after confirming with some one at the checking gate.
She said that the road was pretty bad and they are not allowing even the daily cabs as it was too cloudy and she apologized as they cant allow me in particular as I was alone and its pretty risky.
She asked me to come back with a group or at least a pillion at any time and she would personally see the file get through within minutes. Although disappointed, I was happily surprised with the Sikkim govt. officials. Although I am kind of stereotyping, I can surely say, Sikkim people know how to treat their guests!
I thanked her and was about to leave when she apologized again and suggested other places to visit like ganesh tok, hanuman tok and himalayan zoo park, which I visited duly. Himalayan zoo park was pretty good with snow leopard, small tiger breed and pandas!I came back to Gangtok by 7pm. I felt sad as it was the last day in Sikkim and I cannot describe how  wonderful the last 5 days were.


day 9
Woke up around 8 and left for Darjeeling by 10. Again the road was beautiful with lots of curves and views. As I entered West Bengal, weather quickly changed to hot. I took a small stop by a riverside for a shoot with the bullet. It again became cold and calm once I entered the hills around Darjeeling and the way was totally desolated with huge trees covering the whole way to make it look like a tunnel!
On the way, like 10km from Darjeeling, a loud noise came and looked like something fell from the bike. I stopped to find half of silencer missing. I ran and grabbed the hot tube and saw that a bolt came out before and vibrations made the rest of damage. I removed the bolt from the other footrest and used it to temporarily attach it back. Afterwards, Gautam explained that it was a connector between the body and silencer broke and then due to vibrations, bolt came off. Perhaps a speed breaker could have started it all!
Just before leaving for siliguri, Gautam told he was waiting for some one who is going for a solo trip just like me and only after that he can go to ATM to give the deposit back. I was also little curious to meet the guy and just when I was thinking that generally we guys from AP are not into solo trips, Teja shows up saying he is from tirupathi and works in Mumbai. After a little chat and suggestions about places, I wished him good luck and left for ATM with Gautam. Although I had reached Darjeeling by 2, Gautam showed up at the cafe only by 6 and it was almost 7 when I reached the taxi stand and I had the train ticket booked for 9 from siliguri. Within 5 min, I found a taxi, but he wasn't going anywhere without 5-6 people. After waiting for 10 minutes with no luck I understood it would be pretty late. So I got out and found a siliguri tourist car heading back. So he picked us up and started for Siliguri. 5 min into the ride and he got a call from some one asking him to return as he would be picking some tourists in Darjeeling the next morning. It was almost 7:30 and I was getting nervous and found myself begging god for a taxi to come. In 2 min, first taxi guy came there with around 5 guys in the taxi waving his hand frantically. I got in, thanked the god thousand times and asked the driver if we can reach siliguri in time. He said that he can make it easily and I was relieved.
We reached Siliguri by 8:30 and I grabbed a shared taxi to NJP station. I reached there at 8:55 and I was almost running before finding out that the train got delayed by almost an hour. I was relieved and disgusted at the same time. I checked my mail and fb before boarding the train without realizing that it was going to be the last time in the trip to enjoy internet and perhaps phone network. I had a good sleep that night in the train.


My journey continued for 7 more days and although I missed the bullet, north east was as great as Sikkim where I joined 2 random gultis in camping and other adventurous(not much) activities apart from enjoying some awesome road trips.