💻Software Engineer

A stack is LIFO (last in, first out) with push and pop on one end, while a queue is FIFO (first in, first out) with enqueue at the rear and dequeue at the front. Use a stack for call stacks, undo history, expression evaluation and backtracking. Use a queue for task scheduling, BFS traversal, print jobs and message buffers. Both core operations are O(1).

Big-O describes how runtime or memory grows as input size grows, focusing on worst-case scaling rather than exact timing. O(n log n) grows almost linearly and is typical for efficient sorts like mergesort, while O(n squared) grows quadratically and becomes slow for large inputs as in naive nested loops. Use Big-O to compare approaches quickly and mention best, average and worst cases plus space complexity.

Quicksort: picks a pivot and partitions in place with average O(n log n) time and O(log n) stack space, but worst case O(n squared) without good pivots and it is usually unstable. Mergesort: divides the array and merges sorted halves with guaranteed O(n log n) time and stable ordering, but needs O(n) extra space. Choose quicksort for in-memory speed, mergesort when stability or guaranteed performance matters.

Binary search repeatedly halves a sorted range by comparing the middle element to the target, achieving O(log n) time and O(1) space iteratively. It requires random access and a sorted order, so it fails on unsorted data or linked structures without efficient indexing. Mention overflow-safe midpoint calculation and variants like lower bound and upper bound for duplicates.

BFS: explores level by level using a queue, finds shortest paths in unweighted graphs and uses O(V plus E) time with O(V) memory for the frontier. DFS: explores deep paths first using a stack or recursion, suits cycle detection, topological sort and backtracking, with O(V plus E) time and O(V) memory for the path. Choose BFS for shortest path, DFS for connectivity and exhaustive search.

Use Dijkstra with a priority queue for non-negative weights, giving O(E log V) time by finalizing the closest unsettled node each step. For graphs with negative edges but no negative cycles use Bellman-Ford, and for all-pairs use Floyd-Warshall on small dense graphs. Clarify assumptions first and explain how you would reconstruct the path with parent pointers.

Dynamic programming solves problems with overlapping subproblems and optimal substructure by storing subresults and reusing them. For Fibonacci, memoization or bottom-up tabulation drops naive exponential recursion to O(n) time. For 0-1 knapsack, build a table over items and capacity to decide take or skip, then trace back choices to reconstruct the solution.

Use two pointers when an array or linked list has order or structure you can exploit, such as sorted arrays, palindromes or fast and slow traversal. Classic wins include pair sum in sorted arrays, removing duplicates in place, and cycle detection with Floyd. It usually cuts O(n squared) brute force to O(n) time with O(1) extra space, so narrate the invariant each pointer maintains.

Sliding window maintains a window over an array or string and moves its edges to track a constraint like sum, distinct count or frequency map. Fixed windows slide by one for averages or max sums, while variable windows expand and shrink for longest or shortest subarray problems. It turns nested loops into O(n) single passes, so explain when to expand versus shrink with an example.

A hash table stores key-value pairs by hashing the key to a bucket index, giving average O(1) lookup, insert and delete. Collisions happen when two keys hash to the same bucket. Common resolution strategies are chaining with a linked list per bucket, open addressing with linear or quadratic probing, and double hashing. A good hash function plus resizing at a load-factor threshold keeps performance stable.

Arrays: contiguous memory with O(1) indexed access but O(n) inserts and deletes in the middle plus fixed or amortized resizing cost. Linked lists: node-based with O(1) insert and delete given the node pointer but O(n) indexed access and extra pointer overhead. Choose arrays for cache locality and random access, linked lists for frequent splits, merges and constant-time edits at known positions.

Inorder visits left, node then right and yields sorted order for binary search trees, while preorder visits node first for copying or serializing structure. Postorder visits children first for safe deletion or bottom-up aggregation, and level order uses a queue for breadth-first processing. All depth-first traversals are O(n) time, so pick based on whether parents must precede, follow or interleave children.

A heap is a complete binary tree where each parent satisfies heap order, giving O(1) peek and O(log n) insert and extract for min or max. It is commonly built in O(n) with heapify and implemented in an array with index arithmetic for parents and children. Use it for priority queues, top K problems, task scheduling and merging sorted streams.

Adjacency lists: store neighbors per node with O(V plus E) space, iterate neighbors efficiently and suit sparse graphs. Adjacency matrices: store a V by V table with O(V squared) space and O(1) edge lookup, suiting dense graphs and fast connectivity checks. Choose lists for scalable traversals, matrices for dense graphs or frequent edge-existence queries.

