DS4Fun

Let's do the implementation and understand it in a deep-dive. We will go step-by-step and implement the most useful method. Declare and Initialization Phase- O(1) private int currentRow = 0 ; private int currentColumn = 0 ; private int maxRow , maxColumn ; private int [][] nums ; private int maxElement ; public MultiDimensionArray( int maxRow, int maxColumn) { this . maxRow = maxRow; this . maxColumn = maxColumn; nums = new int [maxRow][maxColumn]; maxElement = maxRow*maxColumn; } Add Element- O(1) public void add( int value) { if (size() <= maxElement ) { if ( currentColumn <= maxColumn - 1 ) { nums [ currentRow ][ currentColumn ++] = value; } else { if ( currentRow < maxRow - 1 ) { currentRow ++; currentColumn = 0 ; } nums [ currentRow ][ currentColumn ++] = value; } } else throw new ArrayIndexOutOfBoundsException(); } Update th

Let's do the implementation and understand it in a deep-dive. We will go step-by-step and implement the most useful method. Declare and Initialization Phase- O(1) int [] nums ; int maxCapacity ; int size = 0 ; public Array( int maxCapacity) { this . maxCapacity = maxCapacity; nums = new int [maxCapacity]; } Add Element- O(1) private void add( int value) { if ( size < maxCapacity ) { nums [ size ++] = value; } else throw new ArrayIndexOutOfBoundsException( size ); } Add Element in a particular and shift all the elements to the right- O(n) private void add( int index, int value) { if ( size < maxCapacity && index > 0 ) { int tempIndex = size ; while (tempIndex > index) { nums [tempIndex] = nums [--tempIndex]; } nums [index] = value; size = (index > size ) ? index + 1 : size + 1 ; } else throw new ArrayIndexOutOfBoundsException(); } Update the element v

An array is a collection of homogenous data stored at the contiguous memory locations. Each element is uniquely identified by its index value. An array is of a fixed size, once it is initialized with a number of an element is allowed then it won't add more than it's capacity. Let's analyze the problem when we come up with this solution. Supposedly, you have to declare and initialize the same data type multiple variables in a program. What do you think, how easy could it be to remember all the names? To overcome these types of problems, we came with the solution of an array. There are two types of array. Single Dimension Array Multi Dimension Array 2D Array 3D Array and so on. Java supports 255 D Array but in actual we mainly focus on 1D and 2D Array. One-Dimension Array (1D Array) 1D Array conceptually means that you have a single row with multiple columns and each column has the same size and they are contiguous by nature. In the example below, you can cle

Cache Replacement LRU Algorithm - (Least Recently Used) Least Recently Used algorithm, the name itself represents its behavior. When we use this algorithm with the cache replacement policy, it will always remove the least used page from the cache and make space for the currently used page. Based on the above statement, we have to think about the implementation of the same. We need a data structure where we have to add all the recently used data from the tail and remove it from the head. For Example:- We can store a maximum of 3 pages in our cache. Suppose, we have the request of pages as given below. 3 , 2 , 1 , 0 , 2 , 3 , 7 , 4 , 7 Cache Frame 2 1 0 2 3 7 4 7 1 2 2 1 0 2 3 7 4 0 3 3 3 2 1 0 2 3 3 Page Status Cache Miss Cache Miss Cache Miss Cache Miss Cache Hit Cache Miss Cache Miss Cache Miss Cache Hit We will follow the steps to push the missing pages into the cache for the performance. If the page is found then remove it and again push it on the top. If the size o

Cache Replacement FIFO Algorithm - (First In First Out) Before, we understood how the cache replacement algorithm works using FIFO. We will just look for a while to understand the FIFO with the layman term. Suppose a company running a seminar and max capacity of the seminar hall is 100 employees. They have decided whoever comes first they will get the entry and once's seminar hall is full then wouldn't allow anyone. There is no priority to anyone or any designation. So, we will implement a cache replacement algorithm using the Queue abstract data type. We can implement a queue using ArrayList or LinkedList. Let's do the code and understand the implementation of the algorithm. Implement Cache Replacement FIFO policy using ArrayList import java.util.Arrays; import java.util.List; import java.util.Optional; /** * @author Chandra Shekhar Paatni on 26/04/20 */ public class CacheReplacementFIFO< T > { T [] cacheReplacementFIFOS ; int index = - 1 ; pu

A cache is secure storage, where we store frequently used data/pages in a system. It gives us valuable advantages with respect to performance. Whenever we look at something in a system, it stores a duplicate copy of data into the cache and next time onward it will serve from the cache only until data is modified. It improves our performance in terms of recently used data from the cache instead of the main memory. There are two main terminologies used:- Cache hit :- If data found in a cache. Cache miss :- If data is not found in a cache. Cache has some limitations with respect to size. Whenever it is full, the respective algorithm will discard the item to make space for new data. Cache Replacement algorithms/policies are optimizing instructions to make a cache work with low latency and high throughput . We will discuss some of the cache replacement algorithms on the coming blog with their implementation.

