SDE - 1

Approach 1 :

1) Count the number of nodes in a linked list.
2) Delete n/2’th node using the simple deletion process. 

TC : O(N) , N=number of nodes in the Linked List
Two traversals of the linked list is needed

SC : O(1)


Approach 2 :

1) The idea is to use two pointers, slow_ptr, and fast_ptr. 
2) Both pointers start from the head of list. When fast_ptr reaches the end, slow_ptr reaches middle. 
3) Keep track of the previous middle so the middle node can be deleted.

TC : O(N)
Single Traversal of the linked list is required

SC : O(1)

Approach 1 (Recursive) :

1) Compare the head of both linked lists.
2) Find the smaller node among the two head nodes. The current element will be the smaller node among two head nodes.
3) The rest elements of both lists will appear after that.
4) Now run a recursive function with parameters, the next node of the smaller element, and the other head.
5) The recursive function will return the next smaller element linked with rest of the sorted element. Now point the next of current element to that, i.e curr_ele->next=recursivefunction()
6) Handle some corner cases. 
6.1) If both the heads are NULL return null.
6.2) If one head is null return the other.

TC : O(N), where N=length of the Linked List
SC : O(N)


Approach 2 (Iterative) :

1) Traverse the list from start to end.
2) If the head node of second list lies in between two nodes of the first list, insert it there and make the next node of second list the head. Continue this until there is no node left in both lists, i.e. both the lists are traversed.
3) If the first list has reached end while traversing, point the next node to the head of second list.

Note: Compare both the lists where the list with a smaller head value is the first list.

TC : O(N), where N=length of the Linked List
SC : O(1)

Approach 1 (Brute Force) :
In this approach, we make use of an idea based on selection sort.

1) Traverse over the given numsnums array choosing the elements nums[i]. For every such element chosen, we try to determine its correct position in the sorted array. For this, we compare nums[i] with every nums[j], such that i < j < n.

2) If any nums[j] is lesser than nums[i], it means both nums[i] and nums[j] aren't at their correct position for the sorted array. Thus, we need to swap the two elements to bring them at their correct positions.

3) Instead of swapping, just note the position of nums[i] (given by i) and nums[j] (given by j). These two elements now mark the boundary of the unsorted subarray(atleast for the time being).

4) Out of all the nums[i] chosen, we determine the leftmost nums[i] which isn't at its correct position. This marks the left boundary of the smallest unsorted subarray(l).

5) Similarly, Out of all the nums[j] considered for all nums[i] we determine the rightmost nums[j] which isn't at its correct position. This marks the right boundary of the smallest unsorted subarray(r).

6) Therefore, the length of the smallest unsorted subarray = r−l+1.

TC : O(N^2)
SC : O(1)


Approach 2 (Using Sorting) :

1) We can sort a copy of the given array nums, say given by nums_sorted. 
2) Then, if we compare the elements of nums and nums_sorted, we can determine the leftmost and rightmost elements which mismatch. 
3) The subarray lying between them is, then, the required shorted unsorted subarray.

TC : O(N*log(N))
SC : O(N)

The idea is to first separate all the bits that are present at the odd positions and the even positions. After separating the bits at even and odd positions, we can swap them by right shifting the number formed by taking bits at even position by 1 bit and left shifting the number formed by taking bits at the odd position by 1 bit. So, our final result will be the Bitwise OR of the two values. To get the bits at the odd position, we will need to toggle all the bits at even position in the binary representation of N off, while keeping the bits at odd positions unchanged, to do so, we will take the Bitwise AND of N with the binary number of the form of  01010101… As taking the Bitwise AND will make all even bits 0 while the odd bits will remain the same. As the number of bits in our input is at most 32, so will take the number  01..(repeated16 times), which can be represented as 0x55555555 in hexadecimal form. Similarly, to get the bits at even positions, we will take Bitwise AND of N with 0xAAAAAAAA.

Steps:

1. Let oddPositionBits and evenPositionBits be the two variables that store the value of bits at odd positions and even positions respectively.
2. Set oddPositionBits as the Bitwise AND of N and 0x55555555.
3. Set evenPositionBits as the Bitwise AND of N and 0xAAAAAAAA.
4. Left shift oddPositionBits by 1 bit and right shift evenPositionBits by 1 bit. In this step, we are swapping the positions of the odd bits and the even bits.
5. Let ans be the variable that stores the final result. Set ans as the Bitwise OR of oddPositionBits and evenPositionBits. Here, we are recombining the od bits and the even bits after swapping them.
6. Return the variable ans.

Answer : 

Destructor : A destructor in C++ is a member function of a class used to free the space occupied by or delete an object of the class that goes out of scope. A destructor has the same name as the name of the constructor function in a class, but the destructor uses a tilde (~) sign before its function name.

Virtual Destructor : A virtual destructor is used to free up the memory space allocated by the derived class object or instance while deleting instances of the derived class using a base class pointer object. A base or parent class destructor use the virtual keyword that ensures both base class and the derived class destructor will be called at run time, but it called the derived class first and then base class to release the space occupied by both destructors.

Approach : 