A trie stores strings as a prefix tree where each edge is a character and nodes mark word endings, enabling O(L) insert and search for length L. It excels at autocomplete, spell checking, prefix counting and IP routing with predictable lookup independent of dictionary size. Trade memory from shared prefixes against hash-map simplicity, and mention compression into radix trees for large alphabets.

A Bloom filter is a space-efficient probabilistic set using a bit array and multiple hash functions to test membership with possible false positives but no false negatives. It offers constant-time adds and checks in tiny memory, ideal for cache pre-checks, crawlers and database guards. Tune size and hash count for a target false-positive rate and note that deletion needs a counting variant.

Combine a hash map for O(1) key lookup with a doubly linked list that keeps most-recently used nodes at the front. On access, move the node to the front, and on insert beyond capacity evict from the tail, giving O(1) get and put. Discuss thread safety, TTL extensions and where the cache sits relative to the database.

Clarify requirements first: read versus write volume, URL length, expiry, custom aliases and analytics. A common design hashes or base62-encodes an auto-increment ID into a short code, stores the mapping in a relational or NoSQL store with Redis caching for hot URLs, and redirects via 302. Add rate limiting, abuse detection, sharding by hash and read replicas. Discuss collision handling, consistency and cache invalidation trade-offs.

The CAP theorem states a distributed data store can guarantee only two of consistency, availability and partition tolerance during a network partition. Since partitions are unavoidable, the real choice is CP (consistent but may reject writes, e.g. etcd or HBase) versus AP (available but eventually consistent, e.g. Cassandra or Dynamo-style). Give examples of each and choose based on whether stale reads or failed writes hurt the product more.

Load balancers spread client traffic across healthy backends using strategies like round robin, least connections, consistent hashing or latency-aware routing. Layer 4 routes on connection info with low overhead, while Layer 7 routes on URL, headers or cookies for smarter affinity and canary rules. Pair them with health checks, autoscaling and sticky-session trade-offs, and remove single points of failure with redundant tiers.

Cache-aside: the application checks the cache first and loads from the database on a miss, giving control and only caching what is read but risking stale data until TTL or invalidation. Write-through: writes go to cache and database together, keeping them consistent with slower writes and a warmer cache. Choose cache-aside for read-heavy flexible workloads, write-through when readers must see fresh writes.

Kafka: a distributed commit log with partitioned topics, replayable retention and high-throughput event streaming for analytics and sourcing. RabbitMQ: a traditional message broker with queues, exchanges and per-message acknowledgments suited to task distribution and complex routing. Choose Kafka for durable streams at scale, RabbitMQ for flexible routing and lower-latency work queues.

Monoliths: a single deployable unit with simple calls, transactions and debugging, but scaling and team ownership get harder as the codebase grows. Microservices: independently deployable services with clear boundaries that scale and evolve separately, but add network latency, distributed transactions and operational overhead. Choose based on team size, scaling needs and appetite for platform investment like service discovery and tracing.

Pick an algorithm such as token bucket or leaky bucket for smooth bursts, fixed or sliding window counters for simplicity, and store counters in Redis for distributed enforcement. Return standard headers with limits and reset times plus 429 responses with retry guidance. Discuss per-user versus per-IP keys, gateway versus service-level enforcement and how to handle bursts for premium tiers.

Raft elects a leader through randomized election timeouts, then replicates a log of commands from the leader to followers with majority acknowledgment. Safety comes from voting rules that ensure only one leader per term and that committed entries survive elections. Explain leader election, log replication and commitment, then note trade-offs versus Paxos simplicity and performance under partitions.

Sharding: splits data by key across nodes to scale writes and storage, but adds cross-shard queries and rebalancing complexity. Replication: copies the same data to multiple nodes for availability and read scaling, but adds lag and conflict handling. Most large systems combine both, so explain how you would pick a shard key and choose synchronous versus asynchronous replicas.

Emit structured logs with request IDs, expose RED or USE metrics for latency, errors and saturation, and propagate traces across services for end-to-end views. Add health endpoints, SLO-based alerts that fire on user impact, and dashboards grouped by service and endpoint. Show how you would debug a latency spike by correlating a trace, a metric and a log sample.

A CDN caches static and cacheable content at edge points of presence near users, cutting latency and origin load through geographic proximity. It handles TLS termination, compression, cache hierarchies and invalidation or versioned URLs for freshness. Discuss cache-hit ratios, dynamic acceleration limits and how you would measure improvement with real user timing.

