Expedia Interview Question for Developer Program Engineers
- 0of 0 votes
.There is an infinite integer grid at which N people have their houses on. They decide to unite at- kumar.prince6 February 20, 2014 in United States
a common meeting place, which is someone's house.
From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
eg: (x,y) can be reached from (x-1,y+1) in a single unit of time.
Find a common meeting place which minimises the sum of the travel times of all the persons.
The following N lines will contain two integers saying the x & y coordinate of the i-th person.
M M = min sum of all travel times;
N <= 10^5
The absolute value of each co-ordinate in the input will be atmost 109
HINT: Please use long long 64-bit integers;
Explanation: Sums of travel times of the houses are 11, 13, 8 and 10. 8 is the minimum.
| Report Duplicate | Flag | PURGE
Expedia Developer Program Engineer Algorithm
Interview Type: Phone Interview
Open Chat in New Window