The process in which a function calls itself and only works where we call the same operation multiple times with different inputs. In every call, we try to make the problem smaller. There must be a base case where the system will stop the recursion and give you a result back. It internally stores the recursion state in the method call stack. If there is no base condition in the recursion method then it will go into an infinite loop and you might face the StackOverflow Exception . There are several types of recursion:- Head Recursion Tail Recursion Tree Recursion Nested Recursion Head Recursion It will call recursively first then at the end do all the computation. private static int factorial( int number) { return (number== 1 )? number : number* factorial (number- 1 ) ; } factorial(5) (5* factorial(5-1)) (5* (4* factorial(4-1)) (5* (4* (3*factorial(3-1))) (5* (4* (3* (2*factorial(2-1)))) (5* (4* (3* (2* (1*1))))) output = 120 Tail Recur

We are now solving a problem which is asked by many of the product based companies. An interviewer will ask you to construct a binary search tree using a preorder traversal array. Before we proceed with this problem, let's recall the binary search tree with below-mentioned points:- The right subtree of a node contains only nodes with keys that are greater than the node's key. The left subtree of a node contains only nodes with keys that are lesser than the node's key. We have to check on each node with the above conditions. Quadratic Solution O(n 2 ) public static TreeNode bstFromPreorder( int [] preorder) { // Initialize the treenode TreeNode treeNode = new TreeNode(); // Check if the preorder array does contain value if (preorder. length > 0 ) treeNode. val = preorder[ 0 ]; // Iterate over the 1 to preorder length for ( int i = 1 ; i < preorder. length ; i++) {

When we use the big-θ notation bounds, a function from above and below; so it defines the exact asymptotic tight bound. Average case analysis. Tight bound of an algorithm. O(g(n)) - {f(n): there exist constants c1, c2 & n 0 such that 0<=c1.g(n) <= f(n) <= c2.g(n) for n>=n 0 }. Once n gets large enough, the running between c1.g(n) and c2.g(n). Let's understand it with the help of the program. private boolean searchValue( int [] n, int targetValue) { for ( int i = 0 ; i < n. length ; i++) { if (n[i] == targetValue) return true ; } return false ; } As per the above program, It will never go beyond the limit of θ(n) runtime analysis in the large value of n. There are two basic rule for Big-Theta (θ):- Drop lower order terms. Drop constants. If T(n) = 2n 2 + 2 then it will be 0 <= 2n 2 <= 2n 2 + 2 <= 3n 2   and it mean θ(n 2 ).

Big-O notation Worst-case analysis. Upper bound of an algorithm. O(g(n)) - {f(n) : there exist constants c and n 0  such that 0<=f(n)<=cg(n) for all n >= n 0 } It is commonly used to calculate time analysis of an algorithm, it will give us an upper bound limit which doesn't exceed any input size. You can clearly see in the below diagram after a particular size of the input (n 0  ) after then the f(n) always lies in or below the c.g(n). There are two basic rules for Big-Oh (0) Drop lower order term Drop constants Let's understand the above rules in an example:- int a = 1 ; // O(1) int b = 2 ; // O(1) int c = 3 ; // O(1) for ( int i = 1 ; i <= n; i++) { // O(n + 1) for ( int i1 = 1 ; i1 <= n; i1++) { // O(n +1) a = i*i1; // O(1) b = i*i1; // O(1) c = i*i1; // O(1) } } for ( int i = 0 ; i < n; i++) { // O(n) a *= i; // O(1) b *= i; // O(

We are now solving a problem which is asked by many of the product based companies. They always want you to give a proper solution with all edge cases covered.However, an array sorted in ascending is rotated (i.e., [0,1,2,3,4,5,6,7] might become [4,5,6,7,0,1,2,3]). Constraints No duplicate element in an array. Runtime complexity must be in the order of O(log n). If found then return index otherwise return -1. Example 1: Input: nums = [4,5,6,7,0,1,2], searchElement = 0 Output: 4 Linear Search Solution- O(n) time complexity It comes to our mind easily to check each element of an array until it finds it or till the array reaches the end of the index. class Solution { public static void main(String[] args) { System. out .println( search ( new int []{ 4 , 5 , 6 , 7 , 0 , 1 , 2 }, 0 )); } public static int search( int [] nums, int searchElement) { if (nums. length != 0 ) { for ( int i = 0 ; i < nums. length ; i++) {