Water Droplet Mixing
Consider a pipe of length L. The pipe has N water droplets at N different positions within it. Each water droplet is moving towards the end of the pipe(x=L) at different rates.
When a water droplet mixes with another water droplet, it assumes the speed of the water droplet it is mixing with. Determine the no of droplets that come out of the end of the pipe.

Question

Water Droplet Mixing

Consider a pipe of length L. The pipe has N water droplets at N different positions within it. Each water droplet is moving towards the end of the pipe(x=L) at different rates.

When a water droplet mixes with another water droplet, it assumes the speed of the water droplet it is mixing with. Determine the no of droplets that come out of the end of the pipe.

Accepted Answer

I gave him a brute force type approach by starting from the second drop and comparing it with the previous one and after checking the condition of speed and time if they can mix or not. Similarly, this was done for each drop. But I can’t come up with an optimal solution which the interviewer wanted. The interviewer wanted a greedy approach by me.

Accepted Answer

CN hint:

A drop will mix with another drop if two conditions are met:

- If the drop is faster than the drop it is mixing with

- If the position of the faster drop is behind the slower drop. Also more time means less speed and less time means more speed.

CN approach: Sort the array according to the position of the drops. Now we got to know which drops lie behind which drops and their respective time taken to reach the end.All the drops before a slower drop will mix with it. And all the drops after the slower drop with mix with the next slower drop and so on.So we will use stack to maintain local maxima of times.So total number of drops will be no of local maxima for time +no of remaining drops after last local maxima

Here is pseudo code:

We will get input in form of array of pairs where first element represents .

Int fun(int arr[],int n)

{

//sort the array according to positions

int k = 0; // counter for no of final drops

// stack to maintain the next slower drop

// which might coalesce with the current drop

stack s;

// we traverse the array from right to left

// to determine the slower drop

for (i = n - 1; i >= 0; i--)

{

if (s.empty()) {

s.push(m[i].second);

}

// checks for next slower drop

if (m[i].second > s.top())

{

s.pop();

k++;

s.push(m[i].second);

}

// calculating residual drops in the pipe

if (!s.empty())

{

s.pop();

k++;

}

return k;

}

Accepted Answer

Minimum Position Approach

We can solve this problem by calculating the time required by each drop to reach the end of the pipe and comparing them based on their position in the pipe and the time required to reach the end.

Calculate the time required by each drop to reach the end of the pipe in fraction format (storing a pair of numerator and denominator) to eliminate the risk of the precision issue in different programming languages.
Now make a pair of positions and times and sort them according to the position.
Now say there are two drops i and j such that i < j, if the time required by drop ‘i’ is less than equal to the time required by drop ‘j’ then it will get merged in drop j and will come out with drop ‘j’.
Now make a stack to store the time of each drop moving separately and the ans will be the size of the stack in the end.
Iterate from i = 0 to i = n-1. For each drop ‘i’, check with drops stored in the stack that if they are merging with ‘i’th drop or not.
While the stack is not empty and drops on the top of the stack are merging with the drop ‘i' keep poping.
Push the ‘i’ drop in the stack.
Return the size of the stack.

We can observe all the drops before a slower drop will mix with it. And all the drops after the slower drop mix with the next slower drop and so on.

For example, if the times to reach the end are - 12, 3, 7, 8, 1 (sorted according to positions)

0th drop is slowest, it won’t mix with the next drop
The 1st drop is faster than the 2nd drop so they will mix and the 2nd drop is faster than the 3rd drop so all three will mix together.
They cannot mix with the 4th drop because it is faster.
So we used a stack to maintain the time of drops in increasing order to check efficiently for every next drop.

Space Complexity: O(n)Explanation:

O(N), Where N is the total number of droplets.

As we have a list of pairs of size N where each pair contains the position of every droplet and its respective time to reach the destination.

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), Where N is the total number of droplets.

N operations to make a list of pairs where each pair contains the position of every droplet and its respective time to reach the destination.

Then N * log(N) operations to sort the list of pairs on the basis of positions.

N operations to figure out which all drops mix together, and which all don't. We used a stack for this.

Top SPRINKLR Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern