Max & Min arrays

Question 1

Reverse Integer

Answer 1

1. Normal reverse operation using % * and /
   int newResult = result * 10 + x % 10;
2. Reconstruct the reverse number and check for equality
   if(((newResult - x % 10) / 10) != result) return 0;

Question 2

Longest palindrome substring

Answer 2

1. Expand around corner, odd and even, maxLen and llo

Question 3

No of ways of decode

Answer 3

1. Classic dp with recursion and memoisation

2. Do with one char and two chars

Question 4

K Frequent Element

Answer 4

1. Hashmap to store the occurence
2. Min heap to store the least occurence map.get(a) - map.get(b)
3. Add all the el to heap, if size > k poll
4. Finally poll the last remaining element

Question 5

Max path sum

Answer 5

1. Recursive
2. max(0, leftSum || rightSum)
3. maxPath = inOrder || maxSum
4. return max(left, right) + node.val;

Question 6

Merge sorted LL

Answer 6

1. l1 = mergeSort(l1.next, l2)

2. Use the same list, no need to create new LL

Question 7

Word search in a adjacent matrix

Answer 7

1. Use the count var to keep track of the current idx of the word
2. Handle the visited nodes, by making empty and undoing at the end

Question 8

Valid palindrome of sentences with punctuations

Answer 8

1. Use two pointer
2. Use character.isLetterOrDigit to consider digits as well
3. Check for charAt match

Question 9

Find first and last of duplicate el in sorted array

Answer 9

1. Two BST search
2. First to search for the firstIndex and second is for searching the endIndex
3. If target found for the first time, check whether its starting else checking on the left side
4. Do the same of the ending index

Question 10

Find peak element in array

Answer 10

1. BST
2. If current > current + 1 search left
3. If current < current + 1 search right
4. end at start == end return start

Question 11

IsCelebrity

Answer 11

1. for to get the possible celebrity candidate

2. If celebrity exists then the possible candidate will be compared against all other candidates

Question 12

Is tree symemtry

Answer 12

t1.val == t2.val
&& isSymmetric(t1.right, t2.left)
&& isSymmetric(t1.left, t2.right);

Question 13

Search in 2D matrix 1

Answer 13

1. Consider the whole matrix as an increasing order of array
2. pivotIdx = mid
3. pivotValue = matrix[idx/n][idx%n]
4. Rest all the binary logic

Question 14

Longest consecutive sequence

Answer 14

1. Store all the el in hashset
2. The logic is to find the the el - 1 not present in the set, and in the does a forloop to check whether from current no + 1 are consective and check for maxlen

Question 15

Perfect square

Answer 15

1. dp, with base[0] = 0 and fill the rest with integer max;
2. Iterate for i to n
3. iterate for every sqr j = 1 ; j *j <= i; j++
4. dp[i] = min(dp[i], dp[i - j * j] + 1)

Question 16

inOrderSuccessor

Answer 16

while(root != null) {
            if(p.val >= root.val) {
                root = root.right;
            } else {
                successor = root;
                root = root.left;
            }
        }