Software Engineer

The idea is to use a method similar to the merge sort algorithm. Like merge sort, divide the given array into two parts. For each left and right half, count the inversions, and at the end, sum up the inversions from both halves to get the resultant inversions.
Algorithm: 
1. Divide the array into two equal or almost equal halves in each step until the base case is reached.
2. Create a function merge that counts the number of inversions when two halves of the array are merged, create two indices i and j, i is the index for the first half, and j is an index of the second half. if a[i] > a[j], then there are (mid – i) inversions. because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j].
3. Create a recursive function to divide the array into halves and find the answer by summing the number of inversions is the first half, the number of inversions in the second half and the number of inversions by merging the two.
4. The base case of recursion will be when there is only one element in the given half.
5. Print the number of total inversions.

Time Complexity: O(NlogN), where N is the total size of the array
Space Complexity: O(N), where N is the total size of the array

For every digit in the number, make a new node and attach it to the previous node in the list. 
Steps:
1. Run a while loop while the number > 0. 
2. Extract digit from the number by num%10 and update number to num%10. 
3. Make a new node with its value as the digit and attach it at the end of the list created. 
4. Return the head of the list created.

Level order traversal can be used to solve this problem. Modify queue entries to store the node and the level of nodes. So, the queue node will contain a pointer to a tree node and an integer level. When we deque a node we can check the level of dequeued node. If it is same, set the right pointer of the node to the front node of the queue. 
Time Complexity : O(N) 
Space Complexity :O(N)

BFS can be used to solve this question. 
1. Start from the given start word and push it in queue. 
2. Maintain a variable to store the steps needed. 
3. Run a loop until the queue is empty : 
2.1 Traverse all words that are adjacent (differ by one character) to it and push the word in the queue. 
4. Keep doing so until we find the target word or we have traversed all words. Keep Incrementing the steps too. 
At last, if the target word is found return the number of steps or return 0 otherwise.

A simple approach would be to create a new arrays with size as sum of the sizes of both the arrays. Copy the elements of both the arrays in the new array and sort the array. 

A space optimized approach also exists. While traversing the two sorted arrays parallelly, if we encounter the jth second array element is smaller than ith first array element, then jth element is to be included and replace some kth element in the first array. 

Algorithm
1) Initialize i,j,k as 0,0,n-1 where n is size of arr1 
2) Iterate through every element of arr1 and arr2 using two pointers i and j respectively
if arr1[i] is less than arr2[j]
increment i
else
swap the arr2[j] and arr1[k]
increment j and decrement k

3) Sort both arr1 and arr2

The question can be approached using recursion. The person can reach nth stair from either (n-1)th stair or from (n-2)th stair. Hence, for each stair n, find out the number of ways to reach n-1th stair and n-2th stair and add them to give the answer for the nth stair. Therefore the expression for such an approach comes out to be : ways(n) = ways(n-1) + ways(n-2)

This is an expression for Fibonacci numbers only, where ways(n) is equal to Fibonacci(n+1). 
Time Complexity: O(2^n) 
The above solution can be optimised using dynamic programming. Maintain an array dp[] and fill it in bottom up manner using the relation :
Dp[i] = dp[i-1] + dp[i-2] for i>=2 
Time complexity: O(N)
Auxiliary Space: O(N)

Concept of Longest Increasing Subsequence can be used in this problem.
Steps: 
1. Sort the north-south pairs on the basis of increasing order of south x-coordinates. If two south x-coordinates are same, then sort on the basis of increasing order of north x-coordinates.
2. Now , use LIS to find the Longest Increasing Subsequence of the north x-coordinates. Here, in the increasing subsequence , a value can be greater as well as equal to its previous value.

The brute force approach would be to traverse the array and run a nested loop. For each interval, count the number of intervals it intersects and at last, print the maximum number of intervals that an interval can intersect.
The above approach can be optimized counting the number of intervals that do not intersect. The intervals that do not intersect with a particular interval can be divided into two disjoint categories: intervals that fall completely to the left or completely to the right. 
Steps:
1. Create a hashmap, say M, to map the number of intervals that do not intersect with each interval.
2. Sort the intervals on the basis of their starting point.
3. Traverse the intervals using the variable i
a. Initialize ans as -1 to store the index of the first interval lying completely to the right of ith interval.
b. Initialize low and high as (i + 1) and (N – 1) and perform a binary search as below:
i. Find the value of mid as (low + high)/2.
ii. If the starting position of interval[mid] > than the ending position of interval[i], store the current index mid in ans and then check in the left half by updating high to (mid – 1).
iii. Else check in the right half by updating low to (mid + 1).
c. If the value of ans is not -1, add (N – ans) to M[interval[i]].
4. Now, sort the intervals on the basis of their ending point.
5. Again, traverse the intervals using the variable i and apply a similar approach as above to find the intervals lying completely to the left of the ith interval.
6. After the loop, traverse the map M and store the minimum value in min.
7. Print the value of (N – min) as the result.

Recursion can be used here. Maintain two pointers, first and second to find the 2 nodes that violate the order. At last, change the values of the two nodes by their value. 

PseudoCode : 

correctBST(Node root) {
help(root);
swap(first->val, second->val);
}

help(Node root){
if(root is NULL) return;
help(root->left);
if(first is NULL and prev->val >= root->val) first=prev;
if(first is not NULL and prev->val >= root->val) second=root;
prev=root;
help(root->right);
}

Tip 1: Firstly, remember that the system design round is extremely open-ended and there’s no such thing as a standard answer. Even for the same question, you’ll have a totally different discussion with different interviewers.
Tip 2:Before you jump into the solution always clarify all the assumptions you’re making at the beginning of the interview. Ask questions to identify the scope of the system. This will clear the initial doubt, and you will get to know what are the specific detail interviewer wants to consider in this service.
Tip 3 : Design your structure and functions according to the requirements and try to convey your thoughts properly to the interviewer so that you do not mess up while implementing the idea .

Tip 1:Before you jump into the solution always clarify all the assumptions you’re making at the beginning of the interview. Ask questions to identify the scope of the system. This will clear the initial doubt, and you will get to know what are the specific detail interviewer wants to consider in this service.

Tip 3 : Design your structure and functions according to the requirements and try to convey your thoughts properly to the interviewer so that you do not mess up while implementing the idea .

Tip 1: Hash map can be used as a data structure to implement this functionality. According to the type of data stored in the file, a combination of data structures can be used to implement insert() and search() functionality.