SDE - Intern

A simple solution is to remove all subsequences one by one and check if the remaining string is palindrome or not. The time complexity of this solution is exponential.

An efficient approach uses the concept of finding the length of the longest palindromic subsequence of a given sequence. 

Algorithm: 

1. str is the given string.
2. n length of str
3. len be the length of the longest 
palindromic subsequence of str
4. minimum number of deletions 
min = n - len

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.

If the execution is traced for this method, it can be seen that there will be overlapping subproblems. For example, minJumps(3, 9) will be called two times as arr[3] is reachable from arr[1] and arr[2]. So this problem has both properties (optimal substructure and overlapping subproblems) of Dynamic Programming.

Method 2: Dynamic Programming. 
Approach: 

In this way, make a jumps[] array from left to right such that jumps[i] indicate the minimum number of jumps needed to reach arr[i] from arr[0].
To fill the jumps array run a nested loop inner loop counter is j and outer loop count is i.
Outer loop from 1 to n-1 and inner loop from 0 to i.
if i is less than j + arr[j] then set jumps[i] to minimum of jumps[i] and jumps[j] + 1. initially set jump[i] to INT MAX
Finally, return jumps[n-1].

Approach: The idea is very simple to solve this problem. Calculate the sum of digits of a given number and then for each index, remove that digit and try all possible digits from 0 to 9 and see if the sum is divisible by 3 or not. Follow the steps below to solve the problem:

Initialize the variable sum as 0 to store the sum of digits of the number.
Iterate over a range [0, N] using the variable i and perform the following steps:
Add the value of digit at i-th index in the variable sum.
Initialize the variable count as 0 to store the answer.
If the number itself is divisible by 3 then increment count by one.
Iterate over a range [0, N] using the variable i and perform the following steps:
Initialize the variable remaining_sum as sum-(number.charAt(i)-48).
Iterate over a range [0, 9] using the variable j and perform the following steps:
Add the value of j to the variable remaining_sum and if remaining_sum is divisible by 3 and j is not equal to the digit at i-th index, then add the value of count by 1.
After performing the above steps, print the value of count as the answer.

I started with an approach where I would iterate over the list of words and then match every other word in the List to check if they are anagrams, If yes then I would store them together.
but this solution will take O(N^2) time complexity.

He then gave me a hint to maybe think about some other data structure that I can use - and it struck me to the idea of using hashmap 
and I landed on the following approach:
A simple method is to create a Hash Table. Calculate the hash value of each word in such a way that all anagrams have the same hash value. Populate the Hash Table with these hash values. Finally, print those words together with the same hash values. A simple hashing mechanism can be modulo sum of all characters. With modulo sum, two non-anagram words may have the same hash value. This can be handled by matching individual characters.

Here, we first sort each word, use the sorted word as a key and then put an original word on a map. The value of the map will be a list containing all the words which have the same word after sorting. 
Lastly, we will print all values from the hashmap where the size of values will be greater than 1.

He then appreciated the solution and asked me if the solution can be further optimized.
so I gave it a hard thought and I was hitting in the bushes trying to communicate with him and I'd say we collective came to the next approach:
In the previous approach, we were sorting every string in order to maintain a similar key, but that cost extra time in this approach will take the advantage of another hashmap to maintain the frequency of the characters which will generate the same hash function for different string having same frequency of characters.
Here, we will take HashMap, the inner hashmap will count the frequency of the characters of each string and the outer HashMap will check whether that hashmap is present or not if present then it will add that string to the corresponding list.

It was a new problem to me. I started with a complex solution having something to do with DP but soon realized that I was making it too complex. 
Then I noticed that I could derive a mathematical formula for the conversion. further going on with this solution I realized it's similar to converting binary to decimals bit instead base 2, it could be base 26.

ex. To convert CDA,
3*26*26 + 4*26 + 1
= 26(3*26 + 4) + 1
= 26(0*26 + 3*26 + 4) + 1

result = 26*result + s[i] - 'A' + 1

He then asked me what would be the case if the question was reversed.
I made some minor changes and come with a solution in little time.

Tip 1 : Don't get nervous.
Tip 2 : Think with a cool mind.
Tip 3 : Thoroughly explain your approach

Tip 1 : Be confident and enthusiastic.
Tip 2 : Ask questions, it's not just an opportunity for them ti know you but for you also to know the company.
Tip 3 : Keep the conversation going.