CareerCup

What is the question?

We can store in a boolean array, the staus (occupied / free) of every toilet. Find the distance between every pair of consecutive occupied toilets & report the mean of the indices of the pair with the maximum distance.

What is the problem statement?

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;
  }

This question can be solved using a Priority queue.

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())