2012 KPCB Engineering Fellows Program - Challenge problem
C++ Shell
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
correctnesstest.cpp
queue.cpp
queue.h
readme.md
storagetest.cpp
test.sh

readme.md

KPCB Engineering Fellows Program - Challenge Problem

Applicant: Yang Su
Email: yang.su@duke.edu
Language C++

Problem:

Using only primitive types, implement a bounded queue to store integers. The data structure should be optimized for algorithmic runtime, memory usage, and memory throughput. No external libraries should be imported and/or used. The solution should be delivered in one class that provides the following functions:

  • constructor - class should provide one method for object creation that takes an integer to set the size of the queue.
  • enqueue - function should take an integer and store it in the queue if the queue isn't full. The function should properly handle the case where the queue is already full.
  • dequeue - function should return an integer if one is currently stored in the queue. The function should properly handle the case where the queue is empty.

Solution:

In order to save memory and allow for easy enqueuing and dequeuing of numbers from the queue, the BoundedQueue class is implemented so the numbers are stored in a contiguous memory block. The block starts out at size of 1 (storage for 1 int that is) and doubles in size every time the current block runs out of memory up to the max size specified when the BoundedQueue was constructed. Each time the size doubles, a new chunk of memory is allocated, the contents are then copied to the new block and the pointers updated, and the old block is discarded.

  • queue.h - heading for the BoundedQueue Class
  • queue.cpp - implementation details of the BoundedQueue Class
    • use INITIAL_SIZE to adjust the initial size of a new BoundedQueue. Default is 1
  • storagetest.cpp - a simple test that enqueues and dequeues a large number of elements (268435456 ints => 256*1024*1024* 4 = 1GB)
  • correctnesstest.cpp - a test that tests BoundedQueue against the STL queue and produces two output files, one corresponding to the operations in BoundedQueue, and the other corresponding to the operations in STL queue
  • test.sh - testing script that compiles BoundedQueue, times storagetest and runs correctness test with various parameters (the outputs are compared using diff), then cleans up the directory

to run test:

./test.sh