Judging Troubles

Introduction

This problem asks you to compare two lists and return the number of common entries

Solutions

HashMap

Idea

Create a hashmap of strings to number of appearances of that string. Read through the first list, incrementing the count for each string found. Scan through the second list. For each string in the map with a positive count, add 1 to the total match count, and subtract 1 from the value in the hashmap.

Runtime

• n

Code

Solution - Java

import java.util.*;
public class j {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new j().go();
	}
	private void go() {
		int n=in.nextInt();
		HashMap<String,Integer> dom=new HashMap<String,Integer>();
		HashMap<String, Integer> kat=new HashMap<String,Integer>();
		for(int i=0;i<n;i++){
			String s=in.next();
			if(!dom.containsKey(s))dom.put(s, 0);
			dom.put(s, dom.get(s)+1);
		}
		for(int i=0;i<n;i++){
			String s=in.next();
			if(!kat.containsKey(s))kat.put(s, 0);
			kat.put(s, kat.get(s)+1);
		}
		int ans=0;
		for(String s:dom.keySet())if(kat.containsKey(s))ans+=Math.min(dom.get(s), kat.get(s));
				System.out.println(ans);
	}
}

Sorting

Idea

Sort the two lists. Start at the head of each list. If the two match, increment the total match count. If they don't, increment the index of the list with the word that appears first alphabetically.

Runtime

n*log(n)