// not with a bang, but a whimper//

// Interviewing at Google (While feeling inadequate)//

I got an email from the ACM (computer science jobs/talks/random list) about an internship at Google called the Engineering Practicum that is specifically for sophomores in college that are “CS minorities” (namely women, blacks, hispanics, etc. who are underrepresented in computer science.)

I hadn’t taken many CS classes at Stanford. When I applied for the program, I’d pretty much taken 106A, 106B and 107. Not only that, but my grades in these classes were definitely below par, and I struggled with the assignments even though I tried my best. But I decided to have a stab at the application anyway- it couldn’t hurt right? The application was due on Oct 15, and I didn’t think much of it after it was gone.

10 days later, they wrote back telling me I had interviews scheduled for Nov 4th. Two weeks after those interviews, which I will talk more about later, I was in the host matching round. After another couple weeks, my recruiter informed me they had found a host match. And finally, on December 19th, she called me from the NY office with an offer! 

Throughout the entire process, I tried to really low expectations to save myself from disappointment. I knew that hundreds applied from all over the world, and there were only so many spots (90 in all 4 offices, probably like 40 tops at the Mountain View office) and I didn’t really have the confidence in my own abilities to make me feel secure. When I finally got the office, it was a dream come true!

I was also really lucky because a friend of mine applied to the program 2 years ago and gave me some guidance, as well as a senior friend who was applying to Google at the same time as me. They helped coach me through the interview process (which was the most difficult part by far.) I’m writing down some of the knowledge they passed down to me and some of my own knowledge after going through the process that I hope will be helpful to others.

DATA STRUCTURES:

     Sets
          contains set of unique objects of same type, search insertion removal have O(1) complexity

     Hashmaps
          add, remove, find- O(1) because everything is in buckets, just index directly
          easy to use to determine equality and search for particular things
          push everything into a map and search (space no object)

     Trees (binary esp.)
          Binary search- going down the height of the tree
          easy to use to compare (greater, less)
          each node has two children, left and right (less than greater than)

     Arrays
          find, add, remove- O(N)

     Heaps (not as important)
          usually implemented with array
          used to find max/min in constant time

     Queue
          First in first out
          used for Breadth first search

     Stack
          First in last out depth first search

ALGORITHIMS
     Quicksort NLOGN (worst case: N^2, but almost never happens)
          In place, switching
          pick a pivot, sort the two halves around it 
          don’t need to insert pivot (will already be included)

     Mergesort NLOGN
          sort the two halves, merge together at end
          need memory to store the sorting halves
          slower because need to take time to get memory

     insertion sort N^2
          generally only used if you need to go through and only add one thing to an already ordered list

Also know pointer arithmetic, algorithmic complexity of operations, as well as some general knowledge of operating systems. Generally, the best advice I received was to keep talking—always let the interviewer know what you’re thinking. There are two back to back interviews, each lasting about an hour, where the entire interview is conducted over the phone and you’re given a googledoc to write out the code for the problem. The interviewer can’t see your face and doesn’t know what’s going through your mind. Even if you get the entire answer wrong, what they really want to see is that you have the mind for the internship, and your thought process is critical even if you make mistakes. Always remember to think about edge cases first (what if NULL values are passed in? what if there are repeating characters in the string?) Write down the pseudocode first, ask for the function calls and work with the data structures you know.  

Questions they asked me, so you can get some reference of what you would see:

• String question: Given two strings, return true if the two are anagrams.
• Pointer arithmetic: bunch of *a = *bs, what are a and b at the end.
• Operating systems + networks: What happens when you query Google for a search? How is all the data Google collects for tracking webpages stored? (hint: think about a HUGE data structure similar to one of the ones listed above.)
• Data structures: Given two linked lists, find the intersection of the two.
• Data structures: How do you implement a stack with queues?
• A debugging question, where they ask you what would go wrong should the function they copy into your document be run.

I sort of forget if there were other questions, but they were pretty varied and of about the same difficulty. Even if you don’t know the answer at first, talk it out! Eventually it’ll work itself out, or the interviewer will step in to help you in the right direction. Both of mine were pretty friendly and understanding that in the end, you’re just a student and they both have 10+ years in industry experience.

All in all, it’s a great experience to interview and always good to practice for the future! I think my summer at Google will be amazing, and I will continue writing about the things I’m doing there come June. 

// raskolnikov//

do you remember, in crime in punishment, how he was unable to ever forget his guilt? and that no matter what he did, it couldn’t escape him. he knew he had done wrong, and every turn seemed like someone else was about to find him. 

in the end, it was his own guilt that turned him in. 

sometimes the mind is too powerful of a place. consciousness is what separates us from animals, but perhaps it is our downfall as well.