Data Structures - lesson 7 | HackIndia Skills

Data Structures - lesson 7 | HackIndia Skills | HackIndia

Example

Repo note example

Add notes like this beside your solution files. Keep them short enough that someone can read them before opening the code.

Problem: First non-repeating character in a string

Choice:
Use a hash map to count characters, then scan the string again.

Why:
We need fast frequency lookup for each character.
A hash map gives average O(1) update and lookup.

Cost:
Time: O(n), because we scan the string twice.
Space: O(k), where k is the number of distinct characters.

Trade-off:
An array of size 26 works for lowercase English letters.
A hash map is safer if input can include uppercase, digits, or symbols.

Edge case:
If no non-repeating character exists, return -1.

Example

Spoken answer template

Practise saying this in 30 to 45 seconds. It works for most college internship interviews.

I need to find pairs that sum to target.
The repeated operation is checking whether target - current exists.
I will use a hash set because lookup is average O(1).
I scan the array once, check the complement, then add the current number.
Time is O(n). Space is O(n) in the worst case.
I am not using two pointers because the array is not sorted.
If sorting were allowed, two pointers would use less extra space but change the cost to O(n log n).

Explain choices like interviews

Say why, not just what

What interviewers listen for

Use a simple script

Repo note example

Compare one rejected choice

Do not overclaim

Spoken answer template

Do this now

Quick check