SDE - 1

Approach : 

1) If ‘N’ is equal to 1, return the only element in the array.

2) Initialize ‘ans’ to 1.

3) Initialize ‘id’ to -1 and ‘minElement’ to 0.

4) Initialize ‘negCount’ and ‘zeroCount’ to 0.

5) Iterate through the array

5.1) If current element is 0, increment ‘zeroCount’ by 1.
5.2) If current element is negative
i) Increment ‘negCount’ by 1.
ii) If ‘id’ is equal to -1 or the magnitude of the current element is smaller than ‘minElement’, assign ‘minElment’ to the current element and ‘id’ to the current index.

6) If ‘zeroCount’ is equal to ‘N’
Return 0

7) If ‘negCount’ is equal to 1 and ‘zeroCount’ is equal to ‘N’ - 1
Return 0

8) Iterate through the array

8.1) If current element is zero, continue.
8.2) If ‘negCount’ is odd and the current index is equal to ‘id’, continue.
8.3) Else update ‘ans’ to the product of ‘ans’ and current element mod 1^9 + 7.

9) Return ‘ans’.


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

Approach : 

1) Create a 2D integer matrix ‘dp’ of size n*m, where dp[i][j] stores the length of the longest path ending at ‘mat[i][j]’. Fill the entire matrix ‘dp[][]’ with INT_MIN initially.

2) Assign dp[0][0]:= 1

3) Run a loop where ‘i’ ranges from 1 to ‘m-1’ and for each ‘i’ if ‘mat[0][i]’ > mat[0][i-1], then assign dp[0][i] := dp[0][i-1] + 1, otherwise break the loop.

4) Run a loop where ‘i’ ranges from 1 to ‘n-1’ and for each ‘i’ if ‘mat[i][0]’ > mat[i-1][0]’, then assign dp[i][0] := dp[i-1][0] + 1, otherwise break the loop

5) Run two nested loops, In outer loop ‘i’ ranges from 1 to n-1, and inner loop ‘j’ ranges from 1 to m-1, and for each (i, j) do the following.
5.1) If mat[i][j] > mat[i][j-1], then assign dp[i][j] = max(dp[i][j], dp[i][j-1] + 1).
5.2) If mat[i][j] > mat[i-1][j], then assign dp[i][j] = max(dp[i][j], dp[i-1][j] + 1).

6) The largest value of the matrix ‘dp[][]’ will be the length of the longest path starting from (0, 0), we need to return this value.


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

Approach :

Finding the cycle : 

1) Initialize slow and fast at the beginning.
2) Start moving slow to every next node and move fast 2 jumps, while making sure that fast and its next is not null.
3) If slow and fast refer to the same node anytime during the process, there is a cycle, otherwise, repeat the process.
4) If fast reaches the end or NULL, then the execution stops and we can conclude that no cycle exists.


Removing the cycle : 

1) Find the length of the cycle, let’s say ‘L’.
2) We will take two pointers ‘ptr1’ and ‘ptr2’, initially ‘ptr1’ points to head and ‘ptr2’ points to Lth node from the head.
3) We will move the pointers until they meet at the same node.
4) To remove the cycle we have to find the previous node of the ‘ptr2’ and change its ‘next’ values to NULL.


TC : O(N) , where N = number of nodes in the Linked List
SC : O(1)

Approach (Using Sorting) : 

1) We will first sort the intervals by non-decreasing order of their start integers.

2) We will create a 2D vector “RES” which will be our resultant vector storing all the merged intervals. Now, we will add the first interval to our resultant list.

3) Now, we will run a loop for the total number of intervals and for each interval, we will check whether the current interval is overlapping with the last interval in our resultant list or not.

4) If it overlaps with the last interval, we will update the end integer of the last interval in the list by the maximum of the end integers of both overlapping intervals.

5) If it doesn't overlap, we will add the current interval to the “RES” vector.

6) Finally, we will return our resultant vector “RES” as our final answer.


TC : O(N*log(N)), where N is the number of intervals
SC : O(1)

Prerequisite to solve this problem : Multithreading

The idea is to create two threads and print even numbers with one thread and odd numbers with another thread.

Below are the steps:

