SDE - 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) We will initialize the variable lowerLimit and upperLimit with the minimum and maximum value present in the array.

2) Iterate while upperLimit - lowerLimit is more than 2.
2.1) Set the variables mid1 with lowerLimit + (upperLimit - lowerLimit)/3 and mid2 with upperLimit - (upperLimit - lowerLimit)/3.

2.2) Initialize the variable cost1 with the cost of converting all array elements to mid1. You have to iterate the complete array to calculate cost1.

2.3) Similarly, find cost2 by keeping mid2 as the target value of all elements in the array.

2.4) If cost1 is less than cost2 then set upperLimit as mid2; otherwise, set lowerLimit as mid1.

3) Set target as (lowerLimit + upperLimit)/2 and cost as 0. The variable cost stores the minimum cost to convert all elements present in the array to target.

4) Iterate index from 0 to N-1.
4.1) Increment cost by an absolute difference of ARR[index] and target.

5) Return the variable cost.


TC : O(N * log(Max(ARR) - Min(ARR))) where N = size of the array.
SC : O(1)

Approach 1 (Brute Force) :

1) Create a variable ans, which stores the total number of subarrays. We will set the variable ans as 0.

2) Iterate index from 0 to N - 1.
 

3) Iterate pos from index to M - 1.
3.1) We will maintain a variable currentXor, which will store the XOR of all elements present in the current subarray. We will set currentXor as 0.
 

4) We will traverse num from index to pos. We will update currentXor with XOR of currentXor and ARR[num].
4.1) Check if currentXor is equal to X.
4.2) Increment ans by 1.

5) Return the variable ans.

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


Approach 2 (Using Hashing) :

1) Create a HashMap “prefXor” which stores the count of subarrays having a particular XOR value.
 

2) Create a variable “curXor” which stores the XOR for ‘i’ elements. Initialise it with zero. Also, create a variable called “ans” to store the count of the subarrays having XOR ‘X’.
 

3) Start iterating through given array/list using a variable ‘i’ such that 0 <= ‘i’ < n
3.1) Update the “curXor” i.e. curXor = curXor ^ arr[i]
3.2) Store the required value of the prefix Xor to make the XOR of the subarray ending at the current index equal to X i.e. req = X ^ curXor
3.3) Now add the count of prefix arrays with required xor i.e. ans = ans + prefXor[req]
3.4) Update the “prefXor” HashMap with the “curXor” i.e. prefXor[curXor] = prefXor[curXor] + 1


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

Approach 1 (Brute Force) :

Create an output array and and one by one copy all arrays to it. Finally, sort the output array using. This approach takes O(N Logn N) time where N is count of all elements.
 

Approach 2 (Using Min-Heap) :

1. Create an output array.

2. Create a min heap of size k and insert 1st element in all the arrays into the heap
 

3. Repeat following steps while priority queue is not empty.
3.1) Remove minimum element from heap (minimum is always at root) and store it in output array.
3.2) Insert next element from the array from which the element is extracted. If the array doesn’t have any more elements, then do nothing.

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

Approach :

1) Create a 2-D dp boolean vector(with all false initially) where dp[i][j] states whether s[i...j] is a palindrome or not and initilialise a variable ans=1 which will store the final answer.

2) Base Case : For every i from 0 to n-1 fill dp[i][i]=1 ( as a single character is always a palindrome ).

3) Now, run 2 loops first one from i=n-1 to i=0 (i.e., tarverse from the back of the string) and the second one from j=i+1 to n.

4) For every s[i]==s[j] , check if(j-i==1 i.e., if s[i] and s[ j] are two consecutive same letters) or if(dp[i+1][j-1]==1 or not i.e., if the string s[i+1,....j-1] is palindrome or not.

5) Because if the string s[i+1,....j-1] is a palindrome and s[i]==s[j] then s[i] and s[j] can be appended at the starting and the ending position of s[i+1,...j-1] and s[i...j] will then be a palindrome , so mark dp[i][j]=1 and update the answer as ans=max(ans , j-i+1).

6) Finally return the ans.

TC : O(N^2) where N=length of the string s
SC : O(N^2)

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)

OOP is used commonly for software development. One major pillar of OOP is polymorphism. Early Binding and Late Binding are related to that. Early Binding occurs at compile time while Late Binding occurs at runtime. In method overloading, the bonding happens using the early binding. In method overriding, the bonding happens using the late binding. The difference between Early and Late Binding is that Early Binding uses the class information to resolve method calling while Late Binding uses the object to resolve method calling.


Early Binding : In Early Binding, the class information is used to resolve method calling. Early Binding occurs at compile time. It is also known as the static binding. In this process, the binding occurs before the program actually runs. Overloading methods are bonded using early binding.


Late Binding : In Late Binding, the object is used to resolve method calling. Late Binding occurs at runtime. It is also known as dynamic binding. In this process, the binding occurs at program execution. Overridden methods are bonded using late binding.

1) Data abstraction is a very important feature of OOPs that allows displaying only the important information and hiding the implementation details.

2) For example, while riding a bike, you know that if you raise the accelerator, the speed will increase, but you don’t know how it actually happens.

3) This is data abstraction as the implementation details are hidden from the rider.

Data abstraction can be achieved through : 
i) Abstract class
ii) Abstract method

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.

1) Friend functions of the class are granted permission to access private and protected members of the class in C++. They are defined globally outside the class scope. Friend functions are not member functions of the class.

2) A friend function is a function that is declared outside a class but is capable of accessing the private and protected members of the class.

3) There could be situations in programming wherein we want two classes to share their members. These members may be data members, class functions or function templates. In such cases, we make the desired function, a friend to both these classes which will allow accessing private and protected data members of the class.

4) Generally, non-member functions cannot access the private members of a particular class. Once declared as a friend function, the function is able to access the private and the protected members of these classes.

Some Characteristics of Friend Function in C++ :

1) The function is not in the ‘scope’ of the class to which it has been declared a friend.
2) Friend functionality is not restricted to only one class
3) Friend functions can be a member of a class or a function that is declared outside the scope of class.
4) It cannot be invoked using the object as it is not in the scope of that class.
5) We can invoke it like any normal function of the class.