Morgan Stanley

  www.morganstanley.com
  www.morganstanley.com

Interview Question

Credit Strats Interview New York, NY

A collection of 2D vectors of different direction and

  lengths. What is the fastest way to pick a subset of vectors in order to move from one point from a two dimensional plane to another.
Answer

Interview Answer

1 Answer

0

Can rephrase this: a set of vector {v_i} where v_i = (x_i, y_i). Choose binary weights b_i s.t. start_point + b1v1 + b2v2 +... + bnvn = end_point. Recognize this is a simple integer programming.

max anything
s.t. summation x_ib_i + x_of_start_pt = x_of_end_pt
summation y_ib_i + y_of_start_pt = y_of_end_pt
and set b_i binary for all i...

Anonymous on Jan 25, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.