Question $3$:

A$.$ Implement a stack data structure using Java that supports the following operations:

$1.$ push$($item$)$: Adds an item to the top of the stack

$2.$ pop$()$: Removes and returns the item at the top of the stack

$3.$ peek$()$: Returns the item at the top of the stack without removing it$.$

$4.$ is$\_$empty$()$: Returns True if the stack is empty, False otherwise

Now, extend your stack implementation to include a new operation:

$5.$ get$\_$min$()$: Returns the minimum item in the stack without removing it$.$

Explain how will you ensure that this operation has a time complexity of O$(1)$

B$.$ Provide the code for your stack implementation and demonstrate how you would use it to push and pop items, retrieve the top item, check if the stack is empty, and efficiently retrieve the minimum item.

C$.$ Test your stack implementation with various scenarios to ensure its correctness and efficiency, especially for the get$\_$min$()$ operation.

Question $4$: Implement a hash table data structure using Java.

Your implementation should include the following operations:

insert$($key$,$ value$)$: Inserts a key$-$value pair into the hash table.

get$($key$)$: Retrieves the value associated with a given key. If the key is not found, return None.

delete$($key$)$: Deletes a key$-$value pair from the hash table based on the provided key.

contains$($key$)$: Checks if the hash table contains a specific key and returns True if found, False otherwise.

keys$()$: Returns a list of all keys in the hash table.

values$()$: Returns a list of all values in the hash table.

$$

You can choose to implement collision handling using techniques like chaining $($linked lists$)$ or open addressing $($linear probing, etc.$).$

And ensure that your hash table can handle resizing when it reaches a certain load factor.

Provide the code for your hash table implementation, including any helper functions or classes, and demonstrate how you would use it to perform the above operations. Test your implementation with various scenarios to ensure its correctness and efficiency.

Please refer the following code snippet in Java below that implements a simple hash table:

import java.util.HashMap;

public class HashTableExample $\{$

$$ public static void main$($String$[]$ args$)\{$

$//$ Create a hash table

$$ HashMap hashTable $=$ new HashMap$<>()$;

$//$ Insert key$-$value pairs into the hash table

$$ hashTable.put$("$apple$",5)$;

$$ hashTable.put$("$banana$",7)$;

$$ hashTable.put$("$orange$",3)$;

$$ hashTable.put$("$grape$",9)$;

$//$ Retrieve the value associated with a specific key

$$ int bananaQuantity $=$ hashTable.get$("$banana$")$;

$$ System.out.println$("$Quantity of bananas: $"+$ bananaQuantity$)$;

$//$ Check if a key exists in the hash table

$$ boolean containsPear $=$ hashTable.containsKey$("$pear$")$;

$$ System.out.println$("$Does the hash table contain 'pear'? $"+$ containsPear$)$;

$//$ Remove a key$-$value pair from the hash table

$$ hashTable.remove$("$orange$")$;

$//$ Print all keys and their corresponding values in the hash table

$$ for $($String key : hashTable.keySet$())\{$

$$ int value $=$ hashTable.get$($key$)$;

$$ System.out.println$("$Key: $"+$ key $+",$ Value: $"+$ value$)$;

$\}$

$\}$

$\}$

a$)$ Explain the purpose of the $$HashTableExample$$ class and its methods.

b$)$ Describe the process of inserting key$-$value pairs into this hash table.

c$)$ Demonstrate how to retrieve the value associated with the key "banana" from the hash table.

d$)$ Explain the role of the $$containsKey$$ and how it can be useful. What is the role of $$containsKey$$ here?

e$)$ How would you remove the key$-$value pair associated with the key "orange" from the hash table?

f$)$ Provide a code snippet to print all keys and their corresponding values in the hash table.