Week 09 Lab Solution

Hash Table Implementation and Applications

Sample Solutions

`HashTableInsert`

void HashTableInsert(HashTable table, int key, int value) {
	if (table->numItems > table->numSlots * MAX_LOAD_FACTOR) {
		resize(table);
	}

	int index = hash(key, table->numSlots);
	while (!table->slots[index].empty && table->slots[index].key != key) {
		index = (index + 1) % table->numSlots;
	}

	table->slots[index].key = key;
	table->slots[index].value = value;
	if (table->slots[index].empty) {
		table->slots[index].empty = false;
		table->numItems++;
	}
}

`HashTableDelete`

void HashTableDelete(HashTable table, int key) {
	int index = getIndex(table, key);
	if (index == MISSING_INDEX) {
		return;
	}

	table->slots[index].empty = true;
	table->numItems--;

	index = (index + 1) % table->numSlots;
	while (!table->slots[index].empty) {
		table->slots[index].empty = true;
		table->numItems--;
		HashTableInsert(table, table->slots[index].key, table->slots[index].value);
		index = (index + 1) % table->numSlots;
	}
}

`findMissingInteger`

The idea is to use a hash table to make checking if an integer is in the array fast. The keys are obviously integers from the array, but it doesn't matter what values we store in this case. Nevertheless, HashTableInsert requires a key and a value, so this solution just passes a value of 0 each time.

int findMissingInteger(int *integers, int n) {
	HashTable seen = HashTableNew();
	for (int i = 0; i < n - 1; i++) {
		HashTableInsert(seen, integers[i], 0);
	}

	int missingInteger = 0;
	for (int k = 1; k <= n; k++) {
		if (!HashTableContains(seen, k)) {
			missingInteger = k;
			break;
		}
	}

	HashTableFree(seen);
	return missingInteger;
}

`findWinner`

This time, the idea is to use a hash table to make it fast to get the number of votes each candidate has.

int findWinner(int *ballots, int numBallots) {
    HashTable voteCounts = HashTableNew();
    for (int i = 0; i < numBallots; i++) {
        int candidate = ballots[i];
        int votes = HashTableGetOrDefault(voteCounts, candidate, 0);
        HashTableInsert(voteCounts, candidate, votes + 1);
    }

    int winner = ballots[0];
    int winnerVotes = HashTableGet(voteCounts, winner);
    int numWinners = 1;
    for (int i = 1; i < numBallots; i++) {
        int candidate = ballots[i];
        if (candidate == winner) {
            continue;
        }

        int votes = HashTableGet(voteCounts, candidate);
        if (votes > winnerVotes) {
            winner = candidate;
            winnerVotes = votes;
            numWinners = 1;
        } else if (votes == winnerVotes) {
            numWinners++;
        }
    }

    HashTableFree(voteCounts);
    return numWinners == 1 ? winner : NO_WINNER;
}

`areSimilarStrings`

We do as the hints described for this task and use two hash tables:

The s1to2 table stores all of the replacements for all of the characters in s1 that turn it into s2.
The s2to1 table stores all of the replacements for all of the characters in s2 that turn it into s1.

If the two strings are similar, then these two replacements should be the inverses of each other, i.e. s1[i] and s2[i] should always replace each other for all i.

bool areSimilarStrings(char *s1, char *s2) {
    int m = strlen(s1);
    int n = strlen(s2);
    if (m != n) {
        return false;
    }

    bool similar = true;
    HashTable s1to2 = HashTableNew();
    HashTable s2to1 = HashTableNew();
    for (int i = 0; i < m && similar; i++) {
        char r1 = HashTableGetOrDefault(s1to2, s1[i], s2[i]);
        char r2 = HashTableGetOrDefault(s2to1, s2[i], s1[i]);
        if (r1 != s2[i] || r2 != s1[i]) {
            similar = false;
        } else {
            HashTableInsert(s1to2, s1[i], s2[i]);
            HashTableInsert(s2to1, s2[i], s1[i]);
        }
    }

    HashTableFree(s1to2);
    HashTableFree(s2to1);
    return similar;
}