import java.util.*; /** * The problem: given a collection of email messages, write an algorithm that computes the minimum number of email * batches such that no single batch contains a message addressed to the same recipient more than once. *

* Example input: {Email1->a@example.com, Email2->b@example.com, Email3->a@example.com} *

* Expected output: {{Email1->a@example.com, Email2->b@example.com}, {Email3->a@example.com}} *

* The solution: use a map to count the number of times a "to address" occurs in the input. Use the count as an index * into a list of resulting email batches. * * @author Chip Killmar */ public class EmailBatches { private static final Random random = new Random(); private static final String fromAddress = "test@example.com"; private static final List randomToAddresses = Arrays.asList("a@example.com", "b@example.com", "c@example.com", "d@example.com"); public static void main(String[] args) { // Create some test data. List emails = Arrays.asList(createRandomEmails(4)); System.out.println("Input=" + emails); System.out.println("Output=" + createEmailBatches(emails)); } private static Email[] createRandomEmails(int numberOfEmails) { Email[] emails = new Email[numberOfEmails]; for (int i = 0; i < emails.length; ++i) { emails[i] = new Email(randomToAddresses.get(random.nextInt(4)), fromAddress, "Message-" + i); } return emails; } /** * An O(n) algorithm that uses a map to keep track of how many times an email to-address has been seen. This count * is then used as an index into a list of email batches. * * @param emails An input collection of emails. * @return The minimum number of email batches such that no single batch contains a message addressed to the same * recipient (to-address) more than once. */ private static Collection> createEmailBatches(Collection emails) { List> emailBatches = new ArrayList>(); Map toAddressCountMap = new HashMap(); for (Email email : emails) { // Use a map to keep track of how many times we've seen a to-address. String toAddress = email.getToAddress(); int toAddressCount = 1; if (toAddressCountMap.containsKey(toAddress)) { toAddressCount = toAddressCountMap.get(toAddress) + 1; } toAddressCountMap.put(toAddress, toAddressCount); Collection emailBatch; if (emailBatches.size() < toAddressCount) { // We need a new batch to put this email into. emailBatch = new ArrayList(); emailBatches.add(emailBatch); } else { // Use the existing batch and add this email to the end of it. emailBatch = emailBatches.get(toAddressCount - 1); } emailBatch.add(email); } return emailBatches; } private static class Email { private String toAddress; private String fromAddress; private String message; public Email(String toAddress, String fromAddress, String message) { this.fromAddress = fromAddress; this.message = message; this.toAddress = toAddress; } @Override public String toString() { final StringBuilder sb = new StringBuilder(); sb.append("Email"); sb.append("{fromAddress='").append(fromAddress).append('\''); sb.append(", toAddress='").append(toAddress).append('\''); sb.append(", message='").append(message).append('\''); sb.append('}'); return sb.toString(); } public String getFromAddress() { return fromAddress; } public void setFromAddress(String fromAddress) { this.fromAddress = fromAddress; } public String getMessage() { return message; } public void setMessage(String message) { this.message = message; } public String getToAddress() { return toAddress; } public void setToAddress(String toAddress) { this.toAddress = toAddress; } } }