SDE - 1

The approach is very simple. Traverse both lists and One by one pick nodes of both lists and add the values. If the sum is more than 10 then make carry as 1 and reduce sum. If one list has more elements than the other then consider the remaining values of this list as 0.

The steps are:
1. Traverse the two linked lists from start to end
2. Add the two digits each from respective linked lists.
3. If one of the lists has reached the end then take 0 as its digit.
4. Continue it until both the end of the list.
5. If the sum of two digits is greater than 9 then set carry as 1 and the current digit as sum % 10

This problem can be solved efficiently by using the technique of hashing. Use a hash_map to check for the current array value x(let), if there exists a value target_sum-x which on adding to the former gives target_sum. This can be done in constant time. Let’s look at the following example.

arr[] = {0, -1, 2, -3, 1}
sum = -2
Now start traversing:
Step 1: For ‘0’ there is no valid number ‘-2’ so store ‘0’ in hash_map.
Step 2: For ‘-1’ there is no valid number ‘-1’ so store ‘-1’ in hash_map.
Step 3: For ‘2’ there is no valid number ‘-4’ so store ‘2’ in hash_map.
Step 4: For ‘-3’ there is no valid number ‘1’ so store ‘-3’ in hash_map.
Step 5: For ‘1’ there is a valid number ‘-3’ so the answer is 1, -3

So, this was a binary search question and there was an easier version of this question in which you had to find only the integer which is closest to the square root of that number, so here you had to only change your code a bit, but the logic was a bit tricky to find, but eventually, I came up with the solution and then the interviewer was quite impressed. I also had to tell the time and space complexity and also explained to them why was this the most optimal approach.

Initially, I thought that this was a tricky problem but I kept thinking out loud, and they were also able to see where and how was I thinking, later I came up with the solution and it was the optimum one, the interviewer again asked me to write how will you represent the generic tree, and then I wrote the code for the tree using a class, the interviewer was again happy to see that, later I wrote the code for the problem and also told him the time and space complexities.

Approach: The idea is to use two variables i initialized to 1 and j initialized to the height of the tree and run a while loop which won't break until i becomes greater than j. We will use another variable flag and initialize it to 0. Now in the while loop, we will check a condition that if the flag is equal to 0 we will traverse the tree from right to left and mark the flag as 1 so that next time we traverse the tree from left to right and then increment the value of i so that next time we visit the level just below the current level. Also when we will traverse the level from the bottom we will mark the flag as 0 so that next time we traverse the tree from left to right and then decrement the value of j so that next time we visit the level just above the current level. Repeat the whole process until the binary tree is completely traversed.

Tip 1 : Try to tell your approach continuously, as if you are stuck then the interviewer might give a hint.
Tip 2 : Be confident and speak what you think.
Tip 3 : Don't give up on the first try, try to come up with some solution. They see your approach.

Tip 1 : Try to tell your approach continuously, as if you are stuck then the interviewer might give a hint.
Tip 2 : Be confident and speak what you think.
Tip 3 : Don't give up on the first try, try to come up with some solution. They see your approach.