Why compare when you can just count?
The Bucket Sort algorithm
LC75 - example of Sorting Colors
The problem statement is as below.
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color
are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library's sort function.
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# bucket sort
value_range = 3 #red, white or blue
counts = [0] * value_range
for i, n in enumerate(nums):
counts[n] += 1
i = 0
for value, freq in enumerate(counts):
print(value, freq)
for _ in range(freq):
nums[i] = value
i += 1
Quick rundown
The bucket sort algorithm relies on the fact that values belong to a known range. In this example it is [0,2] โ Z.
The input arrays have already been prepared, by encoding categorical values into numerical ones. The same
thing could be said about a different numerical range where the start of range is re-indexed or shifted back to 0.
Valentine's Matchmaker Algorithm ๐
LC765 - Couples holding hands
Problem Statement
There are n couples sitting in 2n seats arranged in a row and want to hold hands.
The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the ith seat.
The couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3),
and so on with the last couple being (2n - 2, 2n - 1).
Return the minimum number of swaps so that every couple is sitting side by side.
A swap consists of choosing any two people, then they stand up and switch seats.
Initial solution
The below solution provides an O(n) time complexity and memory. Relatively simply, checking for every pair of people, if the left-hand side person is not seated next to its beloved, then we swap the right person next to them.
Scan It Like You Mean It ๐
Automated Vulnerability Scanning for Dependencies & Packages
Do we need to explain why?
๐ฅ๐ฅ๐ฃ๐จโกโ ๏ธ๐งจ
That’s what I thought.
Configure your pipeline with Snyk
There is a plethora of tools available out there for security scans and/or vulnerable dependencies - Dependabot, Trivy, sonarQube/Lint, Anchore, etc. Most of which can be integrated into your IDE or CI/CD.
For this use case, Snyk has been selected. Snyk is able to scan code, open-source dependencies, container images, and infrastructure as code configurations to helps developers prioritize and fix security vulnerabilities. The free version comes with a max limit scans per month.