Implementation of a ticket queue system in JavaScript

Question

I got this question during an interview. The question itself was very open-ended - it asked me to implement a ticket queue system, where by default it would have 3 different queues to hold tickets that are of severity 1, severity 2, and severity 3 respectively. It should have functionalities like:

1. add a ticket to the corresponding queue
2. get the ticket from the highest severity (priority) queue
3. resolve ticket i.e. remove the ticket from the queue
4. loop over the tickets starting at the highest severity to the lowest severity
5. check if a ticket is in the queue.

Finally, the design should be easily extensible to adapt future changes e.g. adding a new queue.

It doesn't have any predefined data structure for either the queue or the ticket so we have to come up with our own design. Here is how I implemented:

First for the tickets I have a class Ticket:

class Ticket {
  constructor({ name, desc = '', severity }) {
    this.id = Math.floor(Math.random() * 1000)
    this.timestamp = Date.now()
    this.name = name
    this.desc = desc
    this.severity = severity
  }
}

And for the ticket queues I have this:

class TicketQueues {
  constructor(numOfQueues = 3) {
    this.queues = Array.from({ length: numOfQueues }, () => [])
    this.hashSet = new Set()
  }

  addTicket(ticket) {
    if(this.hasTicket(ticket)) return false
    const severityIndex = ticket.severity - 1
    this.queues[severityIndex].push(ticket)
    this.hashSet.add(ticket)

    return true
  }

  *getTicketBySeverity() {
    for (const queue of this.queues) {
      for (const ticket of queue) {
        yield ticket
      }
    }
  }

  getTicketAtHighestSeverity() {
    for (const queue of this.queues) {
      for (const ticket of queue) {
        return ticket
      }
    }
  }

  resolveTicket(ticket) {
    if(!this.hasTicket(ticket)) return false

    const [severity, index] = this._findTicketIndex(ticket)
    this.queues[severity].splice(index, 1)
    this.hashSet.delete(ticket)

    return true
  }

  _findTicketIndex(ticket) {
    for (let i = 0; i < this.queues.length; i++) {
      for (let j = 0; j < this.queues[i].length; j++) {
        if (this.queues[i][j] === ticket) {
          return [i, j]
        }
      }
    }
    return [-1, -1]
  }

  hasTicket(ticket) {
      return this.hashSet.has(ticket)
  }
}

The idea is that I have a two-dimensional array to represent the ticket queue system. The first array inside the two-dimensional array has the highest severity.

i.e. [ [ticket1] , [ticket2], [ticket3]] means we have one ticket for severity 1 and 2 and 3

And I also have a hash set to hold a reference to every ticket so I can achieve constant time look up. For getTicketBySeverity I implemented a generator function and the idea here is to take advantage of the lazy evaluation of generators since the data set might be huge so the user might not want to iterate through the whole list of tickets.

Please feel free to give me any feedback that you think might be helpful. There are a few design decision that I couldn't really think through all of the pros and cons and I would like you to give me some suggestion on the following design choices:

1. As I mentioned I used two-dimensional array to hold the tickets, and it worked out fine. However one alternative I can think of is to use a hash map. so instead of having [ [ticket1] , [ticket2], [ticket3]] we have

{
  sev1: [ticket1],
  sev2: [ticket2],
  sev3: [ticket3],
  ...
}

I couldn't really pinpoint exactly what are some of pros and cons of using either one data structure. One argument I can think of that is against using a hash map is that there might be an issue when looping through all of the tickets in the order of severity since normally hash map doesn't have the notion of order for keys. Another way I can think of is to have separate variable for each queue. so

class TicketQueues {
  constructor(numOfQueues = 3) {
    this.sev1Queue = []
    this.sev2Queue = []
    this.sev3Queue = []
  }

However it seems cumbersome to me but I still am not super clear what exactly is bad about this design.

2. I am using reference equality to find the ticket instead of using an id. Not sure in real world scenario which approach is better. I guess using id is better since it is not always possible to keep the original reference for the object?

3. To bucket the ticket to the right queue, the current implementation relies on the user to specify the correct severity i.e. 1, 2, 3. If they use some weird to represent the severity then it would break e.g. A B C. I guess this can be partially addressed by using TypesScript with either Enum or Union type so the user will know the severity's type. However another approach I thought of is to expose specific API for each valid severity queue we have for the user to use. For example,

class TicketQueues {
    constructor(numOfQueues = 3) {
        this.queues = Array.from({length: numOfQueues}, () => [])
    }
  
    addSev1(ticket) {
      this.queues[0].push(ticket)
    }
  
