Hello guys, this is my first question here on Hashnode. I would like to get an answer to a question that I was asked during an interview process about 4 months before. Of course, I was unable to solve it then with required complexity limits, and I'm unable to solve it now. So, would really appreciate if any of you could help. Thanks in advance.
Thirsty Man Problem (4 days) Suppose there is a thirsty man in the desert carrying a magic bottle with infinite capacity. There is a circular desert path with n oasis along the way. The person should not leave the path as he might get lost.
You can assume two different sets of information:
Write a program in your preferred Language to calculate the first point from where the person will be able to complete the trip without running out of water. (The person will stop at each oasis and will fill all the water from the oasis). Assume for 1 litre of water, the person can go 1 unit of distance. Also, provide the complexity of the Solution and your reasoning behind the solution.
For example, let there be 4 oasis with amount of water and distance to next oasis value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The first point from where person can make a circular tour is 2nd oasis. Output should be “start = 1′′ (index of 2nd oasis).
Expected time complexity: O(n) or less. You can use any favourable programming language.
A possible solution in JS (written in under 20 minutes):
const oasis = [
[4, 6],
[6, 5],
[7, 3],
[4, 5]
]
function rightWay(oasis = []) {
return `start = ${oasis.reduce((previousResult, [newWater, nextWay], index) => {
if (typeof previousResult === 'number' || newWater < nextWay) {
return previousResult
}
const path = [...oasis.slice(index), ...oasis.slice(0, index)]
let water = 0
return path.every(([newWater, nextWay]) => {
water += newWater - nextWay
return water >= 0
})
? index
: previousResult
}, 'impossible')}`
}
console.log(rightWay(oasis))
Mev-Rael
Executive Product Leader & Mentor for High-End Influencers and Brands @ mevrael.com
If you would be able to define your question from the data structure and algorithm point of view Google could help you.
What you have is called a circular linked list.
Problem you have originally was defined as a "petrol pumps problem/algorithm".