SDE - 2

Naive Solution :
 

A simple solution is to traverse each element and check if there’s another number in the array which can be added to it to give sum.

TC : O(n^2)
SC : O(1)


Efficient Solution (Using Hashing ) :

We create an empty hash table. Now we traverse through the array and check for pairs in the hash table. If a matching element is found, we print the pair number of times equal to the number of occurrences of the matching element.

TC : O(k+n) where k is the count of pairs with given sum
SC : O(n)

Approach 1 : Naive Recursive Approach

A naive approach is to start from the first element and recursively call for all the elements reachable from first element. The minimum number of jumps to reach end from first can be calculated using minimum number of jumps needed to reach end from the elements reachable from first.

minJumps(start, end) = Min ( minJumps(k, end) ) for all k reachable from start

TC : O(n^n)
SC : O(n)


Approach 2 : Dynamic Programming - Tabulation

We can solve this iteratively as well. For this, we start from the last index. We need 0 jumps from nums[n-1] to reach the end. We store this as dp[n - 1] = 0 and then iteratively solve this for each previous index till the 0th index. Here dp[i] denotes minimum jumps required from current index to reach till the end.

1) For each index, we explore all the possible jump sizes available with us.
2) The minimum jumps required to reach the end from the current index would be - min(dp[jumpLen]), where 1 <= jumpLen <= nums[currentPostion]

TC : O(n^2)
SC : O(n)



Approach 3 : Most optimal - Greedy-BFS

We can iterate over all indices maintaining the furthest reachable position from current index - maxReachable and currently furthest reached position - lastJumpedPos. Everytime we will try to update lastJumpedPos to furthest possible reachable index - maxReachable.

Updating the lastJumpedPos separately from maxReachable allows us to maintain track of minimum jumps required. Each time lastJumpedPos is updated, jumps will also be updated and store the minimum jumps required to reach lastJumpedPos (On the contrary, updating jumps with maxReachable won't give the optimal (minimum possible) value of jumps required).

We will just return it as soon as lastJumpedPos reaches(or exceeds) last index.

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

Algorithm :

1) Create a graph such that there is a edge between each pair of enemies.

2) We need to find that the above graph is bipartite or not. Check whether the graph is 2-colorable or not

3) We can do that by running dfs and using an auxilary array col to store the assigned col of the node.

4) If we can color the graph with two color such that no two enemies have same color then only we can create two teams.


TC : O(V+E) where V=number of vertices and E=number of edges
SC : O(V)

Approach 1 (Using DP ) :

Observe that , If a chain of length k ends at some pairs[i], and pairs[i][1] < pairs[j][0], we can extend this chain to a chain of length k+1

Steps :

1) Sort the pairs by first coordinate, and let dp[i] be the length of the longest chain ending at pairs[i].

2) When i < j and pairs[i][1] < pairs[j][0], we can extend the chain, and so we have the candidate answer dp[j] = max(dp[j], dp[i] + 1).

TC : O(N^2)
SC : O(N)


Approach 2 (Greedy based):

We can greedily add to our chain.

Steps:

1) Choosing the next addition to be the one with the lowest second coordinate is at least better than a choice with a larger second coordinate.

2) Consider the pairs in increasing order of their second coordinate.
 

3) We'll try to add them to our chain. If we can, by the above argument we know that it is correct to do so.

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

1) TCP or TCP/IP is the Transmission Control Protocol/Internet Protocol.

2) It is a set of rules that decides how a computer connects to the Internet and how to transmit the data over the network.

3) It creates a virtual network when more than one computer is connected to the network and uses the three ways handshake model to establish the connection which makes it more reliable.

1) DHCP is the Dynamic Host Configuration Protocol.

2) It is an application layer protocol used to auto-configure devices on IP networks enabling them to use the TCP and UDP-based protocols.

3) The DHCP servers auto-assign the IPs and other network configurations to the devices individually which enables them to communicate over the IP network.

4) It helps to get the subnet mask, IP address and helps to resolve the DNS. It uses port 67 by default.

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.

Approach :

Pastebin allows users to store text-based data over the internet for a set period of time and generate a unique URL corresponding uploaded data to share that with anyone. Users who create that data, can also modify it by logging in to the same account.

Database Schema :

i) users(userID, name, createdAT, metaData)
ii) paste(pasteID, content, URL, createdAt, expiryAt)

Algorithm :

1) create_paste(api_key, content, expiryAt)- this will return URL generated and success message that paste is stored successfully and in case of error it will return error.

2) read_paste(URL)- returns corresponding original content and a error code in case of any failure.


Architecture and Components :

For creating the backend of pastebin we can either use serverless architecture which will use AWS lambda functions for both APIs create paste and read paste or we can use microservice architecture which will require different services for creating paste and reading paste.


Storing Content :

It will not be a good choice to keep all data in our database(SQL or noSQL). Because storing 1000TBs of data in DB is not a good choice, so we can use hybrid approach we can use Object storage service like AWS S3 in which we can store the content in blob(binary large object) form and for the data less than 100KB we can store it in our Database only.


Cache :

For eliminating Cache, we can use LRU here, URLs which aren’t used frequently we can replace them with frequently used URLs. We need to synchronize cache data with original data in the background, so that consistency is always there in content.


Key Generating Service :

This service helps in generating random 10 letter keys beforehand and will store them in Redis DB, Now whenever we are storing a paste and we need a URL for, we will look up in our Redis DB and see which key is not used, and after using the key we need to mark it used.


Expiry time URL :

We have a cleanup Sync service which will lookup in our database if current time is greater than expiry time set while creating a paste, it will delete the entry from DB and also delete the file present in AWS S3(Object Store).
 

General Tip : Finally , for acing System Design Rounds I would suggest watching Gaurav Sen's System Design Videos on YouTube and for hands on practice there is a Guided Path solely for System Design on CodeStudio which is very useful while preparing for these type of rounds.

1) Data abstraction is a very important feature of OOPs that allows displaying only the important information and hiding the implementation details.

2) For example, while riding a bike, you know that if you raise the accelerator, the speed will increase, but you don’t know how it actually happens.

3) This is data abstraction as the implementation details are hidden from the rider.

Data abstraction can be achieved through:
i) Abstract class
ii) Abstract method

The Diamond Problem : The Diamond Problem occurs when a child class inherits from two parent classes who both share a common grandparent class i.e., when two superclasses of a class have a common base class.

Solving the Diamond Problem in C++ : The solution to the diamond problem is to use the virtual keyword. We make the two parent classes (who inherit from the same grandparent class) into virtual classes in order to avoid two copies of the grandparent class in the child class.

1) Friend functions of the class are granted permission to access private and protected members of the class in C++. They are defined globally outside the class scope. Friend functions are not member functions of the class.

2) A friend function is a function that is declared outside a class but is capable of accessing the private and protected members of the class.

3) There could be situations in programming wherein we want two classes to share their members. These members may be data members, class functions or function templates. In such cases, we make the desired function, a friend to both these classes which will allow accessing private and protected data members of the class.

4) Generally, non-member functions cannot access the private members of a particular class. Once declared as a friend function, the function is able to access the private and the protected members of these classes.
 

Some Characteristics of Friend Function in C++ :

1) The function is not in the ‘scope’ of the class to which it has been declared a friend.
 

2) Friend functionality is not restricted to only one class
 

3) Friend functions can be a member of a class or a function that is declared outside the scope of class.
 

4) It cannot be invoked using the object as it is not in the scope of that class.
 

5) We can invoke it like any normal function of the class.