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....
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....
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....
Updated - 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?...
Tips for post creation
I started blogging in Dec 2021. It’s been a wonderful journey. Has enabled me to gather my thoughts in a far more structured way. The series is based on my setup of Hugo - Netlify - GitHub. I’ll shared my knowledge in terms of Hugo knowledge, how to write a blog post and more. If anyone is interested in the Netlify setup, see Hugo Quick Start then Netlify - Hugo setup....
Tree Basics and some Swift helpers for leetcode
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:...
How Can I Inspect the Size Impact of Symbols in an App Binary: A Practical Guide for Apple Developers
In the previous posts we talked about Build Pipeline, Jargon, Static Linker vs Dynamic Linker. In this post we’ll benefit from the knowledge gained about the app wrapper’s folder structure and the placement of all the different binaries (frameworks and main app’s executable) to know where to look for. New in this post is learning how to use the nm command to inspect and count the number of symbols of each binary....
Optimizing Binaries - How Does the Linker Help Reduce App Size? What are the different types of linking - Part Two
In the previous post we talked about how the linker’s selective loading helps solve the bloat issue. But there are some other limitations to static linking. Because of those limitations software engineers created Dynamic libraries and the Dynamic Linker. In this post we’ll go through some of those limitations and discuss the trade-offs between the two ways of linking and their sizing impact. Inspired by Link fast: Improve build and launch times - 15:47:...
Optimizing Binaries - How Does the Linker Help Reduce App Size? What are the different types of linking - Part One
In the previous post we talked about a problem with the linker: Linking a single function from a library could link to the entire library. This creates a lot of bloat. As a result some enhancements were made to linker. The enhancement was to be selective and only load symbols that you need. Inspired by Link fast: Improve build and launch times - 4:15: Selective Loading In a nutshell if you have the following source code written in C:...
Optimizing Binaries - Build Pipeline Jargon
To understand this post, I highly recommend everyone to watch the WWDC 2022 - Link fast: Improve build and launch times and WWDC 2018 - Behind the Scenes of the Xcode Build Process. They’re of the best talks I’ve ever seen. This post covers some of the jargon and how it all comes together. And even though I love making puzzles, I’ll justify why I picked it as my cover....