SDE - 1

Approach : 

1) First make a recursive function, say ‘solve’ taking the number of opening brackets ‘opening’, number of closing brackets ‘closing’ output string ‘output’, and an array of strings ‘ans’ as arguments.

2) Make the base condition as if ‘opening’ = 0 and ‘closing’ = 0 then push the output string in the ‘ans’ and return.

3) If ‘opening’ is not equal to zero then call the ‘solve’ function recursively by decrementing ‘opening’ by 1 and inserting ‘(‘ into the ‘output’.

4) If ‘closing’ > ‘opening’ then call the ‘solve’ function recursively by decrementing ‘closing’ by 1 and inserting ‘)’ into the ‘output’.


TC : O(2 ^ N), where N is the given integer.
SC : O(N)

Approach : 

1) Let the 'X', 'Y', 'Z' be the maximum availability ‘a’, ‘b’, ‘c’ respectively.

2) Declare an empty string say ‘S’ to store the answer string.

3) Run a loop till (x + y + z)
3.1) If ( 'X' >= 'Y' and 'X' >= 'Z' and the last two letters in ‘S’ is not “aa” ) or ( the last two letters in ‘S’ are “bb” or “cc” and 'X' is nonzero).
Add ‘a’ to ‘S’, and update 'X' to ‘x - 1’.

3.2) If ( 'Y' >= 'X' and 'Y' >= 'Z' and the last two letters in ‘S’ is not “bb” ) or ( the last two letters in ‘S’ are “aa” or “cc” and 'Y' is nonzero).
Add ‘b’ to ‘S’, and update 'Y' to ‘y - 1’.

3.3) If ( 'Z' >= 'Y' and 'Z' >= 'X' and the last two letters in ‘S’ is not “cc” ) or ( the last two letters in ‘S’ are “bb” or “aa” and 'Z' is nonzero).
Add ‘c’ to ‘S’, and update 'Z' to ‘z - 1’.

4) Return S.


TC : O(X+Y+Z), where X, Y, Z are the given maximum number a, b, and c respectively that the output string can have.
SC : O(X+Y+Z)

Approach (Using Backtracking) : 

Let ‘allAllPaths(n, m, edges, src, des)’ be the function that returns a 2D array that contains all the possible paths.

1) Take the following variables: 2D array ‘Graph’, to store graphs and ‘Visited’ array to mark each node whether it is visited or not.

2) Clear graph, initialize the visited array to false.

3) Run a loop from 0 to 'm' :
3.1) Add the undirected edge between edges[i] [0] and edges[i][1].

4) Take an 2D array 'allPaths' to store the answer.

5) Take an array 'currPath' to store the current path.

6) Push ‘src’ in ‘currPath’ and mark visited[src] equal to true.

7) Make a dfs(n, allPaths, currPath, src, des, graph, visited) and call the dfs function.

8) Return ‘allPaths’.


TC : O(N ^ N), where N is the number of vertices.
SC : O(N ^ N)

Approach : 

1) Initialize slow and fast at the beginning.

2) Start moving slow to every next node and moving fast 2 jumps, while making sure that fast and its next is not null.

3) If after adjusting slow and fast, if they are referring to the same node, 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.


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

Approach : 

1) Maintain a hash-map ‘mp,’ which keeps track of the nodes we have visited.

2) We will use a helper function, ‘helper’.

3) ‘helper’ takes ‘root,’ ‘target,’ and ‘mp’ as input parameters, where ‘root’ is the root of the binary tree, ‘target’ is the value which should be equal to sum of 2 nodes and ‘mp’ is the hash-map we use to keep track of nodes visited.

3.1) For a given root ‘toFind’ value is the other half that we need to find to make a pair whose sum is equal to ‘target’, for the given ‘root’s data value.

3.2) If for the current node we have visited a node whose value is ‘toFind’ and they are not the same nodes, we return true.

3.3) Else we recur for the left and right nodes of the current node.

3.4) If we find the pair, we return true. Else we return false as the final answer.


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

OOP is used commonly for software development. One major pillar of OOP is polymorphism. Early Binding and Late
Binding are related to that. Early Binding occurs at compile time while Late Binding occurs at runtime. In method
overloading, the bonding happens using the early binding. In method overriding, the bonding happens using the late
binding. The difference between Early and Late Binding is that Early Binding uses the class information to resolve
method calling while Late Binding uses the object to resolve method calling.


Early Binding : In Early Binding, the class information is used to resolve method calling. Early Binding occurs at
compile time. It is also known as the static binding. In this process, the binding occurs before the program actually
runs. Overloading methods are bonded using early binding.


Late Binding : In Late Binding, the object is used to resolve method calling. Late Binding occurs at runtime. It is also
known as dynamic binding. In this process, the binding occurs at program execution. Overridden methods are
bonded using late binding.

Deadlock : Deadlock is a scenario where a set of processes is blocked because each process has acquired a lock on
a particular resource and is waiting for another resource locked by some other process.
A deadlock can occur in almost any situation where processes share resources. It can happen in any computing
environment, but it is widespread in distributed systems, where multiple processes operate on different resources.

Steps to prevent Deadlock :

1) No Mutual Exclusion :
It means more than one process can have access to a single resource at the same time. It’s impossible because if
multiple processes access the same resource simultaneously, there will be chaos. Additionally, no process will be
completed. So this is not feasible. Hence, the OS can’t avoid mutual exclusion.


2) No Hold and Wait :
To avoid the hold and wait, there are many ways to acquire all the required resources before starting the execution.
But this is also not feasible because a process will use a single resource at a time.
Another way is if a process is holding a resource and wants to have additional resources, then it must free the
acquired resources. This way, we can avoid the hold and wait condition, but it can result in starvation.


3) Removal of No Preemption :
One of the reasons that cause the deadlock is the no preemption. It means the CPU can’t take acquired resources
from any process forcefully even though that process is in a waiting state. If we can remove the no preemption and
forcefully take resources from a waiting process, we can avoid the deadlock.


4) Removal of Circular Wait :
In the circular wait, two processes are stuck in the waiting state for the resources which have been held by each
other. To avoid the circular wait, we assign a numerical integer value to all resources, and a process has to access
the resource in increasing or decreasing order.

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.

If you get this question, it's an opportunity to choose the most compelling information to share that is not obvious from
your resume.

Example :

Strength -> I believe that my greatest strength is the ability to solve problems quickly and efficiently, which makes me
unique from others.

Ability to Handle Pressure -> I enjoy working under pressure because I believe it helps me grow and become more
efficient .


Tip : Emphasize why you were inspired to apply for the job. You can also explain that you are willing to invest a great
deal of energy if hired.

These are generally very open ended questions and are asked to test how quick wit a candidate is. So there is
nothing to worry about if you have a good cammand over your communication skills and you are able to propagate
your thoughts well to the interviewer.