1) We initialise two integer variables ‘si’ and ‘ei’ denoting the start index and the end index to 0 and N -1, respectively. 

2) We also initialise another integer variable ‘pivot’ to 0 that stores the index of the pivot element.

3) In the modified binary search, we will compare ARR[mid] with ARR[0] because if ARR[mid] < ARR[0], then it is guaranteed that ‘pivot’ is mid or present on its left side. Else, ‘pivot’ is present on the right side.

4) The modified binary search to find the pivot point:

4.1) We find the index of the middle element of ARR as mid = si + (ei - si) /2 .
4.2) If (ARR[mid] < ARR[0])
i) pivot = mid
ii) We update the end index ei, ei = mid - 1.
4.3) Else
i) We update the start index si, si = mid + 1.


5) After finding the pivot, we can easily locate the two sorted parts of ARR, one starting from 0 to pivot - 1 and the other from pivot to N - 1. 

6) Now, we apply binary search in that sorted part of ARR in which the element K may lie. If K is present, we return its index. Else, we return -1.

TC : O(log(N)), where N=size of the array
SC : O(1)

Approach : 

1) Select any splitting value, say L. The splitting value is also known as Pivot.
2) Divide the stack of papers into two. A-L and M-Z. It is not necessary that the piles should be equal.
3) Repeat the above two steps with the A-L pile, splitting it into its significant two halves. And M-Z pile, split into its halves. The process is repeated until the piles are small enough to be sorted easily.
4) Ultimately, the smaller piles can be placed one on top of the other to produce a fully sorted and ordered set of papers.
5) The approach used here is reduction at each split to get to the single-element array.
6) At every split, the pile was divided and then the same approach was used for the smaller piles by using the method of recursion.

Technically, quick sort follows the below steps:

Step 1 − Make any element as pivot
Step 2 − Partition the array on the basis of pivot
Step 3 − Apply quick sort on left partition recursively
Step 4 − Apply quick sort on right partition recursively


//Pseudo Code :

quickSort(arr[], low, high)
{
if (low < high)
{
pivot_index = partition(arr, low, high);
quickSort(arr, low, pivot_index - 1); // Before pivot_index
quickSort(arr, pivot_index + 1, high); // After pivot_index
}
}

partition (arr[], low, high)
{
// pivot - Element at right most position
pivot = arr[high]; 
i = (low - 1); 
for (j = low; j <= high-1; j++)
{

if (arr[j] < pivot)
{
i++; 
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}

Complexity Analysis : 

TC : Best Case - O(N*log(N))
Worst Case - O(N^2)

SC : Average Case - O(log(N))
Worst Case - O(N)

Steps : 

1) Create a recursive function that takes a node and the two values n1 and n2.
2) If the value of the current node is less than both n1 and n2, then LCA lies in the right subtree. Call the recursive function for the right subtree.
3) If the value of the current node is greater than both n1 and n2, then LCA lies in the left subtree. Call the recursive function for the left subtree.
4) If both the above cases are false then return the current node as LCA.

TC : O(h), where h=Height of the BST
SC : O(h)

Algorithm:

spiralPrint(matrix[][], rows, cols):
1) Initialize two variables ‘R’, ‘C’ with 0 to denote the lowest boundary for row and column of the submatrix remaining. Also, rows and cols denote the maximum boundary for the submatrix remaining.
2) While(R < rows and C < cols) :
2.1) Print the first row from left to right of the remaining submatrix i.e from column ‘C’ to ‘cols’, print the 
elements of the Rth row. Increment ‘R’ by 1.
2.2) Print the last column from top to bottom of the remaining submatrix i.e from row ‘R’ to ‘rows’, print 
the elements of the (cols)th column. Decrement ‘cols’ by 1.
2.3) Print the last row from right to left of the remaining submatrix i.e from column ‘cols’ to ‘C’, print the 
elements of the (rows)th row. Decrement ‘rows’ by 1.
2.4) Print the first column from bottom to top of the remaining submatrix i.e from row ‘rows’ to ‘R’, print 
the elements of the Cth column. Increment ‘C’ by 1.

TC : O(N*M), where ‘N’ is the number of rows and ‘M’ is the number of columns of the matrix.
SC : O(1)

Answer : 

The Diamond Problem : The Diamond Problem occurs when a child class inherits from two parent classes who both share a common grandparent class i.e., when two superclasses of a class have a common base class.

Solving the Diamond Problem in C++ : The solution to the diamond problem is to use the virtual keyword. We make the two parent classes (who inherit from the same grandparent class) into virtual classes in order to avoid two copies of the grandparent class in the child class.

Answer : 
There are two main types of semaphores i.e. counting semaphores and binary semaphores.

1) Counting Semaphores : 
These are integer value semaphores and have an unrestricted value domain. These semaphores are used to coordinate the resource access, where the semaphore count is the number of available resources. If the resources are added, semaphore count automatically incremented and if the resources are removed, the count is decremented.

2) Binary Semaphores : 
The binary semaphores are like counting semaphores but their value is restricted to 0 and 1. The wait operation only works when the semaphore is 1 and the signal operation succeeds when semaphore is 0. It is sometimes easier to implement binary semaphores than counting semaphores.