How I Prepared for the Google Internship Interview.

Hey everyone, I'm Atibhi, I interned with Google as a Summer Intern in 2020. After I got the internship, a lot of people asked me about my preparation strategy.

In this blog post, I have tried to clear some of the common questions every student has regarding interview preparation. I have also included resources that helped me during my preparation!

My site of choice - Leetcode

I have explored many sites and in the end, I found Leetcode to be the best.
Sites like CodeChef, Codeforces, SPOJ are really good but they are not interview/job-focused, they lean more towards competitive programming. If your aim is to go compete at ACM ICPC, by all means, practice at those sites.
For interview preparation, the top sites are Leetcode, GeeksForGeeks and Interview Bit. Leetcode beats the other two sites hands down. While the theory in GeeksForGeeks is good (it is often coded inefficiently) and their practice platform has weak test cases. InterviewBit has a good collection of questions but their list is limited, also they do not have a vibrant community.
Leetcode has everything that a good site should, an amazing list of questions, good editorials, really good test cases as well as a community(best thing). The discussion section has amazing discussions, sometimes the solutions here are better than those in the editorial.

I Am Intimidated by the List of Questions, Where Should IStart?

First and foremost, there is no reason to be intimidated, we all have to start somewhere:) If you are a complete beginner, start with Top 100 Liked Questions and Top Interview Questions. Sort them by difficulty level and do the easy ones, followed by medium and then hard.

How Should I Solve Each Question?

Everyone has a different way of approaching problems, I initially looked up the solution to every problem but when I gave the Weekly Contests(another amazing feature! more about it later) I realized my technique wasn't working. I then thought about a question and worked out a basic algorithm and then coded. If it took more than a certain amount of time, I saw the solution. I also went through Leetcode discuss to see different approaches.
Here is a curated list of "how to Leetcode" from various people, do give it a read! It is helpful:

• Leetcode Grinding Guide on Reddit
• Patterns on Leetcode Problems
• Want to crack Leetcode problems easily?
• r/cscareerquestions-I have to literally look up up every Leetcode solution. Is it normal?
• how-to-leetcode-effectively

How Do I Measure My Performance, I Am Solving Questions but Am I Improving?

ONE WORD-WEEKLY CONTESTS. Initially, when I started giving weekly contests I would not be able to solve even a single question, but with practice, I started solving two to three. It motivated me to work harder every week and manage time better. I also maintained an excel sheet where I kept track of the questions that I solved in contests.

How my contest excel sheet lookedlike.

How "MANY" Questions Should ISolve?

It is not about the number of questions rather it is about "how" well you understand the concepts and are able to approach new problems. In spite of that, doing the Top Interview Questions should be a must.

Other Tips

• Read as many interview experiences of people as you can from Leetcode Discuss.
• Ask doubts in Leetcode Discuss for each question.
• If your interview is nearing, take Leetcode Premium and do company-wise questions (very helpful).

What are the important topics I should study ?

Big O Notation

• Theory
• Practice problems from Cracking the Coding Interview

Arrays and Maths

• Practice a lot of Questions on Arrays and Maths. Some important topics are mentioned below.
• Circular Arrays - Typical ways to solve on Leetocode
• Boyer Moore Voting Algorithm Leetcode
• Two Sum Problem - Leetcode
• Three Sum Problem - Leetcode
• Four Sum Problem - Leetcode
• Buy and Stock problem - Leetcode
• Buy and Stock problem II - Leetcode
• Buy and Stock problem III - Leetcode
• Buy and Stock problem IV - Leetcode
• Buy and Stock With Cooldown - Leetcode
• Questions relating to Palindromes.
• Longest Palindromic Subsequence
• Finding square root of a number in logn time - Leetcode
• Subarray and Subsequence problems.

Binary Search

• Binary Search from Topcoder(MUST)

Bitwise manipulation

• A summary: how to use bit manipulation to solve problems easily and efficiently - LeetCode Discuss
• Good website to visualize bitwise operations
• https://www.geeksforgeeks.org/bits-manipulation-important-tactics/

Trees

• Pre-order(BOTH recursive and iterative)
• Post-order(BOTH recursive and iterative
• In-order(BOTH recursive and iterative
• N-ary Tree Pre-order Traversal
• N-ary Tree Pre-order Traversal
• N-ary Tree Level Order Traversal
• Maximum Depth of N-ary Tree
• Serialization and deserialization of trees - Leetcode
• Binary Search Tree
• Lowest Common Ancestor - Leetcode
• Morris In-order traversal by Tushar Roy (Video)
• Threaded Binary Tree

Recursion and Backtracking

• Recursion and Backtracking Tutorial
• Blog by csgator(BEST)
• Interview Bit Theory
• Turnpike problem
• Word break Problem Leetcode
• Word break Problem 2 Leetcode
• Letter combinations of a phone-number Leetcode

Graphs

• Representing graphs
• DFS, BFS Explanation by csgator(BEST)
• Topological Sorting
• Prims and Kruskal
• Dijikstra
• Dijkstra on sparse graphs - Competitive Programming Algorithms
• Number of Islands
• Friend Circles
• Decode String

Geometry

• Geometric Algorithms - GeeksforGeeks

Hashing

• map vs unordered_map in C++ - GeeksforGeeks
• Design HashMap
• Design Hashset
• Sliding Window algorithm template to solve all the Leetcode substring search problem. - LeetCode Discuss (This is important !)
• String Hashing

Linked List

• Insertion
• Deletion of Node
• Reverse Linked List (iterative and recursive)
• Circular Linked List
• Doubly Linked List
• Floyd's Cycle Detection Algorithm
• Linked List Cycle - Leetcode
• LRU Cache - C++ Implementation - Bhrigu Srivastava
• Copy list with random-pointer (BEAUTIFUL QUESTION!)

Dynamic Programming

• TopCoder Article (VERY IMPORTANT!!! MUST)
• Top 20 DP questions(Geeks for geeks) Important!
• Tushar Roy DP playlist
• Do Questions from Interview Bit (Good List) :P
• Top 50 DP questions
• Difference between DP and Divide and Conquer

Disjoint Set Union

• DSU CP-Algorithm

Sorting

• Be clear with the basic algorithm and time complexity of all sorting algorithms.
• Additionally read up to count sort, bucket sort and radix sort.

Greedy

• Basics of Greedy

System Design

• Leetcode System Design Posts
• System Design Videos (Sufficient for prep)
• System Design Resources
• How to succeed in a System Design Interview

For now, these are the topics that I feel are important for an interview, obviously, this is not an exhaustive list :)

Google Specific Interview Tips

• Practice coding on google docs.
• Write variable and function names that are descriptive.
• Be honest. Do not bluff.
• Be vocal, explain your approach while coding.
• Give a lot of mock interviews to friends in a real environment.
• Do a lot of leetcode.
• Be confident!

Hope this blog post helped you! All the best! Feel free to post any questions :)