Day 5 of the SDESheetChallenge by takeUforward completed! Smashed 3 core SDE sheet array/matrix problems today.
Solved Search a 2D Matrix (Medium) in O(log(MN)) time by treating the 2D grid as a virtual flat sorted array and mapping index mid to coordinates [mid / cols][mid % cols].
Implemented Pow(x, n) (Medium) using binary exponentiation (O(logN) time) and Majority Element (Easy) using the Boyer-Moore Voting Algorithm (O(N) time, O(1) auxiliary space).
Studied the system architecture of a URL shortener (Bit.ly):
Discussed 301 vs. 302 HTTP redirection, choosing 302 (Temporary Redirect) to ensure all clicks hit the server for metrics and analytics.
Explored unique short code generation, recommending a Base62 counter combined with bijective obfuscation (like Sqids) to guarantee unique, non-predictable IDs.
Designed scaling and latency optimizations including B-Tree primary key indexes on short_url, a Redis Cache-Aside layer (LRU eviction), and an AP-oriented eventual consistency database scaling model.
Next Day Goal
Continue SDE Sheet Arrays/Hashing section.
System Design: Study tinyurl/bit.ly replication and analytics logging.