Learning

Algorithms Live!

youtube | blogspot

Recommended: Do them All!

• Watch episode and solve each problem on your own (most have online judges)
• Skim coding section to potentially pick up some new coding techniques

Minimal: Do the following:

• Fenwick Trees
• Trees and Diameters
• Segment Trees
• Geometric Sweeps
• Cows (Important Binary search technique but a harder format)
• Solution Bags
• Exchange Arguments
• Binary Lifting LCA
• Knapsack DP
• Bitmask DP
• DFS LowLink
• Biconnected Decomposition
• Strongly Connected Components
• Topological Sort
• Orchestra (It's like a hard version of a classic interview problem)
• Max Flow
• Venture Cup (Good Mathematical Approach to simplify a problem)

Learning From Contests

Any time you fail a problem in a contest, look at the solutions afterwards. If it uses a concept you've never heard of, learn that and solve the problem. You will almost certainly see it again somewhere.

Contests

• Leetcode: Saturday 7:30 PST (1 hour 30 minutes)
• Codeforces: 1-2 per week but latest is like 8am PST (2 hours)
• Codechef: 1 Long Challenge (2 weekends long)
• Google Code Jam: Once a year in April, but usually very fun problems.
• Find more contests: clist.by

I recommend doing the Long challenge every month, and doing Leetcode as you are in the mood. Leetcode is most representative of interview but less effective for learning. The long contest gives you time to be creative and explore lots of solutions.

It's important to not look up the answer immediately. The value in spending hours considering failing approaches is that you learn and gain an intuition for what does not work. That way, in an interview, you spend your time exploring only solutions that have potential.

Goals:

Division 1 on Codeforces or Codechef and completing the weekly Leetcode contest in < 1 hour is overkill but a good benchmark to strive for anyway.

Learning Objectives

• Learn Algorithmic concepts
  • This is actually the least important, complicated theory questions are pretty rare in interviews. Segment Trees and Flow is like the absolute limit
• Get better at coding/debugging
  • Debugging problems like these is very hard, and extremely costly in a programming contest. You need to learn how to identify errors quickly and gain an intuition for common edge cases.
  • You need to learn a programming style that minimizes code written and potential mistakes. Ex: sum all neighbors:

  for (int x = 0; x < N; x++)
    for (int y = 0; y < N; y++)
      int sum = 0;
      for (int dx =  -1; dx <= 1; dx++)
        for (int dy = -1; dy <= 1; dy++)
          sum += inBounds(x+dx, y+dy) ? arr[x+dx][y+dy] : 0;
	
public boolean inBounds(int x, int y) {
  return (x >= 0 && y >= 0 && x < N && y < N);
} 

Having written this code many times this is way cleaner to debug than having a bunch of if statements

• Articulating your thought process
  • Easiest way to fuckup an interview is to not say anything. You MUST explicitly say what you are thinking even if you have no idea. Most interviewers will give you useful hints so assume any hint they give you is the right answer.
  • There should be no dead air even when you are coding

Interview Script

1. Ask clarifying questions (bounds, types, edge cases)
2. Propose a brute force solution (and describe its runtime)
3. (Time permitting) do the brute force on a small example)
4. Propose an optimized solution (and describe its runtime)
5. Do the optimized on a small example (this will also help you find logical errors)
6. Code the optimized solution
7. Throw out some edge cases that your solution will handle

Behavioral Questions

• Idk I'm not good at these apparently

Questions for Interviewer

• Tell me about your work
  • Works every time

Practice Interview

Once you feel like you have mastered most concepts, give these questions a try. Try to complete each in 45 minutes or less.

List of Questions to do

• merge k sorted lists

  Open after solving

  This is about 30% of all interview questions, so I hope you solved it.

• critical connections in a network

  Open after solving

  DFS Lowlink coming in huge on this one. Here's another search based question: minimum moves to move a box to their target location

• minimize malware spread

  Open after solving

  This type of problem can be solved with Union-Find but I usually go for BFS/DFS when available. Here's another similar one: check if there is a valid path in the grid

• course schedule II

  Open after solving

  Topological sort is definitely something you want to know in and out. Here's another graph one: find eventual safe states

• construct target array with multiple sums

  Open after solving

  This one is pretty tricky, but it utilizes a very important technique of working backwards. If you didn't get that one, give this one a shot: burst balloons

• uncrossed lines

  Open after solving

  It's pretty common especially for Google to hide standard problems behind some logical transformation that you need to think through. In an interview you would want to be talking through your though process with your inteviewer, and they might give you hints to put you on track. Here's some more DP practice: count all valid pickup and delivery options

• smallest sufficient team

  Open after solving

  I hope you watched the Bitmask DP video, it's not as common in interviews, but if you can't find an optimal solution you can maybe break out the bitmask DP before moving on to something more optimized. Here's some more practice with bitmasks: maximum students taking exam

• daily temperatures

  Open after solving

  Ah the classic Binary tree problem. In java you can use a TreeMap or TreeSet. These are pretty common and you'll look like a chump if O(N) is the best you can do. Here's another one to try: minimum number of taps to open to water a garden

• course schedule III

  Open after solving

  Lots of question have this format of sets of ranges, but the solutions can be varied. Here's are some more to try: maximum profit in job scheduling or minimum number of arros to burst balloons or brick wall

• find in mountain array

  Open after solving

  A binary search question was the only one I messed up on in my actual interview. I think they are pretty tough to intuit and have a lot of edge cases that are tricky to iron out without being able to run code. Here's some more binary search: find first and last position of element in sorted array

Other questions I like:

Some questions with elegant or clever solutions:

• remove palindromic subsequences
• reverse substrings between each pair of parentheses
• convert to base -2
• distinct sequences II
• element appearing in more than 25% of sorted array
• trapping rain water
• maximum performance of a team

Practice with a Googler

Ask a friend to give you a mock interview, behavioral and technical. I'm at "".join("bking2025", "@", "gmail.com")