List of few algorithm that come handy. Not that they are super important for interview or anything, but the mainly for knowledge sake.
 Kadane Algorithm – Largest Sum Contiguous Subarray Code Youtube
The idea is simple. At each index of array we check if what’s the maximum subarray till now. The max subarray can be either the currentindexelement alone or the sum previous subarray index + the current index.
At each index we check what’s the maximum subarray that we have found instead of storing the sum in another array.
import java.lang.*; > to use the Math.max collection.  Boyer–Moore majority vote algorithm Youtube Code
Application – Find Majority Element in an Array.  Sieve of Eratosthenes – Wiki – Given a number n, print all primes smaller than or equal to n. The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes. Code.
The problem with this algo is the space requirement.
We initially create an array equal to the size of n. Initialize all array index with a false flag. Now start looping through the array starting from i = 2(1 is already prime). We process only i which are marker as false. For each i’s factor mark all the array index as false. This will be a nested loop. Keep doing it till i < =n;
The index left as false are the prime number.  Pigeonhole Principle – simple but very helpful in solving many problem. Read few here.
 Brian Kernighan’s Algorithm – Count set bits in an integer
 Birthday ParadoxBirthday Paradox
 The Lazy Caterer’s Problem – Given an integer n, denoting the number of cuts that can be made on a pancake, find the maximum number of pieces that can be formed by making n cuts(pieces can be of unequal size). Wiki
Thus, the total number of pieces after n cuts isThis recurrence relation can be solved. If ƒ(n − 1) is expanded one term the relation becomes

{\displaystyle f(n)=n+(n1)+f(n2).\,}
Expansion of the term ƒ(n − 2) can continue until the last term is reduced to ƒ(0), thus,
Since {\displaystyle f(0)=1}, because there is one piece before any cuts are made, this can be rewritten as
This can be simplified, using the formula for the sum of an arithmetic progression:

Advertisements