SDE - 1

Approach : 

1) Traverse the linked list from start to end and make frequency array of all digits (0-9) present in the linked list.

2) Make the string starting from the maximum of digits (0-9) present in the linked list i.e first append all the 9’s in the answer string then append all the 8’s at the end of the answer string so on for all the other digits in the decreasing order. 

3) Finally, return the formed answer string.


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

Approach : 

1) Suppose the given array is ‘CHOCOLATES’.

2) Sort the given array.

3) Find the subarray with the minimum difference of the last and first elements.

4) To store minimum difference we use a variable (say, ‘minVal’) and the initial value is ‘INFINITE’

5) Run a loop from 0 to ‘N’ - ‘M’ - 1(say, iterator ‘i’)

6) If 'CHOCOLATES'[i] - ‘CHOCOLATES’[i - M + 1] is less than ‘minVal’ then update ‘minVal’ with ‘CHOCOLATES’[i] - ‘CHOCOLATES’[i - M + 1] because we can get minimum difference possible with ‘i’th and (’i' - ‘M’ + 1)’th packet.

7) Finally, return ‘minVal’.


TC : O(N * log(N)), where N = the number of packets of chocolates.
SC : O(1)

Approach : 

1) The idea is to create a 3-D DP of size n*m*k.

2) Initially, all the elements of the DP table will be 0.

3) Now, the value DP[i][j] means denotes the length of the longest common sub-sequence of string A[0..i], B[0..j], and C[0..k].

4) The detailed algorithm to fill the DP table will be as follows:

Loop 1: For i = 1 to N:
Loop 2: For j = 1 to M:
Loop 3: For k = 1 to K:

if(A[i] == B[j] == C[k] ), DP[i][j][k] += DP[i-1][j-1][k-1]
else DP[i][j][k] = max(DP[i-1][j][k], DP[i][j-1][k], DP[i][j][k-1]) 

5) Return DP[n][m][k].


TC : O(n*m*k), where n, m, k are the length of the strings A, B, C respectively.
SC : O(n*m*k)

Approach : 

1) Initialize variables 'FIRSTBUY' as the minimum negative value, ‘FIRSTSELL’ as 0, ‘SECONDBUY’ as the minimum negative value, and ‘SECONDSELL’ as 0.
‘FIRSTSELL’ will be the profit after the first transaction and ‘SECONDSELL’ will be the profit after the second transaction.

2) For ‘i’ in range days:
2.1) Maximise 'FIRSTBUY' as max( 'FIRSTBUY' , - ‘PRICES[i]’), this is the amount left after your first buy.
2.2) Maximise ‘FIRSTSELL’ as max( ‘FIRSTSELL’ , 'FIRSTBUY' + ‘PRICES[i]’).
2.3) Maximise ‘SECONDBUY’ as max( ‘SECONDBUY’ , ‘FIRSTSELL’ - ‘PRICES[i]’).
2.4) Maximise ‘SECONDSELL’ as max( ‘SECONDSELL’ , ‘SECONDBUY’ + ‘PRICES[i]’).

3) Return ‘SECONDSELL’ as it is the final profit or the final amount left with you.

TC : O(N), where N = number of days
SC : O(1)

Approach : This question was similar to the famous problem "Count Inversions" and so I thought of applying Merge Sort here. 

1) By modifying the merging array part of merge sort, we can calculate the required ans.

2) During merging of two halves, when the higher index element is less than the lower index element, it represents that the higher index element is smaller than all the elements after that lower index because the left part is already sorted. Hence add up to all the elements after the lower index element for the required count.

3) We will use the function MergeCount() to count the ans for a particular range of people. Initially, our range is 0 to n-1.

4) The MergeCount() function will perform three operation.
4.1) Recursively call MergeCount() for the left half.
4.2) Recursively call MergeCount() for the right half.
4.3) Call another helper function Merge() to merge both the halves.


TC : O(N * logN), where N = number of people.
SC : O(N)

Process : A process is an instance of a program that is being executed. When we run a program, it does not execute
directly. It takes some time to follow all the steps required to execute the program, and following these execution
steps is known as a process.

A process can create other processes to perform multiple tasks at a time; the created processes are known as clone
or child process, and the main process is known as the parent process. Each process contains its own memory
space and does not share it with the other processes. It is known as the active entity.



Thread : A thread is the subset of a process and is also known as the lightweight process. A process can have more
than one thread, and these threads are managed independently by the scheduler. All the threads within one process
are interrelated to each other. Threads have some common information, such as data segment, code segment, files,
etc., that is shared to their peer threads. But contains its own registers, stack, and counter.

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.

Approach : 

1) We maintain a 2D array dp of size N*M. Since the increasing path can start from any point in the matrix, we use dp[i][j] to store the length of the longest increasing path starting from location (i, j). This ensures that we do not recalculate a visited location. 

2) Now, we perform a DFS from each cell with the current cell as (x, y). We compare the cells in the four directions (dx, dy) and skip cells that are out of boundary or for which mat[x][y] > mat[dx][dy].

If the cell (dx, dy) satisfies the conditions, we perform dfs from that cell and update maxLen as max of maxLen and 1 + (dfs from dx, dy).

3) We then update dp[x][y] with maxLen.

4) Finally, we return the maximum length of the increasing path as result.


TC : O(N*M), where N and M denote the number of rows and columns respectively
SC : O(N*M)

Approach : 

1) We can choose every index to be our starting point and check whether we can complete the round trip starting from that index.

2) For each start point, we will run a loop starting from this index. If at any point, petrol available in the truck is not sufficient to move on to the next petrol pump, we know this is a bad starting point. So, we break the loop and try the same for the next start point.

3) As soon as we find a start point which results in a complete tour of all pumps, we return its index.

4) If no such index exists we will simply return -1.


TC : O(N^2), where N = total number of petrol stations
SC : O(1)

Approach : 

1) Create a boolean array of size n + 1 with default value false.

2) Run a loop from i=0 to k. If A[i] is marked true then we don’t need to traverse its multiples as they have been already traversed. Else Traverse all multiples of A[i] less than n. The carrots which are visited mark it true.

3) After doing traversal count the values from 1 to n with false values. Return this value.


TC : O(N * log(max(A[i]))) where N = number of carrots. 
SC : O(N)