The effect of direction on recursion and understanding code

Today I’m going to discuss another fun and common challenge. It’s the Longest Common Subsequence a.k.a. LCS. I’ll first focus on discussing a pain point I went through when I was trying to compare the algorithm I deduced on my own vs a few other algorithms I saw online. Our algorithms seemed very similar. Yet different. It made debugging my code based on other code very difficult. This is a very common problem I face when I doing leetcode....

December 2, 2023 · 6 min
An AI generated image of asteroids

Asteroids Collision

Today we’re solving https://leetcode.com/problems/asteroid-collision/ Imagine if we had the following: 1 5 3 8 6 -> -> <- <- -> Each number represents the size of an asteroid. Each asteroid is either going left or right. Bigger asteroids destroy smaller asteroids. Asteroids with same size both get destroyed. If two asteroids are going in the same direction, they don’t hit each other, because all are going in the same speed....

November 20, 2023 · 6 min
Multiple envlopes along with their width and height

How Many Envelopes Can You Fit Into Another?

Question: How many envelops can you fit into another? Each envelope has a 2D representation. [4,5] -> width = 4, length = 5 How many envelops can you fit into one another without rotating any envelopes. Bare in mind you can’t fit in two evelopes with same width or height. This is question is very much like a Russian Doll question. Which that question itself uses an Longest increasing subsequence algorithm to solve....

November 12, 2023 · 4 min

Longest Increasing Subsequence Length

Attention: This post was updated to include the alternate solution that uses binary search. It reduces the Time Complexity from O(n * n) to O(n * log n). Before we present the question. Let’s figure out what a subsequence is: What’s a subsequence? Any selection of items from the original array. The selection must respect the order. Meaning for [1,2,3,4,5] only two of the four below are subsequences: [1,2,3,4,5] ✅ [1,4,3,2,5] ❌ order not respected [1,2,5] ✅ [5,1] ❌ order not respected What’s the difference between a subsequence and a subarray?...

November 11, 2023 · 10 min

Interviewing - Trees

August 11, 2023 · 0 min

How to Think Recursively - Part 2

Please read How to Think Recursively before reading this post. This post re-applies the steps mentioned in the previous post on a more challenging question. Question Return all possible ways we can generate a well-formed parenthesis? Examples: if n = 1 then we can only form () if n = 2 then we can form (()) and ()() if n = 3 then we can form ((())), (())(), ()(()), (()()), (), (), () Let’s try applying our 4 steps:...

November 15, 2022 · 5 min

How to Think Recursively - Part 1

These articles are about the gotchas I faced when trying to think recursively. The logic in principle should apply to most recursive problems. In this post, I will use the following question as a point of reference: Count how many ways you can climb a staircase. You can jump either one step at a time or two steps at a time. Example if there are 3 stair cases then you can either jump:...

November 15, 2022 · 9 min

How Understanding State Machines Helps With Building Trees and Graphs

My team was dealing with a large flow, where user can transition from multiple states or sometimes skip certain states. We didn’t have a centralized controller, every screen just had logic on where it should go next. This made it difficult for us to see all our logic at once. We asked around and was told state machines are a good fit for our situation. State machines are void of any UX....

October 6, 2022 · 7 min

Which Way Am I Sorting?

I always got confused as to what’s the end result my sort. I wasn’t sure if it would end up being ascending or descending. The ultimate trick is to not think of up vs down. Instead think of increasing/decreasing from left to right. We perceive arrays as horizontal beings. Hence left and right make more sense vs up and down let nums = [1,4,2,3] let sorted_nums = arr.sorted(by: { $0 < $1 // left is smaller [1,2,3,4] i....

August 3, 2022 · 2 min

Recover Binary Tree

Question: You have a binary tree. But only two of its elements have been swapped. This makes it a faulty binary tree. The challenge is to swap those two elements. And fix the tree. Solution I knew I had to traverse it. But then what? With a little help from reading online, I realized I should traverse it, and store the values into an array. Then you just loop the array and find the bad indexes....

June 27, 2022 · 4 min