SDE - 1

Approach 1 (Brute Force) :

1) Generate all substrings of string1.
2) For each substring, check whether the substring contains all characters of string2.
3) Finally, print the smallest substring containing all characters of string2.

TC : O(N^3), where N=length of the given string s1 and s2
SC : O(1)


Approach 2 (Sliding Window) :

We can use a simple sliding window approach to solve this problem.
The solution is pretty intuitive. We keep expanding the window by moving the right pointer. When the window has all
the desired characters, we contract (if possible) and save the smallest window till now.
The answer is the smallest desirable window.

Algorithm :

1) We start with two pointers, left and right initially pointing to the first element of the string S.
2) We use the right pointer to expand the window until we get a desirable window i.e. a window that contains all of the
characters of T
3) Once we have a window with all the characters, we can move the left pointer ahead one by one. If the window is
still a desirable one we keep on updating the minimum window size.
4) If the window is not desirable any more, we repeat step2 onwards.

TC : O(N+M) where N and M are the respective length of strings S and T.
SC : O(N+M)

The idea is simple: along the path, record all prefix sums in a hash table. For current prefix sum x, check if (x - target)
appears in the hash table.

Steps :

1) We will be using a unordered map which will be filled with various path sum.

2) For every node we will check if current sum and root’s value equal to k or not. If the sum equals to k then
increment the required answer by one.

3) Then we will add all those path sum in map which differs from current sum+root->data value by a constant integer
k.

4) Then we will be inserting the current sum + root->data value in the map.

5) We will recursively check for left and right subtrees of current root

6) After the right subtree is also traversed we will remove the current sum + root->data value from the map so that it
is not taken into consideration in further traversals of other nodes other than the current root’s.


TC : O(n) where n is the total number of nodes in the tree
SC : O(n)

Approach 1 (Recursive Inorder Traversal) :

We know that the inorder traversal of a BST always gives us a sorted array , so if we maintain two variable Tree
Nodes "previous" and "current" , we should always have previous->val < current->value for a valid BST.

Steps :
1) Create a boolean recursive function with two parameters (root and prev) which will return true if our binary tree is a
BST or else it will return false.
2) If root is not null , call the recursive function with parameters (root->left,prev) and check if it return true or not.
3) For the prev node , check if at any point prev->val >= root->val if this condition is met , simply return false.
4) Update prev with root.
5) Call the recursive function again with parameters (root->right , prev)

TC : O(N) where N=number of nodes in the binary tree
SC : O(N)



Approach 2 (Iterative Inorder Traversal) :

We can also perfom an iterative inorder traversal of the Binary Tree using a stack and check the same condition that
we checked above i.e., at any point if prev->value >= current->value if this is met then simply return false.

Steps :

1) Take a stack of TreeNodes and a TreeNode prev with its initial value as NULL.
2) Run a loop till stack is not empty or root != NULL.
3) While pushing a root to the stack, push all its left descendants into the stack untill root != NULL.
4) Take current = stack.top() and pop it from the stack
5) Check if prev is NOT NULL and if prev->val >= curr->val , if this cond. is met simply return false.
6) Update prev with current.
7) Update root with root->right.

TC : O(N) where N=number of nodes in the binary tree
SC : O(N)

Approach 1 (Naive Solution) :

1) The simplest approach to solve the problem is to generate all possible subarrays.
2) For each subarray, check if the difference between adjacent elements remains the same throughout or not.
3) Among all such subarrays satisfying the condition, store the length of the longest subarray and print it as the result.

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


Approach 2 (Efficient Solution) :

1) Initialize a variable called res to store the length of the longest subarray forming an AP.
2) Iterate over remaining arrays and compare the current adjacent difference with the previous adjacent difference.
3) Iterate over the array, and for each element, calculate the difference between the current pair of adjacent elements
and check if it is equal to the previous pair of adjacent elements.
4) If found to be true, continue the ongoing subarray by incrementing res by 1.
5) Otherwise, consider a new subarray. Update the maximum length obtained so far, i.e. res by comparing it with the
length of the previous subarray.
6) Finally, return the res as the required answer.

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

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 (Naive Solution) :

1) Use two loops: The outer loop picks all the elements one by one.
2) The inner loop looks for the first greater element for the element picked by the outer loop.
3) If a greater element is found then that element is printed as next, otherwise, -1 is printed.

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


Approach 2 (Using Stack) :

1) Push the first element to stack.

2) Pick rest of the elements one by one and follow the following steps in loop.

2.1) Mark the current element as next.

2.2) If stack is not empty, compare top element of stack with next.

2.3) If next is greater than the top element, Pop element from stack. next is the next greater element for
the popped element.

2.4) Keep popping from the stack while the popped element is smaller than next. next becomes the next
greater element for all such popped elements.

3) Finally, push the next in the stack.

4) After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.



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

Given,a set of n elements I was supposed to print all the subsets of this set . I was famiiar with this question and had
already solved it in LeetCode and CodeStudio so coding it in the first go was not so hard for me .

Approach : I solved it using bitmasking . The main intuition was if I have a binary number like 1001 , I would take only
the 0th element and the 3rd element of the array .

Steps :
1) Run a loop from 0 to (2^n)-1 (as we have 2^n subsets for a set of n elements)

2) For every number , run a loop again from 0 to n-1 to check if the ith bit is set or not.

3) To check if the ith bit is set or not , simply check if (number & 2^i) > 0 or not
(where i ranges from 0 to n-1)

4) If (num & 2^i)==0 , ith bit is 0 i.e., do not take the ith element into the subset . Else if (num &2^i)>0 , ith bit is 1 i.e.,
take the ith element into the subset.

5) Finally put all the subsets into a vector and output the answer vector


TC : O(2^n)
SC : O(2^n)

Answer : The easiest way to do this is to use external sorting.

Steps :

1) We divide our source file into temporary files of size equal to the size of the RAM and first sort these files.

2) Assume 1GB = 1024MB, so we follow following steps.

2.1) Divide the source file into 5 small temporary files each of size 200MB (i.e., equal to the size of ram).

2.2) Read input_file such that at most ‘runSize’ elements are read at a time. Do following for the every
run read in an array.

2.3) Sort the run using MergeSort.

2.4) Store the sorted array in a file. Lets say ‘i’ for ith file.

2.5) Merge the sorted files using the same approach used in Merge K sorted arrays.


Now we have sorted temporary files.

1) Pointers are initialized in each file

2) A new file of size 1GB (size of source file) is created.

3) First element is compared from each file with the pointer.

4) Smallest element is copied into the new 1GB file and pointer gets incremented in the file which pointed to this
smallest element.

5) Same process is followed till all pointers have traversed their respective files.

6) When all the pointers have traversed, we have a new file which has 1GB of sorted integers.


This is how any larger file can be sorted when there is a limitation on the size of primary memory (RAM).


TC : O(n * log n) , where n=size of the array
SC : O(runSize) , runSize is the space needed to store the array.