Bits of code & design

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set. A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. Note that it is possible to color a cycle graph with even cycle using two colors. We can solve this problem using  Breadth First Search (BFS). Discussion : public static boolean isBipartiteUtil ( int G [][], int src , int colorArr []) { colorArr [ src ] = 1 ; LinkedList < Integer > q = new LinkedList < Integer >(); q . add ( src ); while (! q . isEmpty ()) { int u = q . poll (); if ( G [ u ][ u ] == 1 ) return false ; ...

Following is one useful java template that I use for competitive programming import java.io.BufferedReader ; import java.io.IOException ; import java.io.InputStreamReader ; import java.io.PrintWriter ; import java.math.BigInteger ; import java.util.* ; public class Test implements Runnable { //write logic in this method private void solve () throws IOException { //writer.println(your_answer); } //main method public static void main ( String [] args ) { new Test (). run (); } BufferedReader reader ; StringTokenizer tokenizer ; PrintWriter writer ; public void run () { try { reader = new BufferedReader ( new InputStreamReader ( System . in )); tokenizer = null ; writer = new PrintWriter ( System . out ); solve (); reader . close (); writer . close (); } catch ( Exception e ) { e . printStackTrace (); System . exit ( 1 ); } } int nextInt () thr...

Dijkstra's algorithm finds the shortest path from one node to all other nodes in a weighted graph. Its like breadth-first search (BFS), except we use a priority queue instead of a normal first-in-first-out queue. Each item's priority is the cost of reaching it. Time complexity : Dijkstra's algorithm using a binary min-heap as a priority queue is O((E+V)logV) . A directed graph is weakly connected if replacing all of its directed edges with undirected edges produces a connected undirected graph. If we assume that the input graph is weakly connected, then the graph must have at least V-1 edges. This implies that V is in O(E), which means we can simplify the running time above to O(ElogV) . Sample Java code : class pair implements Comparable < pair >{ int first ; int second ; public pair ( int a , int b ){ first = a ; second = b ; } public int compareTo ( pair a ){ return this . second - a...

Design uber, ola or lyft https://www.youtube.com/watch?v=J3DY3Te3A_A https://www.youtube.com/watch?v=umWABit-wbk&t=1618s https://www.youtube.com/watch?v=fgIgOU0yi0w https://www.youtube.com/watch?v=jItLuOTsCX4&t=2582s Design whats app or chat system https://www.youtube.com/watch?v=L7LtmfFYjc4 https://www.youtube.com/watch?v=5m0L0k8ZtEs https://www.youtube.com/watch?v=vvhC64hQZMk Design twitter or a social network platform  https://www.youtube.com/watch?v=wYk0xPP_P_8 https://www.youtube.com/watch?v=KmAyPUv9gOY Design distributed cache system https://www.youtube.com/watch?v=DUbEgNw-F9c&t=1770s https://www.youtube.com/watch?v=U3RkDLtS7uY https://www.youtube.com/watch?v=iuqZvajTOyA Design rate limiting system https://www.youtube.com/watch?v=mhUQe4BKZXs https://www.youtube.com/watch?v=xrizarXJgC8&t=694s https://www.youtube.com/watch?v=FU4WlwfS3G0 Design tinder https://www.youtube.com/watch?v=tndzLznxq40&t=744s https:...

Problem link Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent. Find the maximum coins you can collect by bursting the balloons wisely. Example :  Input: [3,1,5,8] Output: 167  Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []                       coins =  3*1*5     +  3*5*8    +  1*3*8    + 1*8*1   = 167 Discussion : The base case deals with only a single balloon, in which case the answer is straightforward - we just pop it and collect the coins for it. Assuming we have N balloons, how do we red...

Consistent Hashing is a distributed hashing scheme that operates independently of the number of servers or objects in a distributed  hash table  by assigning them a position on an abstract circle, or  hash ring . This allows servers and objects to scale without affecting the overall system. In other words,  It facilitates the distribution of data across a set of nodes in such a way that minimizes the re-mapping/ reorganization of data when nodes are added or removed. BENEFITS OF CONSISTENT HASHING: Enables Elastic Scaling of cluster of database/cache servers Facilitates Replication and partitioning of data across servers Partitioning of data enables uniform distribution which relieves hot spots Must Read Places: https://www.toptal.com/big-data/consistent-hashing https://towardsdatascience.com/consistent-hashing-simplified-7fe4e512324 https://www.acodersjourney.com/system-design-interview-consistent-hashing/ https://www.youtube.com/watch?v=zaRkO...

Given an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note : A transaction is a buy & a sell. You may not engage in multiple transactions at the same time (you must sell the stock before you buy again). Example : Input:   price[] = {10, 22, 5, 75, 65, 80} Output:  87 Buy at price 10, sell at 22, buy at 5 and sell at 80 Discussion :  public int maxProfit ( int [] priceList ) { int len = priceList . length ; if ( priceList == null || len < 2 ) return 0 ; int [] left = new int [ len ]; int [] right = new int [ len ]; left [ 0 ] = 0 ; int min = priceList [ 0 ]; for ( int i = 1 ; i < len ; i ++) { min = Math . min ( min , priceList [ i ]); left [ i ] = Math . max ( left [ i - 1 ], priceList [ i ] - min ); } right [ len - 1 ] ...

Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array. Discussion : - Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time  - One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.  Removing an element and adding a new element to min heap will take Logk time. So overall complexity will be O(k) + O((n-k)*logk) public void sortKSortedArray ( List < Integer > list , int k ){ PriorityQueue < Integer > pq = new PriorityQueue <>( list . subList ( 0 , k + 1 )); for ( int i = k + 1 ; i < list . size (); i ++){ System . out . print ( pq . poll () + " " ); pq . add ( list . get ( i )); } } ...

How does moving the tortoise to the beginning of the linked list, while keeping the hare at the meeting place, followed by moving both one step at a time, make them meet at starting point of the cycle? Discussion : We can easily understand this from below diagram : S - the non-loop part of the list X - the point where slow and fast pointers meet When two pointers are meet, slow pointer traveled S+X. what about the fast pointer? There are two ways to think about it. 1. Fast pointer traveled twice as much as slow pointer, which is 2*(S+X) 2.  Fast pointer traveled the same distance as slow pointer plus the distance of loop L , which is (S+X)+L This is interesting, because if you put these two together, 2*(S+X) = (S+X)+L simply it to S+X=L , which means S+X equals to the distance of the loop L. Therefore, at position X in the loop, keep moving S distance, then you are guaranteed to meet the start of the loop. Hope this helps :)

In Floyd's cycle-finding algorithm , Its mentioned that we have to take 2 pointers.  One pointer( slower/tortoise ) is increased by one and other pointer( faster/hare ) is increased by 2. When they are equal we find the loop and if faster pointer reaches null there is no loop in the linked list. But the question is why we increase faster pointer by 2. Why not something else? Discussion : We can answer this question with a simple proof. Let us suppose the length of the list which does not contain the loop be S , length of the loop be T and the ratio of fast pointer speed to slow pointer speed be K . Let the two pointers meet at a distance J from the start of the loop. So, the distance slow pointer travels = S+J . Distance the fast pointer travels = S+J+M*T (where M is the number of times the fast pointer has completed the loop). But, the fast pointer would also have traveled a distance K*(S+J) ( K times the distance of the slow pointer). Therefore, we get K*(S+...

Trie  Implementation (Insert, Search, Delete) Tries are an extremely special and useful data-structure that are based on the prefix of a string. They are used to represent the “Retrieval” of data and thus the name Trie. Using Trie, search complexities can be brought to optimal limit (key length).  public class Trie { private class TrieNode { Map < Character , TrieNode > children ; boolean endOfWord ; public TrieNode () { children = new HashMap <>(); endOfWord = false ; } } private final TrieNode root ; public Trie () { root = new TrieNode (); } public void insert ( String word ) { TrieNode current = root ; for ( int i = 0 ; i < word . length (); i ++) { char ch = word . charAt ( i ); TrieNode node = current . children . get ( ch ); if ( node == null ) { ...