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...