Clarify fan-out, freshness and ranking needs, then choose push for active users with pull fallback for celebrities to bound write amplification. Store posts and precomputed timelines in NoSQL with caching, rank with a service, and paginate with cursors. Address hot keys, backfill, consistency of deletes and metrics like p99 load time.

SQL databases are relational with fixed schemas, ACID transactions and JOINs, ideal for structured data needing consistency such as payments or inventory. NoSQL covers document, key-value, wide-column and graph stores with flexible schemas and horizontal scaling, ideal for high-write or semi-structured workloads like feeds or catalogs. Mention the CAP theorem and choose based on query patterns and scale needs.

Start by running EXPLAIN ANALYZE to spot sequential scans, missing indexes or bad join order. Add indexes on filter and join columns, select only needed columns, paginate large results, and denormalize hot paths or add caching where reads dominate. Check for N+1 queries, lock contention and stale statistics with ANALYZE and VACUUM. Walk through a real example showing before and after plans with measured latency improvement.

Indexes provide ordered structures, usually B-trees, that locate rows without full scans and accelerate filters, joins and sorting. They speed reads but slow writes and consume space, so index selective columns used in WHERE, JOIN and ORDER BY. Mention composite column order, covering indexes, and how EXPLAIN shows index versus sequential scans.

ACID: atomicity, consistency, isolation and durability for strict correctness in relational systems handling money or inventory. BASE: basically available, soft state and eventually consistent for highly available systems that tolerate temporary divergence like feeds or carts. Choose ACID when correctness dominates, BASE when scale and availability dominate, and explain the resulting application complexity.

Normalization: organizes tables to reduce duplication with normal forms, improving write integrity but requiring more joins. Denormalization: duplicates or pre-joins data to speed reads at the cost of larger storage and trickier updates. Normalize for transactional correctness first, then denormalize hot read paths with clear invalidation or backfill jobs.

Isolation levels trade correctness for concurrency from read uncommitted up through read committed, repeatable read and serializable. Weak levels allow dirty reads, non-repeatable reads or phantoms, while serializable prevents anomalies at higher locking or retry cost. Pick defaults like read committed plus optimistic locking for most apps, and reserve serializable for ledger-style writes.

Pick a high-cardinality key aligned with common queries, such as user ID for user-scoped access, to spread load evenly and keep most queries single-shard. Avoid hot keys like a global tenant or timestamp prefix that funnel writes to one shard. Plan for growth with consistent hashing, shard splits and a lookup service, and explain how scatter-gather queries would still work.

Use Redis for low-latency caching, session storage, leaderboards with sorted sets, rate counters, pub-sub messaging and distributed locks. Its in-memory speed plus rich data structures beat round trips to disk-backed stores for hot paths. Mention persistence options, eviction policies and clustering limits so the choice reflects durability needs.

Design resource-oriented URLs with nouns such as GET /users/123, use HTTP verbs correctly, return proper status codes (200, 201, 204, 400, 401, 404, 429, 500), and version via /v1. Keep responses consistent with pagination, filtering and sorting, support idempotency for unsafe retries, and document with OpenAPI. Secure with auth, rate limiting and validation, and never expose internal errors to clients.

REST: resource URLs with fixed shapes, HTTP caching and simple tooling, but clients may over-fetch or need many round trips. GraphQL: a typed schema where clients request exactly the fields they need in one round trip, but caching, complexity limits and server cost need care. Choose REST for stable CRUD and cacheable resources, GraphQL for flexible clients and aggregated views.

Version explicitly with URL paths like v1 or headers, keep changes backward compatible by only adding optional fields, and never repurpose existing semantics. Deprecate with sunset headers, changelogs and dual-run periods while tracking adoption per version. Gate breaking changes behind new versions and contract tests so old clients keep working.

Offset pagination: skips N rows with LIMIT and OFFSET, simple for static lists but slow on deep pages and unstable when rows shift. Cursor pagination: pages by an opaque stable key like timestamp plus ID, staying fast and consistent for live feeds. Use offset for small admin tables, cursors for large or frequently updated collections with clear next-page tokens.

Design retries to have the same effect as one call by using idempotency keys, natural keys or safe PUT semantics instead of repeated POST creates. Store the key with request hash and response, return the original result on replays, and expire keys sensibly. Mention exactly-once limits in distributed systems and how clients should generate unique keys per intent.

Polling: the client repeatedly requests updates on an interval, simple and firewall friendly but wasteful and delayed. Webhooks: the server pushes events to a client URL in near real time, efficient for sparse events but requiring public endpoints, signatures and retries. Choose webhooks for timely notifications, polling for simple pulls or when inbound connections are blocked.