    addSev2(ticket) {
      this.queues[1].push(ticket)
    }
  
    addSev3(ticket) {
      this.queues[2].push(ticket)
    }

but again I cannot really pinpoin exactly which approach is better. The second approach feels like it is hard for us to extend the queues if we ever need to add another queue, since we would have to add another method for the new queue.

4. the current implementation is inherently susceptible to starvation. e.g. as long as the sev1 queue is not empty, we will always start with tickets in sev1 queue when looping over the system even when there might a sev2 ticket that has been there for a long long time.

5. Lastly, I wonder if we can use priority queues instead of plain old queues here?

Answer 1

Responses to your questions

1. I think for this specific case, a two-dimensional array would is a great data structure to solve the problem of multiple ticket queues. Like you mentioned, giving concrete names to each ticket queue would just add complexity to the code, because you would then have to sort the named queue by priority whenever you want to use them - effectively turning them into the 2d array you currently have.

2. When checking for the existence of a ticket, you are correct in assuming that it would be better to check the id instead of using a reference to the original object. I think your choice of a set was the wrong data structure to hold all of your tickets in. If you instead did a map (either a Map instance or a plain object), then it would be much easier to look up tickets by id.

3. I would just not worry about data validation here for the following reasons:

   • Like you mentioned, it's really the job of typescript to do that kind of validation.
   • There's a number of bad parameters a user could pass into this class to put it in a bad state. Too much validation bloats code, making it difficult to read, and can do more harm than good. Validation is more important when the data you're receiving is foreign to the project you're working in. i.e. validate when coding publicly-exposed library methods, in rest endpoint handlers, reading config files, etc. Don't bother when creating the internals of a project.

4. The fact that this implementation is susceptible to starvation is due to the design requirements, isn't it? There's nothing you can do about it in your implementation.

5. Using a single priority queue instead of a separate queue for each severity would also work. Adding new entries will be a little slower as it would have to sort them into the right spot. Removing entries from the middle is likely quicker because priority queues are often implemented using a heap. The main issue is that there is no native priority queue in javascript, making this solution more difficult.

As an aside: The computer science definition of the word "queue" doesn't allow removing entries from the middle of the queue. That kind of flexibility is supposed to belong to lists or arrays.

Code quality notes

You did a really good job with your function naming. Overall, the code was easy enough to understand.

If you really expect a large amount of tickets to be in this system, then you ought to be able to generate more than 1000 unique ids. The current implementation will have a lot of id clashes.

Instead of looping over an array and yielding each entry, you can yield* entireArray.

Simplified example

The problem description didn't state how many tickets were expected to be in the queue at a given time, or how often a user would read from it, or add a ticket to it, etc. There's a number of different data structures that can be used to optimize the code - the right one would depend on which aspects need to be fast, and which ones are OK being a little slower.

The following solution is meant to be a dead simple solution that's easy to understand and modify, but will start to run slow if you put too many tickets into the system. Code like this is ideal when you don't expect many tickets or much usage.

const generateId = () => Math.floor(Math.random() * 1e12)

export const createTicket = ({ name, description = '', severity }) => Object.freeze({
  id: generateId(),
  timestamp: Date.now(),
  name,
  description,
  severity,
})

export function createTicketCollection() {
  const tickets = {}
  const getBySeverity = () => Object.values(tickets).sort(
    (a, b) => (a.severity - b.severity) || (a.timestamp - b.timestamp)
  )
  return Object.freeze({
    add(ticket) { tickets[ticket.id] = ticket },
    getBySeverity,
    getTicketAtHighestSeverity: () => getBySeverity()[0],
    resolve(ticket) { delete tickets[ticket.id] },
    has: id => !!tickets[id],
  })
}

(classes can of course be used instead of factory functions - I just tend to prefer factory functions)

Optimized example

On the other end of the spectrum, if you want all of the operations performed against the system to run fast, then a combination of a map (for quick lookup by id), and a doubly-linked list (for quick iteration and removal of entries) will allow all function to run in a constant big-O (even faster than a priority queue). Optimizations like this will naturally cause the code to be less readable and less flexible, which is why it's never good to prematurely optimize. I do not recommend actually using a design like this unless it is really needed, but I'll post it here as a proof-of-concept. (I've done some light testing with it, but there could still be some bugs).

const generateId = () => Math.floor(Math.random() * 1e12)

function createLinkedList() {
  let front, back
  return Object.freeze({
    get front() { return front },
    get back() { return back },
    pushBack(value) {
      const node = { last: back, next: undefined, value }
      if (back) back.next = node
      back = node
      if (!front) front = node
      return node
    },
    removeNode(node) {
      if (node.last) node.last.next = node.next
      if (node.next) node.next.last = node.last
      if (front === node) front = node.next
      if (back === node) back = node.last
    },
    *values() {
      let node = front
      while (node) {
        yield node.value
        node = node.next
      }
    },
  })
}

const createTicket = ({ name, description = '', severity }) => Object.freeze({
  id: generateId(),
  timestamp: Date.now(),
  name,
  description,
  severity,
})

export function createTicketCollection() {
  const listNodeLookup = {}
  const severityGroups = []
  function* getBySeverity() {
    for (const linkedList of severityGroups.filter(x => x != null)) {
      yield* linkedList.values()
    }
  }
  return Object.freeze({
    add(options) {
      const ticket = createTicket(options)
      severityGroups[ticket.severity] ??= createLinkedList()
      const listNode = severityGroups[ticket.severity].pushBack(ticket)
      listNodeLookup[ticket.id] = listNode
      return ticket
    },
    getBySeverity,
    getTicketAtHighestSeverity: () => getBySeverity().next().value,
    resolve(ticket) {
      const listNode = listNodeLookup[ticket.id]
      delete listNodeLookup[ticket.id]
      severityGroups[ticket.severity].removeNode(listNode)
    },
    has: id => !!listNodeLookup[id],
  })
}

Update

In response to @Joji's comment about why I prefer factory functions over classes:

This question actually made me do some deep thinking. In the end, I think it's simply because factory functions tend to work better when programming in a functional style, while classes tend to fit better when programming in an object-oriented style. I usually program in a more functional style, but I'm not hard-core about it.

Let me expound:

I consider this solution "object-oriented" because I'm encapsulating private data and only allowing the private data to get touched via the methods I provide. This can be achieved with both factory functions or classes. I used factory functions there as it felt more concise, but if you continued to add more and more methods to it, it might start to feel clunky and hard to work with (i.e. private functions have to be declared at the top, not next to the public method that needs it). Maybe a normal class would have been a better tool to use in this scenario (I do sometimes use the class syntax too, just not as often).

Now I want to show the same answer but written in a way that's a little more functional.

// ticket.js

const generateId = () => Math.floor(Math.random() * 1e12)

export const create = ({ name, description = '', severity }) => Object.freeze({
  id: generateId(),
  timestamp: Date.now(),
  name,
  description,
  severity,
})


// ticketCollection.js

export const create = ({ ticketsById = {} } = {}) => Object.freeze({ ticketsById })

export const getBySeverity = ticketCollection => Object.values(ticketCollection.ticketsById).sort(
  (a, b) => (a.severity - b.severity) || (a.timestamp - b.timestamp)
)

export const getTicketAtHighestSeverity = ticketCollection => getBySeverity(ticketCollection)[0]

export const addTicket = (ticketCollection, ticket) => create({
  ticketsById: { ...ticketCollection.ticketsById, [ticket.id]: ticket },
})

export const resolve = (ticketCollection, ticket) => {
  const ticketsById = { ...ticketCollection.ticketsById }
  delete ticketsById[ticket.id]
  return create({ ticketsById })
}

export const has = (ticketCollection, id) => !!ticketCollection.ticketsById[id]

Note that we've sacrificed our encapsulation, all data is now publicly accessible (a no-no in OOP). But we've gained other benefits in the process:

• We're not mutating data anymore (leading to fewer unexpected side-effects).
• We now have the power to organize the methods into separate modules if desired (they don't all have to be right there)
• My favorite one: We don't have to tie specific methods to specific classes. As a concrete example: I've been porting some user management code to node. The old implementation was written in a very object-oriented way. There was a User class, and a Group class. user's were members of groups, and groups had users in them. So, which class do you think the implementors put the addUserToGroup() function? If it's put in the User class, how would it update the group's member list? If it's put in the group's class, how will it update the user's group list? Their solution was pretty gross: They put it in both. The addUserToGroup() method on both the user and group class would update their own internal data, then they would call each other's methods using a special optional parameter to keep them from calling each other yet again. There are arguably better ways to do that while still following OOP style, but none of them are very elegant. The port I wrote didn't have a User or Group class, there were just functions to get or set user/group data. Because these encapsulation boundaries didn't exist, there only needed to be one addUserToGroup() function.

If we're programming in this style, it should hopefully be clearer why the factory functions work a little better. The actual instances of the factory are just pure data, usually, there are few to no functions as those are all found outside of the factory. In this case, it's much easier to just have a function that returns an object literal, then to write a class that takes parameters in a constructor and assigns them all to "this".