SDE - 1

Approach : 

Form a recursive function, which will follow a path and check if the path reaches the destination or not. If the path does not reach the destination then backtrack and try other paths. But in case it reaches the destination print the current ‘SOLUTION’ matrix.

Steps : 
f('i', ‘j'):
1) If rat reaches the destination, print the solution matrix.
2) Else:
2.1) If not valid('MAZE[i][j]' ) return
2.2) Else ‘SOLUTION[i][j]' =1
2.3) f(i-1,j) ; f(i+1,j) , f(i, j-1) , f(i,j+1) // Recursive calls
2.4) ‘SOLUTION[i][j]' = 0 // Backtracking

TC : O(4 ^ (N ^ 2)), where ‘N’ is the dimension of the matrix.
SC : O(N*N), where 'N' is the dimension of the matrix

This was a very standard DP problem and I had already solved it on platforms like LeetCode and CodeStudio so I
was able to come up with the logic and code it preety fast.

Steps :
1) Create a two-dimensional array, ‘dp’, where ‘dp[i][j]’ will denote the total number of ways to make j value by using i
coins.

2) Run 2 loops ,1st one from 1 to value and second one throught the array denominations.

3) Fill dp array by the recurrence relation as follows:
ways[i][j] = ways[i-1][j] + ways[i][j-denominations[i]] (if j-denominations[i]>=0) 
Where first term represents that we have excluded that coin and,
Second term represents that we have included that coin.

4) Base Case : Fill dp[0]=0 (as we can make 0 amount by giving no coins at all) and the remaining indices with
INT_MAX value

5) Finally , if dp[value]==INT_MAX , return -1 as it is not possible to make "value" using the given coins else return
dp[value] itself

TC : O(N*V) where N=number of coins and V=Value to be made
SC : O(N*V)

IPv4 : IPv4 is an IP version widely used to identify devices on a network using an addressing system. It was the first version of IP deployed for production in the ARPANET in 1983. It uses a 32-bit address scheme to store 2^32 addresses which is more than 4 billion addresses. It is considered the primary Internet Protocol and carries 94% of Internet traffic.

IPv6 : IPv6 is the most recent version of the Internet Protocol. This new IP address version is being deployed to fulfill the need for more Internet addresses. It was aimed to resolve issues that are associated with IPv4. With 128-bit address space, it allows 340 undecillion unique address space. IPv6 is also called IPng (Internet Protocol next generation).

Differences b/w IPv4 and IPv6 are : 

1) IPv4 is 32-Bit IP address whereas IPv6 is a 128-Bit IP address.
2) IPv4 is a numeric addressing method whereas IPv6 is an alphanumeric addressing method.
3) IPv4 binary bits are separated by a dot(.) whereas IPv6 binary bits are separated by a colon(:).
4) IPv4 offers 12 header fields whereas IPv6 offers 8 header fields.
5) IPv4 supports broadcast whereas IPv6 doesn’t support broadcast.
6) IPv4 has checksum fields while IPv6 doesn’t have checksum fields

Open System Interconnections (OSI) is a network architecture model based on the ISO standards. It is called the OSI model as it deals with connecting the systems that are open for communication with other systems.

The OSI model has seven layers. The principles used to arrive at the seven layers can be summarized briefly as below:

1) Create a new layer if a different abstraction is needed.
2) Each layer should have a well-defined function.
3) The function of each layer is chosen based on internationally standardized protocols.

Unicast : The unicast addressing method indicates that communication through a network involves a unique sender (source) and a single receiver (destination). Making an analogy, we can see unicast communication as a particular conversation with a single person (unicast) at a party with many people (network).

Multicast : A multicast address can be used to deliver a package to a group of destinations. Any packet sent to a multicast address, will be delivered to every host that has joined that particular group.Since IPv6 has no support for the broadcast address, any function that used to rely on broadcasts will now be using multicast addresses.Multicast addresses are in the range of FF00::/8.

Anycast : The anycast address is very similar to the multicast address, but packets will be delivered to only one random host, instead of the entire group.Anycast address don’t have a specific range, as they are exactly the same as regular unicast addresses. This means that a hosts has no way to distinguish a unicast from an anycast address when it sends a packet.

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)

Answer :

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.

Answer :

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.

If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly half the original time, i.e. 30 minutes to burn completely.

1) 0 minutes – Light stick 1 on both sides and stick 2 on one side.
2) 30 minutes – Stick 1 will be burnt out. Light the other end of stick 2.
3) 45 minutes – Stick 2 will be burnt out. Thus 45 minutes is completely measured.