03.md

Cracking the Coding Interview: 6th Edition (in C++)

Return to README

See also: Completed Question List)

Chapter 03 | Stacks and Queues

3.1: Three in One ./ctci6 03 01

• Describe how you could use a single array to implement three stacks.
  • main.cpp
  • header.hpp
  • source.cpp

3.2: Stack Min ./ctci6 03 02

• How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? push, pop, and min should all operate in O(1) time.
  • main.cpp
  • header.hpp
  • source.cpp

3.3: Stack of Plates ./ctci6 03 03

• Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold.

  Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity.

  SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack

  • FOLLOW UP
    
    • Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
  • main.cpp
  • header.hpp
  • source.cpp

3.4: Queue via Stacks ./ctci6 03 04

• Implement a MyQueue class which implmenets a queue using two stacks.
  • main.cpp
  • header.hpp
  • source.cpp

3.5: Sort Stack ./ctci6 03 05

• Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array).

  The stack supports the following operations: push, pop, peek, and isEmpty.

  • main.cpp
  • header.hpp
  • source.cpp

3.6: Animal Shelter ./ctci6 03 06

• An animal shelter, which holds only dogs and cats, operates on a strictly "first in, first out" basis.

  People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type)

  They cannot select which specific animal they would like.

  Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat.

  You may use the built-in LinkedList data structure.

  • main.cpp
  • header.hpp
  • source.cpp

Return to README

See also: Completed Question List