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.
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:
- The amount of water that every oasis has.
- Distance from that oasis to the next oasis.
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.