Top Software Engineer Interview Questions & Answers

A hash map (like Java's HashMap or Python's dict) stores key-value pairs using a hash function, providing O(1) average-case lookup, insertion, and deletion. A tree map (like Java's TreeMap) stores entries in a sorted red-black tree, giving O(log n) operations but maintaining key order. When to choose each: • Hash map — when you need fast lookups and don't care about ordering (the default choice for most problems) • Tree map — when you need sorted iteration, range queries, or finding the nearest key (e.g., a sorted leaderboard or interval-based cache) In practice, hash maps are the go-to; tree maps shine in problems requiring ordered traversal or nearest-key lookups.

Use Floyd's cycle-detection algorithm (tortoise and hare): 1. Maintain two pointers — a slow pointer (moves 1 node at a time) and a fast pointer (moves 2 nodes) 2. If there's a cycle, the fast pointer eventually meets the slow pointer 3. If the fast pointer reaches null, there's no cycle Complexity: O(n) time, O(1) space — which is optimal. To find the cycle's start: • Once the two pointers meet, move one pointer back to the head • Advance both pointers one step at a time • They'll meet at the cycle's entry point This is a classic interview question — know it cold.

In a balanced BST: • Search: O(log n) • Insert: O(log n) • Delete: O(log n) Degradation: if elements are inserted in sorted order, the tree degenerates into a linked list with O(n) operations for all three. Self-balancing variants that guarantee O(log n) worst-case: • AVL trees — stricter balancing, faster lookups • Red-black trees — less strict, faster insertions/deletions • B-trees — optimized for disk-based storage (databases) In interviews, always mention the degradation scenario and the existence of balanced variants — it shows depth.

Start by clarifying requirements: shortening URLs, redirecting, and analytics. Core components: • Key generation — Generate a unique 7-character base62 key (a-z, A-Z, 0-9) giving 3.5 trillion combinations. Use a pre-generation service to avoid collisions. • Storage — NoSQL database (DynamoDB) for fast reads. Schema: short_key → {original_url, created_at, user_id}. • Redirection — 301 (permanent) or 302 (temporary) redirect. Use 302 if you need per-click analytics. • Caching — Redis layer in front of the database for hot URLs (80/20 rule applies heavily). • Analytics — Async pipeline via Kafka → time-series database. Scaling: Shard the database by hash of the short URL. The read-to-write ratio is very high (~100:1), so optimize for reads.

Four main algorithms, each with tradeoffs: 1. Token Bucket — A bucket refills at a steady rate; each request consumes a token. Allows bursts up to bucket capacity. Best for most production systems. 2. Leaky Bucket — Requests enter a queue processed at a fixed rate. Smooths traffic but adds latency. 3. Fixed Window Counter — Count requests in fixed time windows. Simple but allows 2× the rate at window boundaries. 4. Sliding Window Log — Track timestamps of each request. Most accurate but memory-intensive. Recommendation: Token Bucket is preferred — handles bursts gracefully while maintaining average rate. Implementation: Redis with MULTI/EXEC for atomicity, storing token count and last-refill timestamp per client key.

Structure your answer using STAR: • Situation: A specific disagreement — e.g., the team chose a monolithic architecture when you believed microservices were better. • Task: What was at stake (performance, scalability, timeline). • Action: How you presented your case — ran benchmarks, proposed a proof of concept, organized a design review. • Result: Whether the team changed course or you learned why the original decision was valid. Key signals interviewers look for: • You backed your position with evidence, not opinions • You were respectful and collaborative throughout • You could commit to the final decision even if it wasn't yours • You learned something from the experience

Focus on demonstrating prioritization and communication: • Situation: A specific project with a hard deadline. • Action — what strong candidates show: - Identified the critical path early - Communicated explicitly what would and wouldn't ship - Negotiated scope with stakeholders - Delivered the most valuable subset on time • Example tradeoff: "We skipped integration tests for the admin panel but kept them for the payment flow because correctness there was non-negotiable." Avoid: Answers that imply you just worked 18-hour days — interviewers want strategic thinking, not brute force.