Algorithm Problem: Email Batches

The person who told me about this problem ran into a bug in a web service for sending a collection of emails.  If the collection contained more than one email addressed to the same recipient, an error would occur.  He needed to write an algorithm which processes a collection such that it organizes emails into the minimum number of batches needed to successfully use the third-party API.

My solution below runs in worst-case O(n) time, and uses a map to count the number of times a recipient address occurs in the input collection.

1 import java.util.*;
2
3 /**
4  * The problem: given a collection of email messages, write an algorithm that computes the minimum number of email
5  * batches such that no single batch contains a message addressed to the same recipient more than once.
6  * <p/>
7  * Example input: {Email1->a@example.com, Email2->b@example.com, Email3->a@example.com}
8  * <p/>
9  * Expected output: {{Email1->a@example.com, Email2->b@example.com}, {Email3->a@example.com}}
10  * <p/>
11  * The solution: use a map to count the number of times a "to address" occurs in the input.  Use the count as an index
12  * into a list of resulting email batches.
13  *
14  * @author Chip Killmar
15  */
16 public class EmailBatches {
17     private static final Random random = new Random();
18
19     private static final String fromAddress = "test@example.com";
20     private static final List<String> randomToAddresses = Arrays.asList("a@example.com", "b@example.com", "c@example.com", "d@example.com");
21
22     public static void main(String[] args) {
23         // Create some test data.
24         List<Email> emails = Arrays.asList(createRandomEmails(4));
25
26         System.out.println("Input=" + emails);
27
28         System.out.println("Output=" + createEmailBatches(emails));
29     }
30
31     private static Email[] createRandomEmails(int numberOfEmails) {
32         Email[] emails = new Email[numberOfEmails];
33         for (int i = 0; i < emails.length; ++i) {
35         }
36         return emails;
37     }
38
39     /**
40      * An O(n) algorithm that uses a map to keep track of how many times an email to-address has been seen.  This count
41      * is then used as an index into a list of email batches.
42      *
43      * @param emails An input collection of emails.
44      * @return The minimum number of email batches such that no single batch contains a message addressed to the same
45      *         recipient (to-address) more than once.
46      */
47     private static Collection<Collection<Email>> createEmailBatches(Collection<Email> emails) {
48         List<Collection<Email>> emailBatches = new ArrayList<Collection<Email>>();
49
50         Map<String, Integer> toAddressCountMap = new HashMap<String, Integer>();
51
52         for (Email email : emails) {
53             // Use a map to keep track of how many times we've seen a to-address.
58             }
60
61             Collection<Email> emailBatch;
62             if (emailBatches.size() < toAddressCount) {
63                 // We need a new batch to put this email into.
64                 emailBatch = new ArrayList<Email>();
66             } else {
67                 // Use the existing batch and add this email to the end of it.
68                 emailBatch = emailBatches.get(toAddressCount - 1);
69             }
71         }
72
73         return emailBatches;
74     }
75
76     private static class Email {
79         private String message;
80
83             this.message = message;
85         }
86
87         @Override
88         public String toString() {
89             final StringBuilder sb = new StringBuilder();
90             sb.append("Email");
93             sb.append(", message='").append(message).append('\'');
94             sb.append('}');
95             return sb.toString();
96         }
97
100         }
101
104         }
105
106         public String getMessage() {
107             return message;
108         }
109
110         public void setMessage(String message) {
111             this.message = message;
112         }
113