Skip to main content

Coding with a Glass of Milk

Search This Blog

Longest Common Subsequence

on May 23, 2019

Get link
Facebook
Twitter
Pinterest
Email
Other Apps

a b c d a f
a 1 1 1 1 1 1
c 1 1 2 2 2 2
b 1 2 2 2 2 2
c 1 2 3 3 3 3
f 1 2 3 3 3 4

algorithms dynamic programming

Get link
Facebook
Twitter
Pinterest
Email
Other Apps

Comments

Post a Comment

Popular Posts

System Design: LRU Cache

Problem Statement A cache is a in-memory hardware which is designed for fast access. All cache has memory limit which requires cache eviction policy. Basically whenever the memory of cache is full, we use policy to delete an item to make space for the new item. There are many cache eviction policies: First In First Out Most/Least Recently Used Most/Least Frequently Used Random Replacement Today we're going to discuss about LRU. LRU is a cache eviction policy in which we remove the Least Recently Used item. Here Least Recently Used means the item that was accessed least recently. Lets take an example of a LRU cache which holds 5 items and allows following operations: Insert(item) Get(item) Delete(item) Insert(item) Inserts an element. As per LRU this is the most recently used item. If the cache is full then the Least Recently Used item is deleted to make space for the new item. Get(item) Reterieves an item. As per LRU the item retreived becomes the most recently used item. This c

Binary Search

We want to search a million records in a database. How will you do it ? Well, Brute Force ? Fun Bob: Think Again. Okay. So let's take a list which is, well, less than a million: [ 1 2 3 4 5 6 7 8 9 10 ] Then go through each element and compare it with the search element. What's the time complexity ? Why the long faces, it's only O(N). Let's run it on my million records database. *Gulp*. We know that the array is sorted. We can leverage that information and try to come up with a solution. If we divide the array into blocks and search the blocks instead of elements we can save a lot of lookups. Now what's a block you say. We can divide the array into ranges, [1,5], [6, 10]. These ranges represents blocks. Block 1: 1 to 5 Block 2: 6 to 10 The element can belong to one of these two blocks. If the search element is 3 we know it won't be in Block 2. We again divide Block 1 into two blocks. Block 3: 1 to 2 Block 4: 3 to 5 Again 3 canno

Words of a once misguided soul in SQL

Over these months I have noticed that a SQL developer must know these following things which gets unnoticed very easily: The sole purpose of using OUTER keyword in FULL, RIGHT or LEFT join is to improve code readability. Period. Many times you have noticed that you can specify a LEFT/RIGHT/FULL in two ways : They will produce the same result in the same amount of time under similar circumstances. The only difference is code readability, in latter case its more explicit than in the former. Also OUTER joins collectively refers to cases where the resultset can contain values which are out of the scope of the conditions specified. Same thing applies to using INNER keyword in JOINS. Interchanging conditions in WHERE clause with that in ON clause while using INNER JOINS won't effect the result set but in case of OUTER JOINS it will. Lets say you have a query like this : First of all if this query had INNER JOIN instead of LEFT OUTER JOIN then even if you interchange the condit

Powered by Blogger