SDE - Intern

I simply gave the interviewer a hashing based approach and made changes in the original string and he was pretty much satisfied by my approach.

A palindromic subsequence is a sequence of characters that reads the same forwards and backwards, but not necessarily consecutively. The longest palindromic subsequence (LPS) of a given string is the longest subsequence that is a palindrome.

We can start populating the dp table from the bottom right corner and move towards the top left corner, using the following approach:

Initialize the diagonal cells of the dp table with a value of 1, as the longest palindromic subsequence of a single character is always 1.

Iterate over the dp table in a bottom-up manner, starting from the second last row and the second last column, up to the first row and the first column.

For each cell dp[i][j], compare the characters at the i-th and j-th positions of the input string:
a. If the characters are the same, then dp[i][j] = dp[i+1][j-1] + 2. This means that the longest palindromic subsequence of the substring from i-th to j-th characters is equal to the longest palindromic subsequence of the substring from (i+1)-th to (j-1)-th characters, plus 2, as we are including the matching characters in the subsequence.
b. If the characters are different, then dp[i][j] = max(dp[i+1][j], dp[i][j-1]). This means that the longest palindromic subsequence of the substring from i-th to j-th characters is equal to the maximum of the longest palindromic subsequence of the substring from (i+1)-th to j-th characters, and the longest palindromic subsequence of the substring from i-th to (j-1)-th characters, as we need to choose the longer one.

After iterating over all the cells of the dp table, the top right cell dp[0][n-1] (where n is the length of the input string) will represent the length of the longest palindromic subsequence of the entire input string.

To retrieve the actual longest palindromic subsequence, we can trace back from dp[0][n-1] to dp[0][0] by following the arrows (i.e., the choices made in step 3) and including the characters in the input string corresponding to those choices. This will give us the longest palindromic subsequence of the input string.

Velocity of approach for two trains = (40+40)km/hr

Time taken for the trains to collide = 80km/80km/hr = 1hour

The total distance travelled by the bird = 100km/hr * 1hr = 100km

Through this puzzle, the interviewer is testing your approach. Consider yourself rejected if the approach you took involves calculating distance from X to Y, and then Y to X, and so on.

I use recursion to solve this problem, and assigned color to each node and check at last whether it is giving safe configuration or not that is all nodes are of red and blue color and adjacent nodes have not the same color.