General discussion thread for the week 1, part 1 of the crash course.
If Week 1 / Part 1 is Big-O + arrays/strings, here’s a simple plan to get the most out of it:
- Always write a brute-force first, then annotate time/space. Then optimize.
- Know your language’s common op costs: dict/set avg O(1); list insert/delete middle O(n); slicing often O(k).
- Pattern focus: two pointers, sliding window, and hash maps (frequency, index lookup).
- Derive target complexity from constraints before coding (n up to 1e5 → avoid O(n2)).
- Test edges: empty, single item, duplicates, negatives, unicode/whitespace, very large inputs.
- Daily reps: 30–45 min. Suggested set: Two Sum, Valid Anagram, Move Zeroes, Max Subarray (Kadane), Longest Substring Without Repeating Characters.
- Mini-challenge: implement Two Sum 1) brute-force, 2) sort + two pointers, 3) hash map; write Big-O for each.
If anything in the intro (esp. asymptotic analysis or sliding window) is fuzzy, drop your code or reasoning and I’ll point out where the complexity or logic goes off.
Jun’s plan is spot on. A few practical notes that help in interviews and on real projects:
- Derive target complexity upfront: if n ≈ 1e5, aim O(n) or O(n log n). If you can’t hit it, explain tradeoffs.
- Two Sum:
- Brute: O(n2), no extra space.
- Sort + two pointers: O(n log n). Remember sorting loses original indices—sort (value, index) pairs.
- Hash map: O(n) time, O(n) space. Easiest to pass.
- Sliding window (Longest Substring…): keep lastseen[char] = index, and move left = max(left, lastseen[c]+1). Each pointer moves ≤ n times → O(n).
- Arrays/strings pitfalls:
- Don’t slice in inner loops; s[i:j] copies → hidden O(k).
- String concat in loops is O(n2); use list join or StringBuilder.
- Unicode: length is code points, not bytes. Test with emojis/accents if relevant.
- Move Zeroes: write pointer swaps nonzeros forward → O(n), in-place, stable.
- Kadane: running best = max(num, best+num); track global max.
Great string drill: Valid Numeric String.
- Handle trims, optional sign, digits, optional decimal, optional exponent (e/E with signed integer).
- Edge tests: "0", " -3.5e+8 ", ".", ".1", "1.", "1e", "e9", "+.8", " ", "1e-2", "1e+02".
- Linear scan with a small state machine → O(n), O(1) space.
If anyone’s sliding window feels “O(n2)”, you’re likely shrinking the window one-by-one too often or rebuilding substrings—share the snippet and we can pinpoint it.
Jun/Pat’s notes are super helpful. Trying to internalize the sliding window rule. This is my Python for Longest Substring Without Repeating Characters:
python
def lengthOfLongestSubstring(s: str) -> int:
last = {}
left = 0
best = 0
for right, c in enumerate(s):
if c in last and last[c] >= left:
left = last[c] + 1
last[c] = right
best = max(best, right - left + 1)
return best
- Is this truly O(n) in Python? I’m avoiding slicing and concat, but does iterating Unicode (emojis) change anything complexity-wise?
- Pat mentioned using max(left, last[c]+1). My conditional seems equivalent—are there edge cases where the max form is safer? I tested "abba" and it works, but curious if I’m missing something.
Also on Two Sum (sort + two pointers): if I sort (value, index) pairs to recover indices, does that count as O(n) extra space in interviews? Is there any way to do sort+two pointers and still claim O(1) extra without losing original indices?