SDE - Intern

I had the most optimized approach right from the start, as the question was straightforward and the interview time was very limited. My approach was to sort the array in ascending order and check the condition on the next element, incrementing the pointer accordingly until we reach N. The interviewer was satisfied with the approach and instructed me to code it directly.

If the size of the array is 1, return 1.

I used tree traversal using recursion. When you reach node N, return 1 from there (base case) and accordingly increase your count in the recursion itself. The interviewer was satisfied with the approach and instructed me to code it directly.

What if node N is not present?

Is node N the address of that node or the node value?

I provided two approaches for the same problem, one using hashing and the other using sorting, specifying the space and time complexity for each. The interviewer instructed me to code using the sorting approach.

If the value of N is 1, return false.

I initially explained the approach using a frequency array and traversing it. The interviewer pointed out that the constraints for A[i] were very high, so creating a frequency array was not feasible. I then used hashmaps to store the count of each element and traversed from the smallest to the largest element, storing the answer concurrently.

What if the array does not contain duplicates? The solution approach changes if the array has only distinct values.