SDE - Intern

Understand Problem
* Find minimum coins to make given amount
* Each coin can be used unlimited times


* 2. Define DP State
* dp[i] = minimum coins needed to make amount i


* 3. Initialize
* Create array dp[amount + 1]
* Set:
* dp[0] = 0
* Rest → large value (amount + 1)


* 4. Apply Transition
* For every i from 1 → amount
* For each coin:
* If coin <= i
* Update:
Build Solution
* Fill dp array from smaller values → larger values



* 6. Final Answer
* If dp[amount] > amount → return -1
* Else → return dp[amount]



* 7. Time & Space Complexity
* Time: O(n × amount)
* Space: O(amount)

Tip 1: Be strong with your SQL basics. 
Tip 2: Practice daily basics in Java.

Tip 1: Be strong in your projects.
Tip 2: Always highlight the value of your projects.

Step 1: I first understood the problem and started with a basic class design for a bank account with simple deposit and withdraw functions.

Step 2: I implemented the deposit logic easily, but in the withdrawal function, I initially forgot to handle insufficient balance properly.

Step 3: The interviewer pointed this out and asked me to handle edge cases like invalid input and negative values.

Step 4: I updated the logic by adding proper condition checks and ensured that the balance never goes negative.

Step 5: Finally, I added a balance check function and explained the complete flow clearly. The interviewer was satisfied with the clean and structured approach.

Step 1: I first understood the requirement—to convert a string like “aabbbcc” into a compressed form like “2a3b2c”.

Step 2: I initially thought of checking each character one by one and counting occurrences, but that would be inefficient for larger strings.

Step 3: Then I optimized the approach using a hash array (frequency array) to store counts of each character.

Step 4: I traversed the string once and updated the frequency for each character.

Step 5: After that, I iterated over the hash array and constructed the result by appending count + character for all non-zero frequencies.

Step 6: Finally, I ensured the solution handles edge cases like empty strings and single-character inputs.