SDE - Intern

Step 1: I first thought of a brute-force approach where I check all possible subarrays and verify whether all elements are distinct. This approach was simple but inefficient due to high time complexity.
Step 2: To optimize, I used the sliding window technique along with a hash set/map to track elements currently in the window.
Step 3: I expanded the window by moving the right pointer and added elements until a duplicate was found.
Step 4: When a duplicate appeared, I moved the left pointer forward and removed elements until the window again contained only distinct elements.
Step 5: Throughout the process, I kept updating the maximum window size, which represented the longest valid subarray.

Step 1: I used a two-pointer approach, starting one pointer from the beginning and the other from the end of the string.
Step 2: I compared characters at both pointers and moved inward as long as they matched.
Step 3: When a mismatch occurred, I checked two possibilities: skipping the left character or skipping the right character.
Step 4: I verified if either of the resulting substrings formed a palindrome.
Step 5: If at least one condition was true, the string could be converted into a palindrome by removing one character.

Step 1: I initially considered checking all possible subarrays using nested loops, which worked logically but had high time complexity.
Step 2: I then optimized the approach using a prefix sum technique with a hash set to store previously seen sums.
Step 3: While traversing the array, I checked if the current prefix sum minus K already existed in the set.
Step 4: If found, it confirmed the presence of a valid subarray; otherwise, I added the current prefix sum to the set.

Tip 1: Understand how queries are executed internally instead of memorizing syntax.
Tip 2: Focus on use cases and performance implications.
Tip 3: Practice explaining concepts using simple table-based examples.

Tip 1: Avoid assuming linear behavior when it is not stated.
Tip 2: Break the problem into smaller, logical steps.
Tip 3: Think creatively instead of applying formulas immediately.