1
\$\begingroup\$

I am working on a Code Kata

// There is a queue for the self-checkout tills at the supermarket. 
// Your task is write a function to calculate the total time 
// required for all the customers to check out!
// input
// customers: an array of positive integers representing the queue. 
//    Each integer represents a customer, and its value is the amount 
//    of time they require to check out.
// n: a positive integer, the number of checkout tills.

A common solution is

function queueTime(customers, n) {
  // create a new array to represent each till
  // start each till at 0 minutes
  const tills = new Array(n).fill(0);
  // loop through the customers
  for (let i = 0; i < customers.length; i++) {
    // find till with least minutes 
    const shortestTill = Math.min(...tills)
    // find index of shortest till
    const index = arr.indexOf(shortestTill)
    // increase shortest till mins with current customer
    arr[index] += customers[i];
  }
  // return the longest till 
  return Math.max(...tills);
}

My first solution, although longer, seems to work however it times out when I run it in node with a large data set. I am sure there is probably some time complexity issue or infinite loop that I am creating but can not identify.

Where in my code should I refactor to fix this issue?

function queueTime(customers, n) {
  // checking edge case
  if (customers.length === 0) return 0
  // initial time
  let time = 0
  // create a lookup to see if each till is open, where each
  //key is the till number and the val is the time needed for each to finish
  memo = {}
  for (let i = 1; i <= n; i++) {
    memo[i] = customers.shift()
  }
  // not necessarily needed because I'm using returns in the while loop,
  // but the intention is to break the loop
  let completed = false
  // solving the problem was taking two different approaches so
  // this variable allows me to check which approach to use
  let moreTillsThanCustomers = false
  // len = memo.length
  let len = Object.keys(memo).length
  for (let i = 1; i <= len; i++) {
    // if any didn't have a customer to fill the spot, then moreTillsThanCustomers = true
    if (memo[i] === undefined) {
      moreTillsThanCustomers = true
    }
  }
  if (!moreTillsThanCustomers) {
    while (!completed) {
      let found = false
      // if there are any open spots and customers left, we 'found' a spot to fill and can break out of the loop
      for (let i = 1; i <= len; i++) {
        if (memo[i] === 'open') {
          if (customers.length) {
            memo[i] = customers.shift()
              found = true
              break
          }
        }
      }
      // if no spot was found, increase the time by one  and reduce all
      // till times by 1 or to 'open
      if (!found) {
        time++
        for (let i = 1; i <= len; i++) {
          if (memo[i] === 1) {
            memo[i] = 'open'
          } else {
            memo[i]--
          }
        }
      }
      // if every value is 'open' and there are no customers left, we're done
      if (Object.values(memo).every(value => value === 'open')&& !customers.length) {
        completed = true
        return time
      }
    }
    // if there are more tills than customers
  } else {
    while (!completed) {
      // if a  memo is at 0, it's done, otherwise reduce it by one
      for (let i = 1; i <= len; i++) {
        if (memo[i] === 0) {
          memo[i] = undefined
        } else if (memo[i] !== undefined) {
          memo[i]--
        }
      }
      // if all are done, we're done
      if (Object.values(memo).every(value => value === undefined)) {
        completed = true
        return time
      }
      //increase time
      time++
    }
  }
  return time
}

Times out in node

console.log(
  queueTime([28, 9, 27, 37, 12, 33, 20, 31, 19, 18, 3, 8, 39, 40, 49], 5)
)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.