3
\$\begingroup\$

Got this problem in a coding interview - Get the max value of a stack in O(1). The stack contains numbers only. Please review my solution.

class Stack {

      data;
      maxVal;

  pop() {
    return this.data.pop();
  }

  insert(x) {
    const cm = new CheckMax();
    this.data.push(x);
    this.maxVal = cm.max.call(this);
  }

  peek() {
    return this.data[this.data.length - 1];
  }
}

class CheckMax {

  max() {
    let maxVal = this.maxVal;
    let oldVal;
    if (this.data.length > 0) {
      oldVal = this.peek();
      if (maxVal == undefined) {
        maxVal = oldVal;
      }
      if (oldVal > maxVal) {
        maxVal = oldVal;
      }
    }
    return maxVal;
  }
}

const stack = new Stack();
stack.data = [];
stack.insert(123);
stack.insert(22);
stack.insert(23);
stack.insert(9);
stack.insert(73);
stack.insert(54);
console.log(stack.maxVal);

\$\endgroup\$
1
  • \$\begingroup\$ The code does not work. If you push [2, 1, 5] the max is 5. However if you pop the 5 the max remains 5 (should be 2)., If you then push a 4 the max is still 5 (should be 4). You need to recalculate the max each time the stack size changes, not just on the push what you called insert (BTW Stacks don't insert) \$\endgroup\$
    – Blindman67
    Oct 17, 2021 at 11:09

2 Answers 2

5
\$\begingroup\$

This solution looks incorrect and doesn't cover the case when the max value is popped.

For example,

const stack = new Stack();
stack.data = [];
stack.insert(1);
stack.pop();
console.log(stack.maxVal); // even though stack is empty, this will print 1, right?

I think one naive way to solve this is to store (internally) the max value along with the element value, at time of element insertion.

class Entry {
  constructor(value, maxValue) {
    this.value = value;
    this.maxValue = maxValue;
  }
}
// insert 1
[new Entry(1, 1)]
// insert 2
[new Entry(1, 1), new Entry(2, 2)]
// insert 1 - notice how the latest Entry has a value property of 1 but a maxValue property of 2 since the largest property seen so far is 2
[new Entry(1, 1), new Entry(2, 2), new Entry(1, 2)]
// pop - look at last Entry's max value to see max value (2)
[new Entry(1, 1), new Entry(2, 2)]
// pop - look at last Entry's max value to see max value (1)
[new Entry(1, 1)]
// pop - empty, so max value is undefined / null
[]

One way to implement this would be something like this

class Stack {
  constructor() {
    this.entries = [];
  }

  get maxValue() {
    // this value can be stored in an instance variable and updated on pop/push if access to value will occur frequently
    if (0 < this.entries.length) {
      return this.entries[this.entries.length - 1].maxValue;
    }
    return null;
  }

  pop() {
    return this.entries.pop();
  }

  push(value) {
    this.entries.push(
      new Entry(
        value,
        Math.max(
         value,
         this.maxValue
        )
      )
    );
  }
}

Another thing to watch out for - in every call to insert you are instantiating a new CheckMax instance which seems wasteful. CheckMax doesn't really contain any state and the this is referring to an instance of a Stack. I think it's more natural to add the logic in CheckMax on Stack itself.

Finally, the setting of the data property on a Stack instance seems like an internal implementation detail that the caller should not be worried about. I don't think the caller should have to initialize the data property on a Stack instance in order for it to work correctly. Whatever data structure the stack uses under the hood to keep track of elements should not be the concern of the caller of the stack.

\$\endgroup\$
2
\$\begingroup\$

The answer by Jae Bradley already mentions great points - the code should handle the case where elements are removed, and it is strange that the method in the CheckMax class is separate from the Stack class.

Formatting

If I saw this code in an interview one of the first things I would look at is the formatting - e.g. indentation, spacing. The indentation looks fairly consistent - i.e. two spaces, though the properties data and maxVal are indented with six spaces.

uninitialized data property

It seems strange that the data field is not initialized to an array when declared, and the sample usage assigns it before calling the insert method. If the class was used and the data property wasn't assigned then the following error would occur:

VM35:12 Uncaught TypeError: Cannot read property 'push' of undefined

comparison operators

In the CheckMax::max() method there is a loose comparison operator used:

 if (maxVal == undefined) {

A good habit and recommendation of many style guides is to use strict equality operators (i.e. ===, !==) whenever possible (like is used in the snippet above). The problem with loose comparisons is that it has so many weird rules one would need to memorize in order to be confident in its proper usage.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.