Amazon Interview Question
Country: United States
Interview Type: Phone Interview
static int sumOfOccupiedToilets(int toilets, int people) {
if (people >= toilets) {
return (toilets * (1 + toilets)) / 2;
}
int[] currentDistances = new int[toilets];
Arrays.fill(currentDistances, Integer.MAX_VALUE);
int sum = 0;
int maxDistIndex = 0;
for (int i = 0; i < people; i++) {
int pos = maxDistIndex;
currentDistances[pos] = 0;
sum += pos + 1;
maxDistIndex = 0;
for (int j = 0; j < currentDistances.length; j++) {
currentDistances[j] = Math.min(Math.abs(pos - j), currentDistances[j]);
if (maxDistIndex < currentDistances[j]) {
maxDistIndex = currentDistances[j];
}
}
}
return sum;
}
import sys
def getToiletSum(t, p):
if p >= t:
return (t * (t + 1)) / 2
row = [sys.maxsize] * t
result = 0
currIndex = 0
for _ in range(p):
result += (currIndex + 1)
row[currIndex] = 0
maxDistIndex = 0
maxDist = 0
for i in range(len(row)):
row[i] = min(abs(i - currIndex), row[i])
if maxDist < row[i]:
maxDist = row[i]
maxDistIndex = i
currIndex = maxDistIndex
return result
def main():
toilets = 5
ppl = 5
print "Running for t# " + str(toilets) + ", ppl# " + str(ppl)
s = getToiletSum(toilets, ppl)
print "sum: " + str(s)
if __name__ == '__main__':
sys.exit(main())
What is the question?
- onsite December 22, 2017