1 simple hashing bootstrap exercise in this task we will be implementi
Search for question
Question
1. Simple Hashing
Bootstrap Exercise
In this task, we will be implementing a simple container for integers, where:
The range of integer values that can be inserted into the container is known ahead of time
The insertion process must be fast. The function add must run in O(1) time.
The lookup process must be fast. The function search must run in O(1) time.
When you bootstrap this exercise, you will get a header file Container.h. That is where the fast
container must be implemented. You have access to LinkedList.h and ArrayList.h. The current
implementation relies on keeping a list of data sorted at all times so that we can have a fast
search procedure. Whenever a new value is added to the container, it simply appends it and
uses insertion sort to put it in the right place. (Why insertion sort and not quick sort?) The search
process then relies on binary search, which is plausible here since the data is kept in sorted
order.
This implementation is too slow. The insertion happens in O(n), and the searching runs in
O(nlogn).
You may use LinkedList.h and/or ArrayList.h in whatever way you need to in order to pass the
unit tests. In addition to correctness, the suite also tests for speed. The problem being solved in
main.cpp is a simulation where we add n values into the container. For every addition, we
perform n searches, in order to strain the system. We expect that with your implementation will
allow a problem of size 5000 to compete in less than 1 second.
NEED TO -
write this in C++ in the Container.h file