SDE - 2

It is a greedy approach where we will form a min-heap of all the lengths of sticks that are given to us. In this approach, we will always find two sticks with minimum length and connect them and add their cost to our answer. Also, we will add the newly formed stick back into our min-heap. And then we will continue to do the same procedure for all the remaining sticks. Since we need to minimize the cost to connect all the sticks into one, therefore we have to greedily pick the two smallest lengths of sticks from given lengths and add them to the answer and continue it until we are left with one stick in our heap. We are picking the two smallest sticks every time because the new stick formed will also be added to our cost later. Therefore picking smaller sticks will reduce the total cost than using longer sticks which will increase the cost.

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) 

Note: Since the graph can be disconnected so run dfs on each component.

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.

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.

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