1) Create two threads T1 and T2 , where T1 and T2 are used to print odd and even numbers respectively.
2) Maintain a global counter variable and start both threads.
3) If the counter is even in the Thread T1, then wait for the thread T2 to print that even number. Otherwise, print that
odd number, increment the counter and notify to the Thread T2 .
4)If the counter is odd in the Thread T2, then wait for the thread T1 to print that even number. Otherwise, print that
even number, increment the counter and notify the Thread T1.

Multitasking : It refers to the process in which a CPU happens to execute multiple tasks at any given time. CPU
switching occurs very often when multitasking between various tasks. This way, the users get to collaborate with
every program together at the same time. Since it involves rapid CPU switching, it requires some time. It is because
switching from one user to another might need some resources. The processes in multi-tasking, unlike multi-
threading, share separate resources and memories.


Multithreading : It is a system that creates many threads out of a single process to increase the overall power and
working capacity of a computer. In the process of multi-threading, we use a CPU for executing many threads out of a
single process at any given time. Also, the process of creation depends entirely on the cost. The process of
multithreading, unlike multitasking, makes use of the very same resources and memory for processing the execution.

Approach (Using Array) :

Definition of Trie Node :

1) child - storing the address of child nodes (Array of the address of Trie Nodes with size 26 initialized with NULL)
2) isEnd - a bool variable for marking this node as an end of some word.

Then we have defined our Trie Class having members :

1) root - The root node for whole Trie, every word starts from this node.
2) insert(word) - To insert a string "word" in Trie
3) search(word) - To check if string "word" is present in Trie or not.
4) startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".


insert(word) :

1) Initialize the current node with the root node of Trie.
2) Iterate over the word from left to right and if there is NULL in the address of the node for the next character of the
word then create a new node and store the address in child member of the previous character’s node.
3) Keep updating the current node to the corresponding node for the next character of the word.
4) Finally, when we reached the end of the word, mark the isEnd member of the current node to true as it will denote
the word is present or not.


search(word) :

1) Initialize the current node with the root node of Trie.
2) Iterate over the word from left to right and if there is NULL in the address of the node for the next character of the
word then return false as the word is not present in the Trie.
3) Keep updating the current node to the corresponding node for the next character of the word.
4) Finally, when we reached the end of the word, return the isEnd bool variable of the current node as it will denote
the word is present or not.


startsWith(word) :

1) Initialize the current node with the root node of Trie.
2) Iterate over the word from left to right and if there is NULL in the address of the node for the next character of the
word then return false as the no word is present in the Trie with this word as a Prefix.
3) Keep updating the current node to the corresponding node for the next character of the word.
4) Finally, when we reached the end of the word, return true as some word must be present in the Trie as we are able
to cover the whole prefix word.



TC : O(N*W) (insert - O(W), search - O(W), startsWith - O(W))
where N is the number of queries and W is the average length of words.
SC : O(N*W)

Approach : 

1) First, calculate the angle made by the hour hand with respect to 12:00 in H hours and M minutes. In 12 hours the hour hand moves by 360 degrees i.e. 30 degrees in 1 hour and 0.5 degrees in 1 minute. So in H hours and M minutes, the angle moved by hour hand is 0.5 * (H * 60 + M).

2) Then, calculate the angle made by minute hand with respect to 12:00 in H hours and M minutes. In 60 minutes the minute hand moves by 360 degrees i.e. 6 degrees in 1 minute. So in H hours and M minutes, the angle moved by minute hand is 6 * M.

3) The difference between the two angles is the required angle.


TC : O(1)
SC : O(1)

Approach (Using 2-pointers) : 

1) Initially we will have two pointers, let’s say ‘i’ at 0 and another pointer, let’s say ‘j’ at “M - 1”.

2) While the value of i is less than ‘N’ and the value of ‘j’ is non negative do the following steps :
2.1) If arr[i][j] is equal to X, return true.

2.2) If arr[i][j] is less than ‘X’ then increment the value of ‘i’ because ‘X’ will be greater than all values of i’th row(because each row is sorted), hence ‘X’ will never be found in the current row.

2.3) If arr[i][j] is greater than ‘X’ then decrement the value of ‘j’, since all values in the j’th column will be greater than ‘X’(because each column is sorted), hence ‘X’ will never be found in the j’th column.

3) If there is no element equal to ‘X’ return false.


TC : O(N+M) , where N and M are the number of rows and columns respectively.
SC : O(1)