SDE - 1

Approach : 

1) Sort the array in ascending order.

2) Now since we want triplets such that x + y + z = ‘K’, we have x+ y = ‘K’ - z and now we can fix z as arr[i]. So we want to find the sum of two numbers x and y as ‘K’ - arr[i] in the array.

3) We will use two pointers, one will start from i+1, and the other will start from the end of the array.

4) Let the two pointers be ‘FRONT’ and ‘BACK’, where ‘FRONT’ = i + 1 and ‘BACK’ = n - 1. Let ‘SUM’ = x + y, where x = ‘ARR[FRONT]’ and y = ‘ARR[BACK]’. We have to find the triplets such that ‘TARGET’ = ‘SUM’.

5) While ‘FRONT’ < ‘BACK’, there will be 3 cases:
5.1) if ('SUM' < ‘TARGET’), we will have to increase the sum and hence increment front pointer.
5.2) Else if ('SUM' > ‘TARGET’), we will have to decrease the sum and hence decrease the ‘BACK’ 
pointer. 
5.3) Else print the triplet and since we want distinct triplets, do the following.
a) Increment the front pointer until ‘ARR[FRONT]’ = x and ‘FRONT’ < ‘BACK’.
b) Decrement the back pointer until ‘ARR[BACK]’ = y and ‘FRONT’ < ‘BACK’.

6) While ‘ARR[i]’ = ‘ARR[i+1]’, keep on incrementing i, this will automatically ensure that we are only finding distinct triplets.

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

Approach : I solved this problem using 2-pointer technique. 

1) Initialize the first pointer to the start of str1 and the second pointer to the start of the str2.

2) Now increase the first pointer till the character pointed by the first pointer in str1 matches the character at the second pointer in str2. And the number of character which did not match should be placed at the end of str1. Therefore increase our answer by how many times we needed to increase the first pointer.

3) Now character pointed by both the pointer is the same so simply increase both pointers as they are same. And perform this while both the pointer do not exhaust the str1 and str2 respectively.

4) One thing to note is that all the characters which did not match would be placed at the end optimally so that the cost will be equal to the unmatched characters with the prefix of str2.

TC : O(N+M), where N is the size of the first string and M is the size of the second string.
SC : O(1)

Approach : If a number N is power of 2 then bitwise & of N and N-1 will be zero. We can say N is a power of 2 or not based on the value of N&(N-1). The expression N&(N-1) will not work when N is 0.
So,handle that case separately.

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

Approach 1 (Brute Force) : 

Create an output array and and one by one copy all arrays to it. Finally, sort the output array using. This approach takes O(N Logn N) time where N is count of all elements.

Approach 2 (Using Min-Heap) :

1. Create an output array. 
2. Create a min heap of size k and insert 1st element in all the arrays into the heap 
3. Repeat following steps while priority queue is not empty. 
3.1) Remove minimum element from heap (minimum is always at root) and store it in output array. 
3.2) Insert next element from the array from which the element is extracted. If the array doesn’t have 
any more elements, then do nothing.

TC : O(N*log(K))
SC : O(N)

Approach 1 (Using Level Order Traversal) : 

Steps : 
1) Initialize an array ‘spiral’ to store the result.
2) Initialize a variable ‘direction’ to keep track of traversing direction with 1(denoting left to right)
3) Find the height of the given tree and store it in a variable ‘height’.
4) Run a loop - level : 1 to height, to traverse through every level.
4.1) Find level order traversal in the current direction.and store in ‘spiral’
4.2) Toggle the direction.
5) Return ‘spiral’

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

Approach 2 (Using Stack) :

Steps : 
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. 
4) 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)

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.

Approach 1 :

Steps : 

1) If the ‘root’ node is NULL, return 0. The diameter of an empty tree is 0.
2) Recur for the left subtree and store the diameter of the left subtree in a variable ‘leftDiameter’, i.e. 
‘leftDiameter’ = getDiameter(left child of the root node)
3) Similarly, recur for the right subtree and store the diameter of the right subtree in a variable 
‘rightDiameter’ i.e. ‘rightDiameter’ = getDiameter(right child of the root node)
4) Now, get the height of the left subtree and right subtree and store it in a variable.
4.1) ‘leftHeight’ = getHeight(left child of the root node)
4.2) ‘rightHeight’ = getHeight(right child of the root node)
5) The diameter of the given tree will be the maximum of the following terms:
i) ‘leftDiameter’
ii) ‘rightDiameter’
iii) 1 + ‘leftHeight’ + ‘rightHeight’
6) Return the maximum of above terms i.e.max(leftDiameter, rightDiameter, 1 + leftHeight + rightHeight).

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


Approach 2 : 

Steps :

1) If the root node is NULL, assign “height” = 0 and return 0 because the height and diameter of an empty 
tree will be 0.
2) Initialize two variables, “leftHeight” and “rightHeight” to 0, which denotes the height of the left subtree 
and right subtree, respectively.
3) Recur for the left subtree and store the diameter of the left subtree in a variable i.e. leftDiameter = 
getDiameter(root->left, leftHeight)
4) Similarly, recur for the right subtree and store the diameter of the right subtree in a variable i.e. 
rightDiamater = getDiamter(root->right, rightHeight)
5) Update the height of the tree i.e. height = max(leftHeight, rightHeight) + 1
6) The diameter of the given tree will be the maximum of the following terms:
i) “leftDiameter”
ii) “rightDiameter”
iii) “leftHeight” + “rightHeight”
7) Return the maximum of above terms i.e. max(leftDiameter, rightDiameter, leftHeight + rightHeight).

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

Approach : I solved this problem using BFS.

Breadth-First-Search considers all the paths starting from the source and moves ahead one unit in all those paths at the same time. This makes sure that the first time when the destination is visited, it is the path with the shortest length.

Steps : 

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)

Answer : 

Real-time operating system (RTOS) is an operating system intended to serve real time application that process data as it comes in, mostly without buffer delay.
In a RTOS, Processing time requirement are calculated in tenths of seconds increments of time. It is time-bound system that can be defined as fixed time constraints. In this type of system, processing must be done inside the specified constraints. Otherwise, the system will fail.

Advantages of Real-time operating system :

1) Easy to layout, develop and execute real-time applications under the real-time operating system.
2) The real-time working structures are extra compact, so those structures require much less memory 
space.
3) In a Real-time operating system, the maximum utilization of devices and systems.
4) Focus on running applications and less importance to applications that are in the queue.

Disadvantages of Real-time operating system : 

1) RTOS system can run minimal tasks together, and it concentrates only on those applications which 
contain an error so that it can avoid them.
2) RTOS is the system that concentrates on a few tasks. Therefore, it is really hard for these systems to do 
multi-tasking.
3) Specific drivers are required for the RTOS so that it can offer fast response time to interrupt signals, 
which helps to maintain its speed.
4) Plenty of resources are used by RTOS, which makes this system expensive.