42-problems first problem

shekhargulati · shekhargulati · commit 8ea74727616d · 2016-03-01T23:14:00.000+05:30
diff --git a/java8/src/main/java/com/shekhargulati/fortytwo_problems/Problem01.java b/java8/src/main/java/com/shekhargulati/fortytwo_problems/Problem01.java
@@ -0,0 +1,36 @@
+package com.shekhargulati.fortytwo_problems;
+
+import java.util.AbstractMap.SimpleEntry;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * Taken an input a sequence of 2n real numbers.
+ * Design an O(nlogn) algorithm that partitions the numbers into n pairs,
+ * with the property that the partition minimizes the sum of maximum sum of a pair.
+ */
+public class Problem01 {
+
+    public static List<SimpleEntry<Integer, Integer>> pairs(int[] numbers) {
+        /*
+        Algorithm:
+        1. Sort the numbers
+        2. Iterate over half the list and put first number and last in a pair
+
+        Other algorithm feasible
+        1. Sort numbers
+        2. Create reverse numbers
+        3. Take first half of zip of numbers and reverse
+        let l = sort [1,9,5,3]
+        let r = reverse l
+        take (length l `div` 2) (zip l r)
+         */
+        Arrays.sort(numbers);
+        List<SimpleEntry<Integer, Integer>> pairs = new ArrayList<>();
+        for (int i = 0; i < numbers.length / 2; i++) {
+            pairs.add(new SimpleEntry<>(numbers[i], numbers[(numbers.length - i) - 1]));
+        }
+        return pairs;
+    }
+}
diff --git a/java8/src/test/java/com/shekhargulati/fortytwo_problems/Problem01Test.java b/java8/src/test/java/com/shekhargulati/fortytwo_problems/Problem01Test.java
@@ -0,0 +1,18 @@
+package com.shekhargulati.fortytwo_problems;
+
+import org.junit.Test;
+
+import java.util.AbstractMap.SimpleEntry;
+import java.util.List;
+
+import static org.hamcrest.collection.IsIterableContainingInOrder.contains;
+import static org.junit.Assert.assertThat;
+
+public class Problem01Test {
+
+    @Test
+    public void shouldCreatePairsByMinOfMaximumSumOfPairs() throws Exception {
+        List<SimpleEntry<Integer, Integer>> pairs = Problem01.pairs(new int[]{1, 9, 3, 5});
+        assertThat(pairs, contains(new SimpleEntry<>(1, 9), new SimpleEntry<>(3, 5)));
+    }
+}