Session auth: the server stores session state and issues a cookie reference, enabling instant revocation with a lookup cost and sticky or shared storage needs. JWT auth: the server issues a signed token carrying claims that services verify statelessly, scaling well but needing short expiry plus refresh and revocation lists. Choose sessions for simple apps needing instant logout, JWTs for distributed services.

Garbage collection automatically reclaims memory unreachable from roots like the stack and globals. Java uses generational collectors (serial, parallel, G1, ZGC) with mark-and-sweep or compact phases. CPython primarily uses reference counting with immediate cleanup, plus a generational cyclic collector for reference cycles. Mention tuning flags, pause-time versus throughput trade-offs, and debugging with heap dumps or gc module stats.

A closure is a function bundled with its lexical environment, so it remembers outer variables after the outer call returns. This enables private state, function factories, callbacks and memoization without globals. Warn about loop-variable capture and retained memory, and show a small counter or debounced handler example.

JavaScript runs on a single thread where the call stack executes tasks, Web APIs handle timers and I/O, and the event loop moves completed callbacks through microtask and macrotask queues. Promises and async await use microtasks that drain before rendering or timers, which explains starvation risks. Illustrate with a fetch plus timer ordering example and note how workers offload CPU work.

Callbacks: functions passed for later invocation, simple but prone to nesting, duplicated error handling and inversion of control. Promises: objects representing future values with chained then and catch plus async await syntax, centralizing errors and sequencing. Prefer promises or async await for readable flows, and mention conversion with promisify plus unhandled-rejection hygiene.

Static typing: types are checked at compile time, catching errors early and aiding refactoring and performance with added verbosity. Dynamic typing: types resolve at runtime, enabling fast prototyping and flexible code with later failures and heavier testing needs. Mention gradual typing options like TypeScript or Python type hints that blend both strengths.

Inheritance: a child reuses a parent interface through is-a extension, quick to write but brittle when hierarchies change. Composition: an object holds collaborators through has-a delegation, more flexible and testable through injected behavior. Prefer composition with small interfaces, reserving inheritance for true substitutable hierarchies that honor Liskov principles.

Stack memory: stores call frames and locals with fast LIFO allocation and automatic cleanup, but limited size and short lifetimes. Heap memory: stores dynamic objects with flexible lifetimes and sharing, but slower allocation plus garbage-collection or manual-free costs. Explain overflow versus leak symptoms and why large or shared data belongs on the heap.

Interfaces: define pure contracts without state, allowing multiple conformance and clean mocks across languages. Abstract classes: provide shared state plus partial implementation for a family of subclasses, but single-inheritance limits apply in many languages. Use interfaces for capability polymorphism, abstract classes for Template Method reuse within one hierarchy.

Concurrency means multiple tasks make progress by interleaving on shared resources such as threads or async I/O, while parallelism means tasks literally execute simultaneously on multiple cores. Concurrency suits I/O-bound work and responsiveness; parallelism speeds CPU-bound work. Use the barista analogy: one barista juggling orders is concurrency, multiple baristas are parallelism. Mention GIL limits in CPython and how multiprocessing helps.

Processes: isolated address spaces with separate memory and file descriptors, safer but heavier to start with costlier IPC. Threads: lighter units sharing memory within a process, faster to switch and communicate but prone to races needing synchronization. Choose processes for isolation and CPU parallelism under the GIL, threads or async for shared-memory I/O concurrency.

Deadlocks need mutual exclusion, hold and wait, no preemption and circular wait, often from locks acquired in inconsistent order. Prevent with lock ordering, timeouts and try-lock, coarse scoping, or lock-free designs, plus detection via wait-for graphs in databases. Describe a two-lock ordering fix and how you would reproduce the issue in a test.

Reproduce with stress tests and deterministic scheduling, then capture interleavings with logs, thread sanitizers and consistent repro scripts. Fix by narrowing shared state, using locks or atomics correctly, or shifting to message passing and immutable data. Verify with repeat runs under sanitizers and add a regression test that fails on the old ordering.

SOLID pushes single responsibility, open-closed extension, Liskov substitutability, interface segregation and dependency inversion for maintainable OOP. A classic example splits a bloated order class into pricing, storage and notification collaborators behind narrow interfaces. Mention one smell each principle prevents, such as shotgun edits or fragile subclasses.

Unit tests: isolate a single function or class with mocks, running fast to pinpoint logic errors and guard refactors. Integration tests: exercise real collaborators like databases or services to catch contract and wiring issues, running slower and flakier. Keep a pyramid with many unit tests, fewer integration tests and very few end-to-end flows tied to user journeys.

