Skip to content

Instantly share code, notes, and snippets.

@jianminchen

jianminchen/mock interview - find a position

Created February 12, 2018 19:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/c5a3456e721a38cc453469ec27c5b51f to your computer and use it in GitHub Desktop.
Save jianminchen/c5a3456e721a38cc453469ec27c5b51f to your computer and use it in GitHub Desktop.
Download ZIP
Feb. 12, 2018 -
Raw
mock interview - find a position
[[1, 2,] [4, 3] [6, 3]]
find a point which minimizes the sum of the manhattan distance to each point
dist = abs(x1 - x2) + abs(y1 - y2)
xs = [1, 4, 6]
ys = [2, 3, 3]
quickselect
medianX 4, medianY 3
O(n)
Math.abs(x - x1)
(x1 + x2 +.. + xn)/ n -> median - 1, 2, 3, 2 , 1, 2, 3, 4 - 2 + 3/ 2
[4,2,3,1]
https://en.wikipedia.org/wiki/Quickselect
QuickSelect(xs, 1) // average case: O(n)
-----------------------------
(X:7) 4, 6, 8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment