swift

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 algoritm I deduced on my own vs a few other algorithms I saw online. Our algoritms seemed very similar. Yet different. It made debugging my code based on other code very difficult. This is a very commong problem I face when I doing leetcode....

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....

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?...

I do leetcoding every once a while, but keep forgetting some tree basics. This post here it to help with that. Types of Tree Trees can have multiple children. Or on the special case of binary trees have only two. A binary tree is still different from a binary search tree (BST) where things follow a certain order. Binary search tree For a Binary tree to be a BST, it has to follow the following rules:...

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....

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....

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....

A good number of interview questions require you to constantly split an array/string in half. This is relatively easy to achieve when the array count is odd. However when the count is even, it’s not as easy. let a = [1,3,8,10,22] // middle index is 2 let b = [1,3,8,10] // middle index is 1.5 which is non-existent. So what now? Most important thing to note is: There’s no such thing as “middle index” when the count is even, I mean there’s two middles in that case....

Question A simple compression algorithm would be to replace repeating characters with their count. Example aaa --> a3 aaabb --> a3b2 aaabbaa --> a3b2a2 Want to stand out? Ask if there’s a difference between a & A and if you need to add uppercase & lowercase together or need to separate them. In my implementation I assumed they’re different. Code // start counting, then upon seeing a diff, write the count....

Question You can edit a string in three different ways: insert, remove or replace a character. Write a function to see if two strings are one or zero edits away. Example like, like --> true (zero edits) like, likes --> true (one edit: remove/insert) like, life --> true (one edit, replace) like, lik --> true (one edit: remove/insert) like, pine --> false (two edits) like, lion --> false (two edits) Strategy For most questions that require you to return true or false, you can reduce the scope of the question by removing noise....