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.

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".

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

@lichtjaeger Neither am I. But the way I see O(n) terminology is like this: In very-very simple/brief form, an O(n) solution would be the one where, even for the worst case scenario, the maximum number of iterations of a loop would be equal to the number of inputs(n). For eg. a loop inside a loop, would be a O(n^2) solution. Same logic applies for both time-complexities and memory complexities. So, if for 1 input, the program produces the output in 4s(assume) and consuming 4KB(assume) of memory, then if 10 inputs are fed, if the program has O(n) complexity, it would produce the output in a maximum of 40s and would consume 40KB of memory at most. Hope that gives you an idea and clarifies a bit.

I have run some test and it looks like my first attempt is better than O(n) and the solution with for ... of is even better and faster.

@lichtjaeger thanks for the clarification.

Thread

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.

Responses(2)

Search Hashnode

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.

Responses(2)