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

Fig: 1