SDE - 1

Step 1: I started by thinking about the properties of subsequences. The number of subsequences in an array is 2^n, where n is the length of the array, because each element can either be included or excluded from a subsequence.

Step 2: I then implemented a simple formula using the power of 2 to calculate the total number of subsequences:
Total Subsequences = 2^n

Step 3: The interviewer pointed out that this formula counts the empty subsequence as well, so I adjusted the solution by subtracting 1 to exclude the empty subsequence.

Step 4: The interviewer was satisfied with the solution, and I concluded that the correct result is 2^n - 1 subsequences (excluding the empty subsequence).

Step 1: I began by initializing two pointers, one for each array (i=0 and j=0), and an empty result array.
Step 2: I used a while loop to compare the elements at the pointers A[i] and B[j]. I added the smaller element to the result array and moved the pointer of the array from which the element was taken.
Step 3: After completing the main loop, there could still be remaining elements in either A[] or B[], so I appended the rest of the elements from the array that still had remaining elements.
Step 4: The interviewer suggested checking edge cases, such as one of the arrays being empty. I confirmed that the solution handles this case correctly, where the result is just the non-empty array.
Step 5: The interviewer was happy with my solution and suggested that the time complexity of this approach is O(N+M), which is optimal for merging sorted arrays.

Step 1: I started by performing a pre-order traversal of the binary tree to process each node.
Step 2: For each node, I checked whether the random pointer points to any of the node's descendants. To do this, I used a helper function that checks if a node is an ancestor of the current node (e.g., by performing a simple traversal of the left and right subtrees).
Step 3: If the random pointer points to one of the successors, I left it as is. Otherwise, I set the random pointer to NULL.
Step 4: The interviewer suggested making the function more efficient by storing the nodes in a hash map during the traversal. This way, I could check if the random pointer points to a valid node in constant time. I implemented the hash map and was able to optimize the solution.
Step 5: The interviewer was satisfied with the solution, which runs in O(N) time, where N is the number of nodes in the binary tree.

Step 1: I started by understanding that to form valid combinations of parentheses, for every opening parenthesis '(', there should be a matching closing parenthesis ')'. 

Step 2: I used a backtracking approach, where I recursively added opening and closing parentheses. I made sure that the number of closing parentheses never exceeded the number of opening parentheses. 

Step 3: For each valid combination, I ensured that no duplicates occurred by maintaining the condition that, at any point, the number of opening parentheses could not exceed N, and the number of closing parentheses could not exceed the number of opening parentheses already added. 

Step 4: I generated all valid combinations and returned the result. To optimize, I used a set or list to store only unique combinations (though for backtracking, this is generally not needed if the logic ensures no duplicates). 

Step 5: The interviewer liked the backtracking approach and confirmed that the solution is optimal, running in O(4^n / n^(3/2)) time, which is the time complexity for generating balanced parentheses combinations.

Step 1: I first created a boolean array visited[] of size 256 (since there are 256 possible ASCII characters) to track whether a character has already been seen.
Step 2: I then looped through the string character by character. For each character, I checked if it had been marked as visited in the visited[] array.
Step 3: If it hadn’t been visited yet, I added the character to the result string and marked it as visited in the visited[] array.
Step 4: If the character had already been visited, I simply skipped it and moved on to the next character.
Step 5: The interviewer was happy with the solution and pointed out that this approach works in linear time, O(n), as we are only iterating through the string once.