chillua98's blog

A question I came across in an Interview
By chillua98, history, 10 days ago, In English

There was a question I came across in an Online Assessment recently and I was not able to solve it. It goes as follows:-

There are n children in a classroom and the teacher wants to arrange them in a circle, such that the max height between any 2 students is MINIMIZED.

For example:-

N=7 Students: 4 1 3 2 1 2 3

The minimum value of max height diff is 1, if we arrange it as follows:

2 3 4 3 2 1 1

(Just a reminder that the height difference between the first student and the last student is also considered as they are in a circle)

I thought it was involving Binary Search but couldn't come up with a helper function. Could someone please help me out?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think greedy approach will work you can sort the given array then pick the maximum element i.e. last element from array, place it at middle position (mid) in answer array then pick second last element at put it at (mid-1) position then third last element and put it at (mid+1) position and so on. like (mid-2), (mid+2)...

for given test case after sorting, array will be : 1 1 2 2 3 3 4 then answer array will look like : 1 2 3 4 3 2 1

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yea this seems like a much better approach. Cannot really try it ,but makes sense to me.

    → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

for example consider this array [1, 2, 3, ..., n ], notice that when arrange in sorted order there difference btw element is minimum while first and last is (n-1), also notice that if you pick any element (let named it x) inside the array and append it to the front or back the difference btw first and last element change but the net total difference is still the same, e.g. [3 2 1 4 7 6 5] gives the same value as [1 2 3 4 5 6 7]

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

just sort the array and rotate the second half of the array will work here I guess

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No that won't work I have alrdy tried that. I think the first comment is the right approach , seems like the right answer

    → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the interviewer stole the problem from this 1131C - Birthday

its greedy : sort the array then print the elements with even position and then print the elements with odd positions

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When I first read the question and looking at the part of the question which states minimizing the maximum difference Binary search comes to mind and the answer space would be 1(lowest value) and max height-min height (the maximum value) and then using a predicate function to check on a possible mid value while storing it in the result if feasible.

bool f(vector& heights, int n, int max_diff) { int start = heights[0]; int count = 1;

for (int i = 1; i < n; ++i) {
    if (heights[i] - start > max_diff) {
        start = heights[i];
        count++;
        if (count == n) {
            return false;
        }
    }
}

return true;

}

int minMaxHeightDiff(vector& heights, int n) { sort(heights.begin(), heights.end());

int low = 1;
int high = heights[n-1] - heights[0];
int result = high;

while (low <= high) {
    int mid = low + (high - low) / 2;

    if (f(heights, n, mid)) {
        result = mid;
        high = mid - 1;
    } else {
        low = mid + 1;
    }
}

return result;

} Not sure if this gives an AC but yes this can be an approach in my opinion correct me if I am doing something wrong.

→ Reply