SDE - 1

Approach :

1) Create two lists or arrays, say, ‘leftMax’ and ‘rightMax’.
2) At every index in the ‘leftMax’ array store the information of the ‘leftMaxHeight’ for every elevation in the map.
3) Similarly, at every index in the ‘rightMax’ array store the information of the ‘rightMaxHeight' for every elevation in the map.
4) Iterate over the elevation map and find the units of water that can be stored at this location by getting the left max height and right max height from the initial arrays that we created.

TC : O(N), where N=total number of elevations in the map.
SC : O(N)

Approach (Using BFS) :

1) Create an empty queue and enqueue source cell and mark it as visited

2) Declare a ‘STEPS’ variable, to keep track of the length of the path so far

3) Loop in level order till the queue is not empty
3.1) Fetch the front cell from the queue
3.2) If the fetched cell is the destination cell, return ‘STEPS’
3.3) Else for each of the 4 adjacent cells of the current cell, we enqueue each valid cell into the queue and mark them visited.
3.4) Increment ‘STEPS’ by 1 when all the cells in the current level are processed.

4) If all nodes in the queue are processed and the destination cell is not reached, we return -1.

TC : O(N*M) , where ‘N’ and ‘M’ are the number of rows and columns in the Binary Matrix respectively. 
SC : O(N*M)

Approach : 

1) Given a tree node ROOT, initialise a queue of nodes NODEQUEUE and COUNT by 0.

2) Push ROOT into NODEQUEUE.

3) While NODEQUEUE is not empty do:
3.1) Initialize node TEMP as NODEQUEUE.peek().
3.2) If TEMP.left is not NULL, push TEMP.left to NODEQUEUE.
3.3) If TEMP.right is not NULL, push TEMP.right to NODEQUEUE.
3.4) If TEMP.right and TEMP.left are both NULL, increase COUNT by 1.

4) Return COUNT

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

Approach 1 :

1) We use a count array to store the frequency.
2) We initialize the count array to zero for all the numbers.
3) Now, iterate through the array and increment the corresponding frequency count of the numbers.
4) Now, we iterate through the count (frequency) array.
5) The number with a frequency equal to zero is the missing number while the number with a frequency equal to two
is the repeating number.

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


Approach 2 :

1) Traverse the array and mark the index corresponding to the current number.
2) While traversing if the index corresponding to the current number has already been marked. Then the current
number is the repeating number in the array.
3) In order to determine the missing number, traverse the array again and look for a positive value.
4) The index corresponding to the positive number gives us the missing number (= index + 1).

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

Approach : 

1) Create a hashmap/dictionary which will store the count of occurrences of each element and initially it will be empty.

2) Run a loop from i=0 to N-1 and for each i’th element its value is arr[i] and we need to find the number which is equal to Sum - arr[i]. So check if sum-arr[i] is present in the hashmap/dictionary. If it is present, the answer will be increased by the count of occurrence of sum-arr[i] present in the hashmap/dictionary as arr[i] can be paired with all those sum-arr[i] elements present in its left side.

3) Now increase the count of arr[i] in the hashmap/dictionary by 1.

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

Answer :

Structure : Structure is a user-defined data type in C programming language that combines logically related data
items of different data types together.
All the structure elements are stored at contiguous memory locations. Structure type variable can store more than
one data item of varying data types under one name.

Union : Union is a user-defined data type, just like a structure. Union combines objects of different types and sizes
together. The union variable allocates the memory space equal to the space to hold the largest variable of union. It
allows varying types of objects to share the same location.


Key differences b/w Structure and Union :

1) Every member within structure is assigned a unique memory location while in union a memory location is shared
by all the data members.
2) Changing the value of one data member will not affect other data members in structure whereas changing the
value of one data member will change the value of other data members in union.
3) Structure is mainly used for storing various data types while union is mainly used for storing one of the many data
types.
4) In structure, you can retrieve any member at a time on the other hand in union, you can access one member at a
time.
5) Structure supports flexible array while union does not support a flexible array.


Advantages and Disadvantages of using Structure :

Advantages :
1) Structures gather more than one piece of data about the same subject together in the same place.
2) It is helpful when you want to gather the data of similar data types and parameters like first name, last
name, etc.
3) It is very easy to maintain as we can represent the whole record by using a single name.

Disadvantages :
1 )If the complexity of IT project goes beyond the limit, it becomes hard to manage.
2) Change of one data structure in a code necessitates changes at many other places. Therefore, the
changes become hard to track.
3) Structure is slower because it requires storage space for all the data.


Advantages and Disadvantages of using Union :

Advantages :
1) It occupies less memory compared to structure.
2 )When you use union, only the last variable can be directly accessed.
3) Union is used when you have to use the same memory location for two or more data members.

Disadvantages :
1) You can use only one union member at a time.
2) All the union variables cannot be initialized or used with varying values at a time.
3) Union assigns one common storage space for all its members.


Tip : Cover concepts of OOPS properly preferrably in C++ or in Java and for quick revision, the guided path of C++ in
Coding Ninjas is a very good resource. I completed the OS and C++ guided path before my interviews and it helped
me a lot.

C++ is an Object-oriented programming language and it supports Polymorphism as well:

Compile Time Polymorphism: C++ supports compile-time polymorphism with the help of features like templates, function overloading, and default arguments.

Runtime Polymorphism: C++ supports Runtime polymorphism with the help of features like virtual functions. Virtual functions take the shape of the functions based on the type of object in reference and are resolved at runtime.

Approach : 

1) We will maintain two stacks, one for each direction i.e. leftToRight and rightToleft.

2) We will do a level order traversal of the given binary tree and push nodes of each level onto one of the stack according to the current direction of traversal.

3) After we’ve pushed all nodes of a level onto one stack, we’ll start popping those nodes. While popping the nodes we will push their children (if any) onto our other direction stack, so that the next level be traversed in reverse order.

TC : O(N), where ‘N’ is the number of nodes in the binary tree.
SC : O(N)

Approach : A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Stack ‘s’ can be implemented in two ways :

Method 1 (push - O(1) , pop - O(n) ) :

1) push(s, x) operation :
i) Enqueue x to q1 (assuming size of q1 is unlimited).

2) pop(s) operation :
i) One by one dequeue everything except the last element from q1 and enqueue to q2.
ii) Dequeue the last item of q1, the dequeued item is result, store it.
iii) Swap the names of q1 and q2
iv) Return the item stored in step 2.

TC : push(s,x) -> O(1)
pop() -> O(n)


Method 2 (push - O(n) , pop - O(1) ) :

1) push(s, x) operation :
i) Enqueue x to q2
ii) One by one dequeue everything from q1 and enqueue to q2.
iii) Swap the names of q1 and q2

2) pop(s) operation :
i) Dequeue an item from q1 and return it.

TC : push(s,x) -> O(n)
pop() -> O(1)

Approach : 

1) Traverse a given binary tree.
2) While traversing the given binary tree, store the old value of the current node, recursively call for left and right subtrees.
3) Now change the value of the current node as the sum of the values returned by the recursive calls of left and right subtrees.
4) Finally, return the sum of the new value and value (which is the sum of values in the subtree rooted with this node).

TC : O(N), where ‘N’ is the number of nodes in the given binary tree.
SC : O(N)

Answer :

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.

Android is an open-sourced operating system that is used on mobile devices, such as mobiles and tablets. The Android application executes within its own process and its own instance of Dalvik Virtual Machine(DVM) or Android RunTime(ART).