SDE - 1

Approach (Using BFS) : 

1) Parse the given ‘edges’ into an adjacency matrix ‘graph’, by pushing ‘i’ is graph[j] and ‘j’ in graph[i] if edges[i][j] is 1.

2) Maintain a vector ‘color’ which denotes the color of the ‘i’ the node, initially, all colors are un-assigned, hence -1.

3) Maintain a color ‘c’ initially 0 to assign to nodes and flip after each level of the graph.

4) Now maintain a queue ‘que’ for doing a breadth-first traversal and push ‘i’, the root node in it.

5) While ‘que’ is not empty:
5.1) Maintain a variable ‘node’ which denotes the node in the front of the ‘que’.

5.2) Traverse all the neighbors ‘nbr’ of the current node.
i) If the ‘color[nbr]’ is equal to ‘color[node]’, return false, since this is not possible, as discussed above.
ii) Else if the ‘color[nbr]’ is -1, which means it is unassigned, assign it ‘c’.

5.3) Flip the color after traversing all the ‘nbr’ of ‘node’.

6) If we exit the loop, return true, since all nodes have been assigned colors and no 2 adjacent nodes have the same color.


TC : O(N^2), where N = no. of nodes
SC : O(N)

Approach 1 (Brute Force) :

1) Create a variable ans, which stores the total number of subarrays. We will set the variable ans as 0.

2) Iterate index from 0 to N - 1.

3) Iterate pos from index to M - 1.
3.1) We will maintain a variable currentXor, which will store the XOR of all elements present in the
current subarray. We will set currentXor as 0.

4) We will traverse num from index to pos. We will update currentXor with XOR of currentXor and
ARR[num].
4.1) Check if currentXor is equal to X.
4.2) Increment ans by 1.

5) Return the variable ans.


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



Approach 2 (Using Hashing) :

1) Create a HashMap “prefXor” which stores the count of subarrays having a particular XOR value.

2) Create a variable “curXor” which stores the XOR for ‘i’ elements. Initialise it with zero. Also, create a
variable called “ans” to store the count of the subarrays having XOR ‘X’.

3) Start iterating through given array/list using a variable ‘i’ such that 0 <= ‘i’ < n
3.1) Update the “curXor” i.e. curXor = curXor ^ arr[i]

3.2) Store the required value of the prefix Xor to make the XOR of the subarray ending at the current
index equal to X i.e. req = X ^ curXor

3.3) Now add the count of prefix arrays with required xor i.e. ans = ans + prefXor[req]

3.4) Update the “prefXor” HashMap with the “curXor” i.e. prefXor[curXor] = prefXor[curXor] + 1


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

Approach (Using Kahn's Algo) : 

1) Create a graph using the ‘prerequisites’ array.

2) We compute indegree(number of incoming edges) for each vertex present in the graph.

3) We initialise an integer variable ‘visited’ to 0, representing the count of visited nodes.

4) Pick all vertices with indegree 0 and add them in a queue.

5) We do the following operations until the queue becomes empty.
i) Remove a vertex from the queue.
ii) Increment ‘visited’ by 1.
iii) Decrement the indegree of all its adjacent vertices by 1.
iv) If indegree of adjacent vertices is reduced to 0, then add them to the queue.

6) If ‘visited’ is equal to ‘N’, then return “Yes” else return “No”.


TC : O(N+M), where N = no. of vertices and M = no. of edges in the graph
SC : O(N)

Approach : 

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)

1) Memory protection is a strategy that makes it possible to manage the amount of access rights that are granted to
the memory found on a computer hard drive.

2) The main purpose of this type of protection is to minimize the potential for some type of storage violation that
would harm the data contained in the memory, or damage a portion of the memory capacity of the hard drive.

3) One of the main functions of memory protection is the prevention of any application from making use of memory
that the operating system has not specifically allocated to that application.

4) This prevents applications from seizing control of an inordinate amount of memory and possibly causing damage
that negatively impacts other applications that are currently in use, or even creating a loss of data that is saved on the
hard drive.

5) In many operating systems, this is managed by segmenting the memory for use by all open applications, ensuring
that each has enough to operate properly without creating issues with the other running applications.

Semaphore : Semaphore is simply a variable that is non-negative and shared between threads. A semaphore is a
signaling mechanism, and a thread that is waiting on a semaphore can be signaled by another thread. It uses two
atomic operations, 1)wait, and 2) signal for the process synchronization.
A semaphore either allows or disallows access to the resource, which depends on how it is set up.


Mutex : The full form of Mutex is Mutual Exclusion Object. It is a special type of binary semaphore which used for
controlling access to the shared resource. It includes a priority inheritance mechanism to avoid extended priority
inversion problems. It allows current higher priority tasks to be kept in the blocked state for the shortest time possible.
However, priority inheritance does not correct priority- inversion but only minimizes its effect.


Main Differences b/w Mutex and Semaphore :

1) Mutex is a locking mechanism whereas Semaphore is a signaling mechanism

2) Mutex is just an object while Semaphore is an integer

3) Mutex has no subtype whereas Semaphore has two types, which are counting semaphore and binary semaphore.

4) Semaphore supports wait and signal operations modification, whereas Mutex is only modified by the process that
may request or release a resource.

5) Semaphore value is modified using wait () and signal () operations, on the other hand, Mutex operations are locked
or unlocked.

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 : 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)

1) OnCreate(): It is called when activity is created. Using this, the views are created and data is collected from bundles.

2) OnStart(): It is called if the activity is becoming visible to the user. It may be succeeded by onResume() if the activity comes to the foreground, or onStop() if it becomes hidden.

3) OnResume(): It is called when the activity will start an interaction with the user.

4) OnPause(): This is called when the activity is moving to the background but hasn’t been killed yet.

5) OnStop(): This is called when an activity is no longer visible to the user.

6) OnDestroy(): This is called when the activity is finished or destroyed.

7) OnRestart(): This is called after the activity has been stopped, prior to it being started again.

An intent is a messaging object that is used to request an action from other components of an application. It can also be used to launch an activity, send SMS, send an email, display a web page, etc.

It shows notification messages to the user from within an Android-enabled device. It alerts the user of a particular state that occurred. There are two types of intents in Android:

1) Implicit Intent- Used to invoke the system components.
2) Explicit Intent- Used to invoke the activity class.

The context in Android is the context of the current state of the application or object. The context comes with services like giving access to databases and preferences, resolving resources, and more.

There are two types of context. They are : 

Activity context : 

1) This activity context is attached to the lifecycle of an activity.
2) The activity context can be used when you are passing the context in the scope of an activity or you need the context whose lifecycle is attached to the context of the activity.


Application context : 

1) This application context is attached to the lifecycle of an application.
2) The application context should be used where you need a context whose lifecycle is separate from the current context or when you are passing a context beyond the scope of activity.

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.