Dictionary

The questions below are due on Monday October 12, 2026; 11:59:00 PM.
 
You are not logged in.

Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.
Back to Exercises

In this exercise, we'll implement a struct similar to Python-style dictionaries, where we have keys mapping to values. The keys are unique, while the values need not be unique. We'll use a concrete example, but the technique can be generalized to any types.

Suppose we own a grocery store, and we want to keep track of prices for various items. Each item is labeled with an integer ID, which is its key, and is mapped to its decimal price, which is its corresponding value.

We will implement this struct as an int array for keys and a float array for values such that values[i] is the value corresponding to key keys[i]. As is common with array-type structures in C, we will also store its size. Finally, not all entries in the array will be in use all the time, so we'll have a true/false array to indicate whether a given index i is in use.

Here is the struct:

typedef struct {
  int* keys; // array of keys
  float* values; // array of values
  int* in_use; // 0 for no, 1 for yes
  int max_size; // length of keys array (same as values array)
} dictionary;

1) Find key

1.1) Exercise 1

Consider a dictionary where keys = {1000, 1001, 1002, 1003}, values = {1.58, 3.42, 100.24, 0}, in_use = {1, 1, 0, 0}, and max_size = 4. We want to know the values corresponding to certain keys, if they are valid.

What should be the value corresponding to the key 999?

What should be the value corresponding to the key 1000?

What should be the value corresponding to the key 1003?

There are many operations we may want to do with a dictionary, most of which start with determining whether a given key exists.

1.2) Exercise 2

Write a function which returns the index for a given key, if it exists, or returns -1 if the key is invalid.

You may feel free to call find_key for the rest of this exercise, and it will call a working implementation.

2) Find value

2.1) Exercise 3

Write a function which returns the value corresponding to a given key, if it exists, or return -1 if the key is invalid.

3) Update

Next, we start manipulating the dictionary. The first thing we want to do is insert (key, value) pairs into it. In Python, this was accomplished by dict[key] = value. However, it is not as simple here. In order to maintain the invariant that all keys are unique, we cannot simply append the key and value to the end of their respective arrays. Rather, we have to check whether the key exists. If it does, then no new key should be created; rather the existing one gets its value updated. If it does not, then we make a new key. For the purpose of this exercise, it should be inserted at the lowest index that is not in use.

3.1) Exercise 4

Write a function that puts a (key, value) pair into a dictionary. If the key exists, its value should be updated and return 0. If the key is invalid, then insert the key into the first array entry that is not in use and return 1; if the array is full and the new key cannot be inserted, return -1.

4) Remove

Removing an element is a lot simpler in our implementation. In particular, we don't have to actually remove data from the arrays. Rather, we can just mark the index as no longer in use and able to be overwritten.

4.1) Exercise 5

Write a function that takes a key and removes that key, value pair from a dictionary, if it exists. If it exists, return 0. If the key is invalid, return -1.

This naive implementation is not particularly efficient, having to potentially loop through the entire array each time to check whether a key exists. There are more efficient data structures that can avoid or lessen the time spent on searching for a key. You will learn about some of these, such has hash tables, in your algorithms classes.

Back to Exercises