Write a failing test for one small behavior, implement the minimal code to pass, then refactor with tests green in short red-green-refactor loops. Keep tests fast, deterministic and expressive so they document intent and catch regressions. Note when to relax strict TDD, such as spikes or UI exploration, while keeping coverage on critical paths.

Git merge: preserves branch topology with a merge commit, safe for shared branches and honest history at the cost of clutter. Git rebase: replays commits onto a new base for linear history, cleaner for private branches but rewrites SHAs and risks confusion if pushed shared. Use merge for team branches, rebase locally before review, and never rebase published history.

A strong pipeline builds once, runs fast parallel tests with caching, scans for security and style, and promotes immutable artifacts through staging to production. It gates on quality checks, supports rollbacks and feature flags, and gives quick feedback with clear logs. Measure lead time and failure recovery, and keep main always releasable.

Virtual machines: virtualize hardware with guest operating systems on a hypervisor, giving strong isolation with heavier memory and boot costs. Containers: share the host kernel with isolated namespaces and cgroups, starting fast with less overhead but weaker isolation. Use containers for dense microservices, VMs or lightweight VMs for untrusted or kernel-sensitive workloads.

Scope the blast radius with metrics and traces to see if latency is global or tied to one route, deploy or dependency. Check recent deploys, saturation signals, slow query logs and downstream timeouts, then reproduce in staging with sampled traffic. Fix with indexing, caching, timeouts or rollback, and add an SLO alert plus a regression test.

Check correctness against requirements, edge cases, error handling and concurrency risks before style nits. Then assess readability, naming, testing, security issues like injection, and performance pitfalls such as N plus 1 queries. Give actionable kind feedback with suggestions and praise good patterns, keeping reviews small and timely.

Dependency injection passes a component's dependencies in from the outside through the constructor, a setter or a framework container, instead of letting it construct them. This decouples modules, makes behavior swappable between real and mock implementations, and greatly improves testability. Give an example such as injecting a database client into a service class so tests can substitute an in-memory fake without changing business logic.

Use a singleton sparingly for truly global coordination like configuration, connection pools or logging where one instance simplifies access. Risks include hidden coupling, painful testing and thread-safety bugs from lazy initialization. Prefer dependency injection with a single shared instance, and implement double-checked locking or module-level initialization if you must.

Factory: centralizes creation behind a method that picks subclasses, simplifying client code when the exact type varies. Builder: assembles complex objects step by step with a fluent interface, handling many optional fields without telescoping constructors. Use factories for polymorphic choice, builders for readable construction of configurable objects.

Observers subscribe to a subject and receive updates through a common interface when state changes, decoupling publishers from subscribers. Classic uses include UI bindings, event buses and pub-sub feeds with careful unsubscribe handling. Warn about notification storms and ordering guarantees, and contrast push versus pull update styles.

Encapsulate each algorithm or rule behind a shared interface, then inject the chosen strategy instead of branching on type codes. For example, separate pricing, shipping or validation strategies selected by configuration or request type. This keeps open-closed extension easy and makes each path independently testable.

Adapter: converts one existing interface into what a client expects, letting incompatible classes work together with minimal changes. Facade: provides a simplified front for a complex subsystem, hiding orchestration behind one clean call. Use adapters for integration mismatches, facades to reduce coupling to sprawling APIs.

A repository exposes collection-like methods for domain objects while hiding query, mapping and transaction details behind an interface. This centralizes queries, enables in-memory fakes for tests and eases swapping stores. Keep business logic out of the repository and return domain types rather than leaking cursors or ORM internals.

Publishers emit events to topics without knowing subscribers, and brokers fan out to queues or push endpoints with filtering and retries. This enables independent scaling, replay and new consumers without publisher changes. Address schema evolution, ordering, duplicate delivery and dead-letter handling in your design.

A circuit breaker wraps remote calls and trips open after threshold failures, failing fast instead of piling up threads on a sick dependency. Half-open probes test recovery before resuming full traffic, usually paired with timeouts, bulkheads and fallbacks. Explain tuning of thresholds and how dashboards show state transitions.

Wrap an object with decorators that share its interface to add behavior like caching, logging or validation without subclass explosion. Composition keeps combinations flexible at runtime and honors single responsibility per wrapper. Show a concrete chain such as authenticated plus cached data access and note ordering effects.

Encapsulate each request as an object with execute and undo methods plus parameters, letting invokers queue, log or retry operations uniformly. Undo stacks, transactional macros and job queues all build on this uniform interface. Mention receiver decoupling and how serialized commands support audit and replay.