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.

My source code can be downloaded here.

  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) {
 34             emails[i] = new Email(randomToAddresses.get(random.nextInt(4)), fromAddress, "Message-" + 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.
 54             String toAddress = email.getToAddress();
 55             int toAddressCount = 1;
 56             if (toAddressCountMap.containsKey(toAddress)) {
 57                 toAddressCount = toAddressCountMap.get(toAddress) + 1;
 58             }
 59             toAddressCountMap.put(toAddress, toAddressCount);
 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>();
 65                 emailBatches.add(emailBatch);
 66             } else {
 67                 // Use the existing batch and add this email to the end of it.
 68                 emailBatch = emailBatches.get(toAddressCount - 1);
 69             }
 70             emailBatch.add(email);
 71         }
 72
 73         return emailBatches;
 74     }
 75
 76     private static class Email {
 77         private String toAddress;
 78         private String fromAddress;
 79         private String message;
 80
 81         public Email(String toAddress, String fromAddress, String message) {
 82             this.fromAddress = fromAddress;
 83             this.message = message;
 84             this.toAddress = toAddress;
 85         }
 86
 87         @Override
 88         public String toString() {
 89             final StringBuilder sb = new StringBuilder();
 90             sb.append("Email");
 91             sb.append("{fromAddress='").append(fromAddress).append('\'');
 92             sb.append(", toAddress='").append(toAddress).append('\'');
 93             sb.append(", message='").append(message).append('\'');
 94             sb.append('}');
 95             return sb.toString();
 96         }
 97
 98         public String getFromAddress() {
 99             return fromAddress;
100         }
101
102         public void setFromAddress(String fromAddress) {
103             this.fromAddress = fromAddress;
104         }
105
106         public String getMessage() {
107             return message;
108         }
109
110         public void setMessage(String message) {
111             this.message = message;
112         }
113
114         public String getToAddress() {
115             return toAddress;
116         }
117
118         public void setToAddress(String toAddress) {
119             this.toAddress = toAddress;
120         }
121     }
122 }