Datastructures

Delete the node given position of the node to be deleted and head of the list Sample input1: position = 0, 1->2->3->4 Sample output1: 2->3->4 Sample input2: position = 2, 1->2->3 Sample output2: 1->3 Solution: 1) If position is 0 (head node) then make the head to point to  head->next 2) If position is greater than one then find the current node to be deleted by traversing the list also store the reference of previous node. 3) Make previous->next to point to current->next. Code: Node Delete(Node head, int position) {     if(position == 0){         head = head.next;         return head;     }     Node current = head;     Node prev=head;     for(int i=1; i<=position; i++){         prev = current;         current = current.next;     }     //if the position is greater than t...

Delete 3 in the linked list 1->2->3->5 to make it like 1->2->5 Solution: 1) Find the previous node and current node of the list to be deleted. 2) Make the next of the previous node to point to current->next. Illustration: Special cases: i) If the head is null then return without any further operations. ii) If the given key is in the head node itself then make the head to point to head->next. iii) If we finished up to tail and the key is not present in the list then return. Code: void delete(int key){     //case (i)     if(head == null)        return;     //case (ii)     if( head.data == key){        head = head.next;     }     Node previous = head;     Node current = head.next;     while(current != null && current.data != key){          ...

Introduction:     Linked list is a linear data structure. It consists of nodes. Each node has data and pointer to the next node. Linked list is represented by it's head pointer. Representation of a node: class Node {       int data;       //reference to the next node       Node next;       //constructor to initialize the node       Node(int data){           this.data = data;           next = null;       } } Insertion : (i) insertion at the head of the linked list: Steps: 1) Create a node with given data. 2) Make the next of the node to point to head , so that we are preserving the pointer to next node. 3) Make the head to point to new node. Code: void Insert(Node head,int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } Illustration: Insertion of 1 at the head ...

Find the largest three elements in an array with O(1) space and O(n) time complexity Input: 5           1 2 3 4 5 Output: 3 4 5 Method: 1. Initialize three variables first, second and third with minimum value. 2. If you find an element greater than first element then move second to third, first to second and array element to first. 3. Else if you find an element greater than second element then move second to third and array element to second. 4. Else if you find an element greater than than third element then move that element to third position. Key point: We are using third variable like a temporary variable here. Because when we find an element to fit in one of first three positions then we definitely don't need that third element ever. Code: import java.io.*; import java.util.*; class ArrayMaxElements { public static void main (String[] args) { Scanner in = new Scanner(System.in); int first = Integer.MIN_VALUE; int second = Integ...

Array rotation Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements. Rotation of the above array by 2 will make array Input: 7 2 1 2 3 4 5 6 7 Expected Output: 3 4 5 6 7 1 2 Method 1: 1. store d elements in temporary array of size d. 2. Shift all other elements. 3. Restore temp array at the last. Time complexity  O(n) Auxiliary Space:  O(d) Code: ------------------------------------------------------------------------------------------------------- import java.util.*; import java.lang.*; import java.io.*; class ArrayRotation { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(); int d = in.nextInt(); int arr[] = new int[n]; int temp[] = new int[d]; int count = 0; for(int i=0; i<n; i++){    arr[i] = in.nextInt(); } for (int i=0; i<n; i++){    if(i<d)     ...

    In the above tree if you see node 1 the ancestors(nodes which are higher in hierarchy) are 3, 8. And for 4 the ancestors are 3,6 and 8. So the lowest(close to both nodes) common ancestor of 1 and 4 is 3.     Now for a given nodes v1 and v2 we have to find the lowest common ancestor of both nodes.     In binary search tree if a given value say v1 is lesser than the present node then it is definitely lies in the left subtree. Similarly if the given value is greater than the present node then it lies in the right subtree. Using this property we will solve the example problem as shown below. Solving the problem: We will follow the below steps to find the lca of 1 and 4. 1. We will be starting with the root node which is 8. Both 3 and 4 is less than 8, so we will go to left subtree of 8. 2. current node is 3. Here 1 is less than 3 but 4 is greater than 3. This is the key point of the problem. At node 3 one value is less other va...