SDE - 1

The brute force solution is based on the idea that if the two ends of a string are the same, then they must be included in the longest palindrome subsequence. Otherwise, both ends cannot be included in the longest palindrome subsequence. So, recursion can be used here. 
Time Complexity of this approach would be exponential. 

This solution can be optimized using dynamic programming. 
Let dp[l][r] denote the length of the longest palindromic subsequence of s[l..r].
There are 2 options:
o If s[l] == s[r] then dp[l][r] = dp[l+1][r-1] + 2
o Elif s[l] != s[r] then dp[l][r] = max(dp[l+1][r], dp[l][r-1]).
Then dp[0][n-1] is our result.

The idea is to traverse all the leaves and connect them by changing their left and right pointers. We also need to remove them from the Binary Tree by changing left or right pointers in parent nodes. 
One way to solve this is to add the leaves at the beginning of the current linked list and update the head of the list using the pointer to head pointer. Since we insert at the beginning, we need to process leaves in reverse order. For reverse order, we first traverse the right subtree, then the left subtree. We use return values to update left or right pointers in parent nodes.

The brute force solution is to run two loops, the outer loop picks all characters one by one, the inner loop counts the number of occurrences of the picked character. We keep track of odd counts. Time complexity of this solution is O(n2). 
We can do it in O(n) time using a count array. 
Steps : 
1. Create a count array of alphabet size which is typically 256. Initialize all values of count array as 0.
2. Traverse the given string and increment count of every character.
3. Traverse the count array and if the count array has more than one odd values, return false. Otherwise, return true.

Recursion can be used here. Once the parent node is processed, make recursive calls for the children node. 
For serializing the tree into a list : 
• If node is null, store -1 in list and return
• Store the data at current node in list.
• Call function recursively for left and right subtrees.
• Return the list.
For deserializing the list into a tree : 
• If there are no more elements in list, return null.
• Create new node for storing current element.
• Call function recursively for left and right subtrees.
• Return the tree.

The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element. 
Algorithm : 

To shuffle an array a of n elements (indices 0..n-1):
for i from n - 1 down to 1 do
j = random integer with 0 <= j <= i
exchange a[j] and a[i]

Time Complexity: O(n), assuming that the function rand() takes O(1) time.
Auxiliary Space: O(1)

A rolling hash is a hash function where the input is hashed in a window that moves through the input.
A few hash functions allow a rolling hash to be computed very quickly—the new hash value is rapidly calculated given only the old hash value, the old value removed from the window, and the new value added to the window—similar to the way a moving average function can be computed much more quickly than other low-pass filters.
One of the main applications is the Rabin–Karp string search algorithm, which uses the rolling hash.

Tip 1: Mapping of current characters can be stored in a map. 
To check for two strings to be isomorphic using a map :
1) If lengths of str1 and str2 are not same, return false.
2) Do following for every character in str1 and str2
a) If this character is seen first time in str1, then current of str2 must have not appeared before.
(i) If current character of str2 is seen, return false. Mark current character of str2 as visited.
(ii) Store mapping of current characters.
b) Else check if previous occurrence of str1[i] mapped to same character.

Tip 1: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.
Tip 2 : Design your structure and functions according to the requirements and try to convey your thoughts properly to the interviewer so that you do not mess up while implementing the idea .

Use two stacks: one to store actual stack elements and the other as an auxiliary stack to store minimum values. 
The idea is to do push() and pop() operations in such a way that the top of the auxiliary stack is always the minimum. 

Push(int x) // inserts an element x to Special Stack 
1) push x to the first stack (the stack with actual elements) 
2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y. 
…..a) If x < y then push x to the auxiliary stack. 
…..b) If x > y then push y to the auxiliary stack.
int Pop() // removes an element from Special Stack and return the removed element 
1) pop the top element from the auxiliary stack. 
2) pop the top element from the actual stack and return it.

int getMin() // returns the minimum element from Special Stack 
1) Return the top element of the auxiliary stack.