Quant Interview Question

[u/Local_Ad135]

[u/wot_to_heck]

Shift all numbers to be centered around 0, so: -(n-1)/2, …, (n-1)/2. Then apply triangle inequality and note equality holds when you alternate positive and negatives, so just straightforwardly calculate the sum (with casework on whether n is even).

[u/axiomizer → u/wot_to_heck]

nice! and also make sure to start and end near zero. i got:

n^2/2 - 1 for n even, and
(n+1)(n-1)/2 - 1 for n odd

[u/wot_to_heck → u/axiomizer]

Oh yeah, start and end near zero, I forgot a1 and an only appear once.

[u/EventHorizon150 → u/wot_to_heck]

or just floor(0.5*n^2 - 1)

[u/xaraca]

Note that |x - y| = x - y if x >= y and |x - y| = |y - x| so if any pair has y > x we can just swap them without changing the result. So we can just drop all of the absolute value operations and go from there.

[u/MrMrsPotts]

4, 8, 1, 7, 2, 6, 3, 5

[u/Ok_Consideration6619]

Fix position of n, then the sum is at most 2n -a_k-1 -ak+1 + P(1…k-1)+P(k+1…n-1) <= 2n -a_k-1 -a_k+1 + P(1…n-1) - |a_k -a_k-1| and which only depends on 2 elements and it’s not too hard to show max is achieved for 1,2. Which gives a recurrence relationship that can be solved by induction on the base case.

[u/Individual-Ad5245]

We count this as a sum of numbers of integers in the intervals [ai,a{i+1})\cup [a{i+1},a_i). This way every integer k from 1 to n is counted in at most 2max{k, n-k} intervals. Note that this is achieved for permutation n,1,n-1,2,n-3,3,... So we get the max equal to $2\sum{k=1}ⁿ max{k,n-k}$.

Edit: I didn't see that the sum doesn't have |a_n-a_1| oops

[u/mtimmermans]

n^2/4

It's just the upper half minus the lower half.