SDE - 2

This was a preety standard Binary Search Question and I had solved this question before on platforms like LeetCode and CodeStudio . I was asked this question to test my implementation skills and how well do I handle Edge Cases.

Approach :

1) The idea is to find the pivot point, divide the array in two sub-arrays and perform binary search.

2) The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only element for which next element to it is smaller than it.

3) Using the above statement and binary search pivot can be found.

4) After the pivot is found out divide the array in two sub-arrays.

5) Now the individual sub–arrays are sorted so the element can be searched using Binary Search.


TC : O(Log(N))
SC : O(1)

Approach :

1) Create a 2-D dp boolean vector(with all false initially) where dp[i][j] states whether s[i...j] is a palindrome or not and initialise a variable ans=1 which will store the final answer.

2) Base Case : For every i from 0 to n-1 fill dp[i][i]=1 ( as a single character is always a palindrome ).

3) Now, run 2 loops first one from i=n-1 to i=0 (i.e., tarverse from the back of the string) and the second one from j=i+1 to n.

4) For every s[i]==s[j] , check if(j-i==1 i.e., if s[i] and s[ j] are two consecutive same letters) or if(dp[i+1][j-1]==1 or not i.e., if the string s[i+1,....j-1] is palindrome or not.

5) Because if the string s[i+1,....j-1] is a palindrome and s[i]==s[j] then s[i] and s[j] can be appended at the starting and the ending position of s[i+1,...j-1] and s[i...j] will then be a palindrome , so mark dp[i][j]=1 and update the answer as ans=max(ans , j-i+1).

6) Finally return the ans.


TC : O(N^2) where N=length of the string s
SC : O(N^2)

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

Approach : 

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.

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 specific detail the 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 types of rounds.

The SOLID principle is an acronym of the five principles which is given below :

1) Single Responsibility Principle (SRP)
2) Open/Closed Principle
3) Liskov’s Substitution Principle (LSP)
4) Interface Segregation Principle (ISP)
5) Dependency Inversion Principle (DIP)


Uses of SOLID design principles :

1) The SOLID principle helps in reducing tight coupling.

2) Tight coupling means a group of classes are highly dependent on one another which we should avoid in our code.

3) Opposite of tight coupling is loose coupling and our code is considered as a good code when it has loosely-coupled classes.

4) Loosely coupled classes minimize changes in your code, helps in making code more reusable, maintainable, flexible and stable.


Explaining the 5 SOLID principles one by one :

1) Single Responsibility Principle : This principle states that “a class should have only one reason to change” which means every class should have a single responsibility or single job or single purpose. Use layers in your application and break God classes into smaller classes or modules.


2) Open/Closed Principle : This principle states that “software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification” which means you should be able to extend a class behavior, without modifying it. Using this principle separates the existing code from the modified code so it provides better stability, maintainability and minimizes changes as in your code.


3) Liskov’s Substitution Principle : According to this principle “Derived or child classes must be substitutable for their base or parent classes“. This principle ensures that any class that is the child of a parent class should be usable in place of its parent without any unexpected behavior.


4) Interface Segregation Principle : This principle is the first principle that applies to Interfaces instead of classes in SOLID and it is similar to the single responsibility principle. It states that “do not force any client to implement an interface which is irrelevant to them“. Here your main goal is to focus on avoiding fat interface and give preference to many small client-specific interfaces.


5) Dependency Inversion Principle : Two key points are here to keep in mind about this principle
a) High-level modules/classes should not depend on low-level modules/classes. Both should depend upon abstractions.
b) Abstractions should not depend upon details. Details should depend upon abstractions.

1) Garbage Collection in Java is a process by which the programs perform memory management automatically.

2) The Garbage Collector(GC) finds the unused objects and deletes them to reclaim the memory. I

3) In Java, dynamic memory allocation of objects is achieved using the new operator that uses some memory and the memory remains allocated until there are references for the use of the object.

4) When there are no references to an object, it is assumed to be no longer needed, and the memory, occupied by the object can be reclaimed.

5) There is no explicit need to destroy an object as Java handles the de-allocation automatically. The technique that accomplishes this is known as Garbage Collection. Programs that do not de-allocate memory can eventually crash when there is no memory left in the system to allocate. These programs are said to have memory
leaks.


Garbage collection in Java happens automatically during the lifetime of the program, eliminating the need to de-allocate memory and thereby avoiding memory leaks.

In C language, it is the programmer’s responsibility to de-allocate memory allocated dynamically using the free() function. This is where Java memory management leads.