Nishank Soni soninishank

System Design Cheatsheet

Picking the right architecture = Picking the right battles + Managing trade-offs

User cases (description of sequences of events that, taken together, lead to a system doing something useful)
- Who is going to use it?
- How are they going to use it?

Graham Scan algorithm for Convex Hull O(n * log(n))
Online construction of 3-D convex hull in O(n^2)
Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn)
- Suggested Reading - http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm
Rotating Calipers Technique
- Suggested Reading - http://cgm.cs.mcgill.ca/~orm/rotcal.html

Problems - Refer the article for a list of problems which can be solved using Rotating Calipers technique.

	Additional Questions from Career-cup
	Company selected Google,
	Sorted by most comments

	1.Partition integer array respect to zero, i.e. negative ... 0 ... positive, keep relative order
	E.g. -1 1 3 -2 2 => -1 -2 1 3 2.

	2. Search in 2D matrix,
	Given each row and column sorted, or given for each (i,j) A[i][j] < A[i][j+1] & A[i][j] < A[i+1][j]