Given an array of integers, sort it as a = b = d ...etc

Question

Given an array of integers, sort it as a >= b <= c >= d ...etc

Anonymous · Accepted Answer

Consider:

5000 >= 18 = 9 = 15 = 17

^^ split list into largest half and smallest half,
put larger half into all even indexes and 0 [0,2,4,6,...] and then put the smaller half into odd indexes [1,3,5,7,...]. This will always follow the above rules. We don't care about the actual sorting of the left or right half: so we just need to find the median value and everything smaller than that goes into an odd index and anything larger goes into an even index.

Correction, for some reason the signs aren't showing up, but you get it · Answer

Consider:

5000 > = 18  = 9  = 15  = 17

^^ split list into largest half and smallest half,
put larger half into all even indexes and 0 [0,2,4,6,...] and then put the smaller half into odd indexes [1,3,5,7,...]. This will always follow the above rules. We don't care about the actual sorting of the left or right half: so we just need to find the median value and everything smaller than that goes into an odd index and anything larger goes into an even index.

X

X Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches