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)

Algorithm :
1)Create a recursive function (say TreeNode*build(arr,start,end) ) which returns the root of the newly cretaed BST . The parameters of this function will be the sorted array , left end of the array , right end of the array .

2)Now, find the mid element of the array and make it as the root i.e., 
TreeNode*root=new TreeNode(arr[mid]); where mid=(start+end)/2


3)Call the build function again for the left half of the array and store the result in root->left . i.e. ,
root->left=func(arr,start,mid-1);

4)Similarly , call the build function for the right half of the array and store the result in root->right . i.e. ,
root->right=func(arr,mid+1,end);

5)Finally , return root .

The approach is to use the preorder traversal of the tree to traverse the tree and check that we have visited the current vertical level and if visited then we can check for the smaller horizontal level node and store it. Else we can just update the vertical level as visited and store the node and horizontal level of the current node.

1) We have to create the map to check whether the horizontal level is visited or not as it will state the horizontal distance of the node from the root node. Where key will represent the horizontal distance and the value is the pair containing the value and level of each node.
2) We will traverse the tree using the preorder traversal.
3) Every time we check if the level of the current horizontal distance is less than the max level seen till now then we will update the value and the level for this horizontal distance.
4) We will pass level-1 for the left child and level+1 for the right child to get the vertical level.
5) Print the values present in the map.

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)

Tip 1: Firstly, remember that the system design round is extremely open-ended and there’s no such thing as a standard answer. Even for the same question, you’ll have a totally different discussion with different interviewers. 

Tip 2: Before you jump into the solution always clarify all the assumptions you’re making at the beginning of the interview. Ask questions to identify the scope of the system. This will clear the initial doubt, and you will get to know what are the specific detail interviewer wants to consider in this service. 

Some standard requirements for this problem would be : 

1) Given a long URL, the service should generate a shorter and unique alias of it.
2) When the user hits a short link, the service should redirect to the original link.
3) Links will expire after a standard default time span.
4) The system should be highly available. This is really important to consider because if the service goes down, all the URL redirection will start failing.
5) URL redirection should happen in real-time with minimal latency.
6) Shortened links should not be predictable.



Tip 3: Now knowing about the requirements , note down all the important factors to take into consideration while solving this problem . Most common factors include : 

1)Traffic 
2) URL Length
3) Data Capacity Modeling
4) URL Shortening Logic (Encoding basically) - Standard Hashing Techniques like Base62 , MD5 should be known
5) Choice of Database - SQL vs NoSQL


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.

Prerequisite to solve this problem : Multithreading

The idea is to create two threads and print even numbers with one thread and odd numbers with another thread. Below are the steps:

1) Create two threads T1 and T2 , where T1 and T2 are used to print odd and even numbers respectively.
2) Maintain a global counter variable and start both threads.
3) If the counter is even in the Thread T1, then wait for the thread T2 to print that even number. Otherwise, print that odd number, increment the counter and notify to the Thread T2 .
4)If the counter is odd in the Thread T2, then wait for the thread T1 to print that even number. Otherwise, print that even number, increment the counter and notify the Thread T1.