Posts

Recursion

-
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
1 comment
Read more

Priority Queue

-
A priority queue is an abstract data structure and it is similar to the regular queue . Each element in the priority queue has a priority associated with it. In the priority queue, we dequeue the highest priority element before the lowest priority and if the priority is the same then as per the insertion order it will dequeue. One of the best real-time applications, CPU Scheduling is basically done the same thing. If the higher priority task occurs then it interrupts the ongoing process and shares the resources to the higher priority. We have taken the example of RabbitMq in the queue blog . In RabbitMq, we push elements in the queue and wait until the subscriber subscribes to the messages. Suppose, If there are n messages that are pending to subscribe and one of the messages needs to be processed as soon as possible. If we have pushed the message by setting the high priority in the queue then it will process first then rest of them. Some of the languages implement the priority queue
Post a Comment
Read more

Deque

-
Image
Double Ended Queue is an abstract data structure that allows us to enqueue from both of the sides but dequeue can only be done either of the side (rear or front) . We have to decide before writing a code whether we are allowing dequeue from front or rear. We can implement the deque using an Array or Linked List . It is easy to create Deque using a linked list but in an array, we need to very careful to implement it.  Dequeue From Rear Dequeue From Front NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it as an Object. Deque Implementation using an Array #1 Initialization of Custom Deque - O(1) public class CustomDeque< T > { T [] data ; int length , front , rear , capacity ; public CustomDeque( T [] data) { this . data = data; capacity = data. length ; } } #2 Adding Element at the Front - O(1) public void addFirst( T ele) { if (ele == null ) throw new NullPointerExceptio
Post a Comment
Read more

Queue

-
Image
A  Queue  is a data structure that holds the element, will insert from the rear of the queue, and remove from the front of the queue. Insertion is known as Enqueue and Deletion is known as Dequeue. It follows the First In First Out(FIFO) or Last In Last out(LILO). There are many problem statements where we generally use the queue to hold the object and process it whenever it is required. One of the most used application is RabbitMq in real-time projects. Let's take an example, there are 1 publisher and 1 subscriber, publisher publish an object into the queue, and the subscriber will subscribe and remove it from the queue. We can implement a queue using an Array or Linked List .                                                                                NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. Queue Implementation using Array #1 Initialization of Custom Queue public class CustomQueue<
Post a Comment
Read more

Stack

-
Image
The Stack  looks more like a container which holds the element, will insert element from the top and remove from the top only. It follows the Last in First out(LIFO)  or First In Last out (FILO)  approach. Java uses the method stack area to hold the state of the method if some method calls another method inside it.   public class Demo { public static void main(String[] args) { new Demo().firstCall(); System. out .println( "Main" ); } public void firstCall() { secondCall(); System. out .println( "First" ); } private void secondCall() { thirdCall(); System. out .println( "Second" ); } private void thirdCall() { System. out .println( "Third" ); } } This is how it maintains the method call in the method stack area. It will remove from the top every time and complete its method execution and remove next's top from the stack. This process will continue until th
2 comments
Read more

Circular Doubly Linked List

-
Image
Now, We have a good understanding of the Linked list and its internal working of it. In a Doubly linked list, we have next and previous pointer but the head's previous and tail's next are null. If we reach the end of the linked list then it will terminate. This might be a drawback in some of the use cases, to overcome this situation we will use the circular doubly linked list. Suppose, We have sent data into the network, data is divided into the packet and each packet has its own ordered unique identification number. If the packet is coming late then it will search the position by traversing forward and backward and placed the packet in an accurate position. This could be one of the real-time examples of using the Circular Doubly linked list. NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. #1 Custom Doubly Linked List Class class Node< T > { T data ; Node< T > next ; Nod
Post a Comment
Read more

Find Nth Node from End of the Singly linked list.

-
Image
Given N size node in the Singly Linked list and you have to find the kth node's value from the end.  Suppose, You have been provided the above Singly Linked List and the interviewer asks you to return 2nd last element from the linked list. Your response will be 7 and if the kth element is greater than the size of the Linked list then return -1. -1 will represent that the kth element is not present. This problem is repeatedly asked by many of the product based companies and the interviewer will grill you on it. He will add some constraint on the fly and asks you to solve it optimize way. Suppose, If we are going to solve this problem what would be the solution that comes into our mind. A Singly linked list holds the count of the node in the size variable, We will iterate from the head node to size - kth node and return the kth node's value. Once you give this solution to the interviewer, he/she will directly tell you that there is no size variable available in this custom Singl
Post a Comment
Read more