Technical Interviews

From David's Wiki
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
\( \newcommand{\P}[]{\unicode{xB6}} \newcommand{\AA}[]{\unicode{x212B}} \newcommand{\empty}[]{\emptyset} \newcommand{\O}[]{\emptyset} \newcommand{\Alpha}[]{Α} \newcommand{\Beta}[]{Β} \newcommand{\Epsilon}[]{Ε} \newcommand{\Iota}[]{Ι} \newcommand{\Kappa}[]{Κ} \newcommand{\Rho}[]{Ρ} \newcommand{\Tau}[]{Τ} \newcommand{\Zeta}[]{Ζ} \newcommand{\Mu}[]{\unicode{x039C}} \newcommand{\Chi}[]{Χ} \newcommand{\Eta}[]{\unicode{x0397}} \newcommand{\Nu}[]{\unicode{x039D}} \newcommand{\Omicron}[]{\unicode{x039F}} \DeclareMathOperator{\sgn}{sgn} \def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits} \def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits} \)

Resources for Technical Interviews


Algorithms

In general, consider the following approaches

  • Brute-force and searching
  • Dynamic Programming
  • Greedy (sorting + take the best at each step)
  • Linear searching (with 2 pointers)
    • Usually the answer if you're searching for a connected segment along an array
    • E.g. max contiguous subarray

Computer Systems

Web Architecture

Four Key Principles

  • Availability
  • Performance
  • Reliability
  • Scalability
  • Manageability
  • Cost

Services

  • Separate each functionality into its own service so each can be scaled separately
(e.g. Reading and Writing can be two services which access the same file store)
  • Each service can then be managed separately.

Redundency

  • Replicate nodes for each service using a "shared-nothing architecture."
  • Each node should be able to operate independently.

Partitions

  • Also known as shards
  • Scaling vertically: Add more hard drives, memory
  • Scaling Horizontally: Add more nodes
  • Distribute data somehow: geographically, by type of user,...
  • Make sure you can identify server from id of data (e.g. adding it to hashing or maintaining an index)

Caches

  • Place a cache on the request layer.
  • Cache in memory, not disk (e.g. memcached, redis)
Global Caches
  • If you have several request nodes, you can put a global cache between the request node and the database
Distributed Cache
  • Each request node holds a cache for a specific type of data
  • A request node may forward requests to other request nodes which have the corresponding cache
  • Cons: May be hard to remedy if a node goes down

Proxies

  • Used to filter, log, and modify requests
  • Collapsed Forwarding: collapse the same or similar requests and return the same result to clients
  • You can also collapse requests that are spatially close together on the database

Indexes

  • Indexes are used to quickly find small data in large datasets
  • Indexes are stored in memory, data separated across several servers
  • Possibly many layers of indexes

Load Balancers

  • Purpose: Handle many connections and route them to request nodes
  • Algorithms: Random, round robin, custom criteria
  • Software: HAProxy
  • Usually placed at the front of a distributed system
    • Load balancers can send requests to other load balancers
  • Challenges: Managing user session data
    • Solutions: Caches, cookies, user data, URL rewriting
  • Cons: Makes problem diagnosis difficult

Queues

  • Schedule client tasks in a queue, acknowledge task received immediately
  • Queues protect from service outages and failures
  • Software: RabbitMQ, ActiveMQ

System Design

Misc