SDE - Intern

Case1: Every single character is a palindrome of length 1
L(i, i) = 1 (for all indexes i in given sequence)
Case2: If first and last characters are not same
If (X[i] != X[j]) L(i, j) = max{L(i + 1, j), L(i, j – 1)} 
Case3: If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2 
Case4: If there are more than two characters, and first and last characters are same
Else L(i, j) = L(i + 1, j – 1) + 2 

We can improve the time complexity using DP

Kadane’s algorithm for 1D array can be used to reduce the time complexity to O(n^3). The idea is to fix the left and right columns one by one and find the maximum sum contiguous rows for every left and right column pair. We basically find top and bottom row numbers (which have maximum sum) for every fixed left and right column pair. To find the top and bottom row numbers, calculate the sum of elements in every row from left to right and store these sums in an array say temp[]. So temp[i] indicates sum of elements from left to right in row i. If we apply Kadane’s 1D algorithm on temp[], and get the maximum sum subarray of temp, this maximum sum would be the maximum possible sum with left and right as boundary columns. To get the overall maximum sum, we compare this sum with the maximum sum so far.

The idea is to put all the opening brackets in the stack. Whenever you hit a closing bracket, search if the top of the stack is the opening bracket of the same nature. If this holds then pop the stack and continue the iteration. In the end if the stack is empty, it means all brackets are balanced or well-formed. Otherwise, they are not balanced.

Tip 1: Proper use of oops
Tip 2: Everything optimised
 

Tip 1: Read about topics like Kafka redis elastic search 
Tip 2: Java is preferred
Tip 3: Have at least one good project