UOJ Passport Checking : Hash Table Method

The Interpol database contains a list of N stolen passport numbers. We have another list of M passport numbers to check if they are stolen or not.

Input

  • The first line of the input contains an integer N.
  • The next N lines contains the list of N stolen passport numbers, one passport number per line.
  • The next line of the input contains an integer M.
  • The next M lines contains the list of M passport numbers, one passport number per line.

Output

Output the total number of stolen passports in the list of M passports.

Constraints

  • Time Limit: 3s
  • Memory Limit: 64MB
  • 1≤N≤100,000
  • 1≤M≤100,000
  • Passport numbers are alphanumeric (combination of alphabetic and numeric characters) and are of length at most 15

Problem Source: UTP Online Judge

Let’s try solving this problem using hash table. Hash table is a data structure that can map keys to value.

For example, you have 9999 students’ ID with code from 0001 to 9999 and store it in an array, A[]. Everyday, teachers will scan their ID if they’re present and you will receive an array of student list, say Present, like {3478,0034,3203,0120,...,2840,0001}. If the principal wants you to print a list of students that are absent, your code would probably be:

Pseudocode

for i from 0001 to 9999
    if not i in Present
        print i

This is simple and straightforward but the time complexity is not really good. First, you have to go through every element from 0001 to 9999, n. Then, to check if the element is in the list Present, you have to go through every element in that list, m. So, your time complexity will be O(nm).

For hash table, the idea is as below:

Pseudocode

for i in Present
    A[i] = 1

for i from 0001 to 9999
    if A[i] = 0
        print i
    

It may look longer than the previous code, but it is much more efficient. First, we go through m steps to record student who is present with 1 in their corresponding index. Then, we scan through A[] to print out the index of students with data 0, which means they are absent. This method results in time complexity of O(n+m) only.

Now, get back to the actual problem: Passport Checking. We first look at the overall solution involving hash table (unordered_map in C++):

C++

#include <iostream>
#include <string>
#include <unordered_map>
 
using namespace std;
 
int main() {
	int N;
	cin >> N;
 
	unordered_map<string, int> stolen_map;
 
	unordered_map<string, int>::hasher fn = stolen_map.hash_function();
 
	for (int i=0; i<N; i++){
		string stolen;
		cin >> stolen;
 
		stolen_map[stolen] = fn(stolen);
	}
 
	int M;
	cin >> M;
 
	int cnt = 0;
	for (int i=0; i<M; i++){
		string target;
		cin >> target;
 
		unordered_map<string, int>::const_iterator got = stolen_map.find(target);
		if (got != stolen_map.end()) cnt++;
	}
 
	cout << cnt << endl;
 
	return 0;
}

Line 3:

#include <unordered_map>;

This allows us to use functions in unordered_map.

Line 11:

unordered_map<string, int> stolen_map;

Create a hash table to map string (stolen passports) to int.

Line 13:

unordered_map<string, int>::hasher fn = stolen_map.hash_function();

Create a hash function (the method), fn,to convert the string (stolen passports) to int and store it in stolen_map.

Line 19:

stolen_map[stolen] = fn(stolen);

The stolen passport, type string, is store with their value after entering the hash function fn.

Line 30:

unordered_map<string, int>::const_iterator got = stolen_map.find(target);

To call for the target value.

Line 31:

if (got != stolen_map.end())

If the target value is searched.

Advertisements
UOJ Passport Checking : Hash Table Method

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s