/google-tech-dev-guide

Preparation for Software Technical Interview

Primary LanguagePythonApache License 2.0Apache-2.0

Preparation for technical Interview

Introduction

Interview study to reinforces basic software engineering skills.

Interview Preparation

Technical Phone Interview Preparation
Technical Interview Study Plan

Overall Plan

  1. I didn't solve hard problems at all. I solved around 400 medium problems and all easy problems on LeetCode. It's better to understand the approaches used and learn to come up with the solution yourself, instead of looking up the answer.
  1. Don't look the answer at all. If you can't solve the problem in an hour, even with drawing on a notebook with a pen, just skip the question. Don't look the answer. Go back to this question in two weeks and try another hour. If you still can't solve it - try to find a hint, if there's not hints, then lookup the answer. Review this question in a month or so.
  1. Practice your weak topics.
  1. You'll most likely asked a hard problem on the interview. But solving many Medium LC questions will help you much more. There are many Medium problems that are harder than the Hard ones.
  1. Don't run after numbers. It doesn't matter if you solved 100, 200, or 1000 problems. All that important is the quality. If you solved 200 problems, but you looked the answers for half of them, I bet you won't be able to come up with a solution to a problem you saw 3-4 weeks ago. Which means, your brain will work like a Queue.
  1. Quality > Quantity.
  2. Good luck.

You should be able to crack a decent amount of hard LCs, that being said, Google focuses pretty heavily on breadth. So be sure to practice extensively on:

backtracking(appears very often)

dynamic programming

graphs (dfs, bfs, union find [usually asked as a follow up question to optimize a purely dfs/bfs approach], dijkstra)

two pointers (very often)

binary search (very very often) I've noticed somewhat of a new trend at Google, namely binary search on monotonic functions, i.e. : https://leetcode.com/problems/split-array-largest-sum/.

Several others have mentioned getting interviews on this kind of problem, and you're pretty much gonna be able to come up with a solution instantly if you map it to binary search on sight.

Other sites guides

Pattern Plan

Review

Question List

Complexity - Time and Space

Merge sort time and space complexity

Practice Your Code

Sites to practice your code

Company focused tags

Lectures and Tutorial and Guides

Style Guide

Tutorials

Lecture Videos

Python Topics
Python - Deep copy vs shallow copy
Python - When to use
Python - Integers
Python - List
Python - Dictionary
Python - Typing Annotations
Textbook Resources

Data structures

Binary Tree
Stack
Queue
Heap
  • Binary Heap
    • n = len(array)
    • last parent = ((n - 1) - 1)//2
    • parent index given i: parent = (i-1)//2
    • index of left child = 2 * parent + 1
    • index of right child = 2 * parent + 2
    • where 0 <= i < n
from typing import List

def swap_min_value(array: List, parent, index):
    n = len(array)
    if index < n and array[parent] > array[index]:
        array[parent], array[index] = array[index], array[parent]
        
def min_heapify(array: List):
    
    n = len(array)
    last = n - 1

    # Last parent index
    parent = (last - 1) // 2

    while parent > 0:

        left, right = 2 * parent + 1, 2 * parent + 2
        
        swap_min_value(array, parent, left)
        swap_min_value(array, parent, right)
        
        parent -= 1

Algorithms

Mergesort
Quicksort
Heapsort

  • Heapsort using binary heap

  • To sort elements in ascending order:

     start i = 0
 while i less than n-1
     build max heap from i=0 to n-1-i
     swap 0 and n-1-i element in order to put the max element at n-1-i index

  • To sort elements in descending order:

     start i = 0
 while i less than n-1
     build min heap from i=0 to n-1-i
     swap 0 and n-1-i element in order to put the min element at n-1-i index

Google Tech Dev Guide

Google Tech Dev Guide

  1. Find the find longest word in dictionary that is a subsequence of a given string

  2. Find the max span of a given list

  3. Remove all occurance of a pattern in a given string

  4. Sum numbers in a given string

  5. Find a balance sum in an given list

  6. Hangman game

LeetCode

LeetCode Articles
LeetCode

Sliding window

Problem Difficulty Solution Test Time Complexity Space Complexity
Maximum sliding window

70 Questions

algoexpert.io - 70 Questions

Array

Problem Difficulty Solution Test Time Complexity Space Complexity
Two number sums Easy .py O(n) O(n)
Three number sums Medium .py O(n^2) O(n)

LinkedList

Problem Difficulty Solution Test Time Complexity Space Complexity
Construction of a double linked list Easy .py
Remove Kth Node from End Medium .py O(n) O(1)

String

Problem Difficulty Solution Test Time Complexity Space Complexity
Caesar Cipher Easy .py .py O(n) O(1)
Largest palindrome substring Medium .py .py O(n^2) O(1)

Searching

Problem Difficulty Solution Test Time Complexity Space Complexity
Largest three numbers Easy .py .py O(n) O(1)
Binary search value Easy .py .py O(log n) O(1)

Searching

Problem Difficulty Solution Test Time Complexity Space Complexity
Bubble Sort Easy .py .py O(n^2) O(1)
Insertion Sort Easy .py .py O(n^2) O(1)
Selection Sort Easy .py .py O(n^2) O(1)

Hackerrank

Hacker Rank

String validators