When it comes to solving questions asking for the number of ways to be king of the world, or something simpler — the number of ways to generate a specific coin change — use Dynamic programming.
Question from Elements of Programming interviews :
In a game, a play may lead…
The first thing to note about Dynamic Programming is that — you cannot memorize the patterns! Memoize, but do not memorize!
If you understand recursion — dynamic programming is just one and a half steps ahead of recursion. …
I’d started to get bored of leetcode. I could not bring myself to solve another leetcode problem. After all, it did not serve any higher purpose. I wanted something else to occupy my mind — that is when I came across Jeff Erickson’s book on Algorithms : https://jeffe.cs.illinois.edu/teaching/algorithms/#book
It absolutely blew my mind! This book is clearer and better written than any other algorithm book out there! So friends and algorithm enthusiasts — let’s solve the exercises!
I will be starting a new series of posts on the book — I’m open to discussions and working together while solving the exercises! Let me know!
What are skip lists? The idea is actually quite intuitive. Let’s look at a real life example : You are travelling from Algoland (an imaginary city) and as a tourist, you would like to visit different places and cover as many spots as possible.
As seen in the image below…
If you notice the problem closely — what you need is a sorted list of the array everytime. What better data structure to use than a heap?
public int connectSticks(int[] sticks) {
PriorityQueue<Integer> pq = new PriorityQueue<>()…A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
Input s = “ababcbacadefegdehijhklij”;
Output = [9…
The motivation for this problem came from Steven Skiena :
8–4. The longest common subsequence (LCS) of two sequences T and P is the longest sequence L such that L is a subsequence of both T and P. …
The longest common subsequence is a very popular DP problem whereby we try to figure out the longest common subsequence between two strings
For example : “democrat”, “republican”
The longest common subsequence between the above two strings is “eca”
To figure out the length of LCS, we can build a…
We take a look at a variant of the Longest common subsequence problem — which is the longest common substring problem.
8–3. The longest common substring (not subsequence) of two strings X and Y is the longest string that appears as a run of consecutive letters in both strings. …
We take a look at another variant of the edit distance problem — Interleaving strings.
8–2. Suppose you are given three strings of characters: X, Y, and Z, where |X|=n, |Y|=m, and |Z|=n+m. Z is said to be a shuffle of X and Y iff Z can be formed by…
