Posts

Standard Finite-State-Machine (FSM) Implementation - II

-
Image
There are multiple ways to solve this problem, but I find a state machine implementation very intuitive, even if we have to leave some of the state transitions empty (no-op). The state manages whether you're in "same char" mode or "different char". Code is down below, cheers, ACC. Find Mismatched Segments Between Two Strings - LeetCode You are given two strings s1 and s2 of the same length. A mismatched segment is a maximal contiguous range of indices where the characters of s1 and s2 differ at every index. Return a 2D array containing [sub1, sub2] for each mismatched segment, where sub1 and sub2 are the corresponding substrings from s1 and s2 , respectively. Return the segments in increasing order of their starting indices. If there are no mismatched segments, return an empty array. A substring is a contiguous non-empty sequence of characters within a string.   Example 1: Input: s1 = "earth", s2 = "empty" Output: [["ar...
Post a Comment
Read more

Sliding Window Technique - Part 14

-
Image
A bit of vintage coding, no GAI involved. This is a sliding window problem, it is a bit tricky because you have to maintain not only the numbers in the candidate subarray but also the sum of pairs in that subarray, so two different data structures (I used hash tables but you can use other dictionary data structures) to keep this information. You need to update both of them accordingly when moving either the right pointer or the left one. Complexity is N^2 (N==1000) however the usage of untyped hash tables is slowing down the constant significantly, there are other ways especially given that the numbers in the array are small-bounded. Code is down below, cheers, ACC. Longest Subarray With Restricted Pair Sums - LeetCode You are given an integer array nums . A subarray nums[l..r] is valid if there are no three distinct indices i , j , and k such that l <= i, j, k <= r and: nums[i] + nums[j] == nums[k] Return the maximum length of a valid subarray of nums .   Example 1: In...
Post a Comment
Read more

X to the power of X (X^X)

-
One of my sons asked an interesting question: what number raised to itself equals to 25? In other words, he wanted to find X such that X^X = 25. I decided to write a simple program (no GAI for a change, just vintage coding) to do that. The key observations here are: 1/ X^X is continuous in the real domain 2/ It grows monotonically  3/ It grows very fast With that in mind, the solution is a binary search. The lower bound is 1, the upper bound can be found quickly by doubling the number, then we perform a standard binary search (some nuances there just because we're dealing with floating-point numbers). Complexity stays around Log(Log(N)), hence very fast. Code is down below, cheers. Oh... and the answer to my son is the following: 2.96321964263916 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Exp { internal class Program { static void Main(string[] args) { double...
Post a Comment
Read more

Sliding Window Technique - Part 13

-
Image
Solution here is a simple sliding window approach, the caveat is to cache the mapping number -> list of unique factors which you can use across test cases. Reasonably fast prime factorization is important too, mine isn't the most optimal but fast enough to pass all test cases. Code is down below, cheers, ACC. Longest Subarray With at Most K Distinct Prime Factors - LeetCode You are given an integer array nums consisting of positive integers and an integer k . The prime factor set of a subarray is the union of the distinct prime factors of all its elements. Return the length of the longest subarray whose prime factor set contains at most k distinct prime factors. If no such subarray exists, return 0.   Example 1: Input: nums = [7,6,10,12,11], k = 3 Output: 3 Explanation: Consider the subarray [6, 10, 12] : The distinct prime factors of 6 are {2, 3} . The distinct prime factors of 10 are {2, 5} . The distinct prime factors of 12 are {2, 3} . The union of these sets is {2...
Post a Comment
Read more