Imagine you have a sorted list of names, and you are using binary search to find a certain name. Answer the following questions and explain your thought process:

1. If the list contains 64 names, what is the maximum number of steps it would take to find the name?

   6 → We know that the Big Oh runtime of Binary Search is $log_2n$ so, at most, it would take $log_264$ steps to find the name which evaluates to 6.

2. What if the size of the list doubles (to 128 names)?

   7 → We know that the Big Oh runtime of Binary Search is $log_2n$ so, at most, it would take $log_2128$ steps to find the name which evaluates to 7.

Suppose you have a contact list where each name is associated to a phone number. The contact list is sorted in alphabetical order by name. What is the Big Oh runtime of your algorithm if you wanted to do the following operations. Explain:

1. You have a person’s name, and you want to find their phone number.

   $O(log_2n)$ → Because the list is sorted by name we can leverage binary search and the Big Oh of binary search is $log_2n$.

2. You have a person’s phone number, and you want to find their name.

   $O(n)$ → Since the list is only ordered by name, we cannot use binary search. Therefore, we would have to iterate over (potentially) every item in the list.

3. You want to read through the phone numbers of every person whose name starts with the letter E.

   $O(n)$ → Potentially all names start with E.

You have been asked to consult on a project for Pely, a popular restaurant review app. They are trying to expand their interface to allow customers to get added to a wait list of a restaurant from their app. They need your input on the data structure they should use to add and remove people from their list easily and efficiently. They want you to take into consideration that the wait lists can grow and shrink very fast.

⚠️  assume people cannot leave the list in the middle they can either get seated or get added to the list.

a. What data structure would you recommend for this feature? Why?

I would recommend a Queue. The first person to get added to the waitlist should be the first person to be seated. This is FIFO behavior which is the behavior queues follow.

b. Would you suggest implementing this data structure using a linked list or an array? Why?

Because the waitlist can grow and shrink rapidly and we do not know how many people will want to get added to a waitlist, I would use a linked list since linked lists are dynamically sized.

Popular music streaming apps “Bannana Music” and “Dotify” have a “play next” feature that allows users to choose the song they want to listen to next. However, the feature works differently in each of these apps as explained below:

Imagine the user picks songs to listen to next in this order:

PlayNext → “As It Was by Harry Styles"

PlayNext → “Flowers by Miley Cyrus”

PlayNext → “Kill Bill by Sza”

What data structure is used by each streaming app to keep track of the songs’ playing order? Explain.

Bannana Music → Stack → LIFO behavior

Dotify → Queue → FIFO behavior

Suppose that you have a max priority queue consisting of “Task” objects.

• Each task object has an escalationLevel attribute that is an integer value assigned at creation. The higher the escalation level value, the faster the task should be resolved. The Task class defines the “<” operator for Task objects based on escalationLevel, i.e.:
  • TaskA < TaskB returns true if TaskA.escalationLevel < TaskB.escalationLevel
• We can create a new task with the following code: new Task(name, priorityLevel)
• If two tasks with the same escalationLevel get added, the one that was added first should have greater priority (should leave the queue first)
• Assume that the queue is stored in least to greatest order of escalationLevel (low priority → high priority)

Knowing this information, answer the following questions:

1. Assuming the queue starts as empty, draw the queue that would result from the following adds:

   add (new Task (a, 1))
   add (new Task (b, 2))
   add (new Task (c, 3))
   add (new Task (d, 1))
   

   

   The reason that we would add the nodes in order of escalationLevel is because this is a priority queue.

2. Given the priority queue that was created above, what Task would be returned by calling the peek( ) method?

   

   The reason why we peek from the back even though this is a queue, is because this is a max priority queue (reference the code from class for the priority queue remove or peek methods)

3. What would the queue look like if we ran each of the following method calls in the order shown? Draw the resulting queue.

   remove ()
   remove ()
   add (new Task(e, 1))
   add (new Task(g, 3))
   add (new Task(f, 2))
   remove ()
   remove ()
   

   

4. Explain how you would implement a stack using a single queue. Assume you have access to the code for the doubly linked list-based queue we wrote in class. Make sure you explain how you would go about creating the following methods and draw pictures as needed:

<aside> ⚠️ you shouldn’t change anything in the ListQueue.h file. You are trying to create a ListStackQ class with the “guts” of it being the ListQueue. Just like in the ListQueue class the DblList is the “guts”. So, you ONLY have access to the ListQueue interface (i.e. add(), remove(), peek(), isEmpty(), size(), …)

</aside>

• push ( )
• pop ( )
• peek ( )

link to video explanation

7. Implement the deleteList() method in the DblList class below. This method should traverse the list and remove all nodes, effectively clearing it.

template<typename T>
void DblList<T>::deleteList(){
    ListNode<T>* current = m_front;
    while (current != NULL) {
        ListNode<T>* temp = current;
        std::cout << "Deleting node with data: " << temp -> m_data << std::endl;
        current = current->m_next;
        delete temp;
    }
    m_front = NULL;
    m_back = NULL;
    m_size = 0;
}

or

template<typename T>
void DblList<T>::deleteList(){
    ListNode<T>* current = m_front;
    while (current != NULL) {
        std::cout << "Deleting node with data: " << m_front -> m_data << std::endl;
        removeFront();
    }
    m_front = NULL;
    m_back = NULL;
    m_size = 0;
}