Knuth Morris Pratt (KMP)

Introduction

KMP is a string searching algorithm using pattern searching. If subpattern appear more than once KMP is effecient. If two adjacent letters match, it improves the count of longest proper prefix and suffix count. Otherwise it reduces to previous value. Once full pattern has been found, for the next character match, we go to previous value of lps, so that we only need to compare single character. Therefore time complexity of KMP algorithm is O(n)

Rabin Karp Algorithm

Introduction

Rabin-Karp algorithm is one of the string searching algorithms. It uses hashing and sliding window technique to find pattern within the target text.

Algorithm

In the algorithm, we try to find the index where certain pattern starts. It returns -1, if the pattern was not found.

rabinKarp (T, P, d, q):

• T is the target text, where we search the Pattern
• d is a small integer which we use to calculate power for creating hash
• q is a prime number to get modulus, so that we don’t overflow in calculation

1. Calcuate h = d ^ m-1 (m is length of P)
2. Calculate initial t and p, with t = (d * t + T[i]) % q, do same for p
3. In a loop from i = 0 to m-n, check if t and p match. If it matches, check T.substring(i, i+m) equals to P. If so return i
4. For next iteration, while i < n-m, t = ((d * t - T[i] * h) + T[i+m]) % q, adjust q if negative
5. Average case for Rabin Karp Algorithm is O(n+m), but worst case is O(nm). Worst case is when P and T have same characters, thus same hash value.
6. To avoid hash colision, we could save all the different substrings in a list using same hash as key in a HashMap. We don’t use this in this example.

HIndex II (LC)

Given sorted array of citations return HIndex. HIndex is “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.” (wikipedia).

Implement Linked List data structure

Linked List is one of the most important data structures. We can perform several operations on this simple data structure like addition of new data at the beginning of the linked list(head) or at the end (tail) of the linked list, insert data before certain node, insert after certain node, delete nodes, search certain values etc. Efficiency of linked list mostly depends upon its usage. Linked List can be used to implement other data structures like queue, stack. In general linked list is not used if data is to be searched, as linked list does not have index references. To get to a particular node, we need to use pointers to next node and traversed all the way to the particular node from the beginning of the list (O(logn)) . However, since linked list is based on pointers, adding element to the head of the linked list, inserting nodes at some location (if we have reference to neighboring nodes) is very efficient. If data has some structure and we have index to particular cell, array might be more efficient data structure . However, unlike array inserting new data to linked list does not require moving data as required in array. Therefore insertion would be more efficient. In this tutorial, we will see a linked list implementation of few operations like insertion, deletion etc.

Implement basic hash map using chaining (LC)

Hash map is a key value pair data structure, where a value is associated to a particular key. In this tutorial I will discuss a basic implementation of hash map. I will create an array of list of limited size and use a hashing method to map the given key to each bucket. I will also use a Pair class to save the key and value in that list, so that element can be accurately searched later on. If the hashing method is random or fair, the elements will be distributed evenly, thus making hash map O(1) for insertion, update, search and deletion. In this implementation, the hashing method is very simple, I will use a modulus of key to the size of the bucket. If all the keys map to same bucket, a hash map can be as inefficient as a linked list O(n). Below is the implementation

Binary Search Algorithm

Binary search algorithm is a searching algorithm, where a particular element is searched in a sorted array. We can use linear search to search the element, starting at index 0 all the way to n-1. However, this process takes O(n) running time. On a sorted array, we can reduce the search time to O(logn) by reducing the search space into half the array in each iteration. We can use both iterative or recursive approach for this algorithm.

Popular Sorting Algorithms

In this post, I will discuss 3 popular sorting algorithms. Understanding them is crucial not only for sorting data, but also to use some of similar techniques to solve a wide range of algorithms. In this post I will describe the details of QuickSort, MergeSort and HeapSort.

Russian Doll Envelopes (LC)

You have number of envelopes with width and height, find how many smaller envelopes can fit on larger. Width of larger envelop must be strictly larger.

E.g For envelopes

int[][] arr = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};

We can fit {2, 3} -> {5, 4} -> {6, 7} => 3

We first sort the array and then use Longest Increasing Subsequence to get the number of dolls that fit. While sorting, if two widths are equal, we sort the heights in descending order, as we want to use higher number first in LIS, so that shorter number is not used twice for calculating the length, as {6, 4} does not fit on {6, 7}, so we only need to include {6, 7}

Python Tutorial (Basics): Note

This tutorial is a note for Learn Python – Full Course for Beginners youtube tutorial from freeCodeCamp.org