BubbleSort & pair=sum of given number algorithms

melmedany · melmedany · commit 3c5f32c241e3 · 2018-01-07T20:18:09.000+02:00
diff --git a/src/main/java/BubbleSort.java b/src/main/java/BubbleSort.java
@@ -0,0 +1,34 @@
+
+/**
+ * @author medany
+ */
+
+/*
+ * (Best case) O(n) if the array is already sorted, that means no swap occurred.
+ * 
+ * (Worst case) O(n^2) if the array is already sorted but in descending order.
+ */
+
+public class BubbleSort {
+
+	public int[] solve(int[] a) {
+
+		int[] result = new int[3];
+		int temp;
+		for (int i = 0; i < a.length; i++) {
+			for (int j = 0; j < a.length - 1; j++) {
+				if (a[j] > a[j + 1]) {
+					temp = a[j];
+					a[j] = a[j + 1];
+					a[j + 1] = temp;
+					result[0] += 1;
+				}
+			}
+		}
+		result[1] = a[0];
+		result[2] = a[a.length - 1];
+
+		return result;
+	}
+
+}
diff --git a/src/main/java/IceCreamParlor.java b/src/main/java/IceCreamParlor.java
@@ -0,0 +1,35 @@
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * @author medany
+ */
+
+/*
+ * Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they pool
+ * together money dollars for ice cream. On any given day, the parlor offers a
+ * line of n flavors. Each flavor, i, is numbered sequentially with a unique ID
+ * number from 1 to n and has a cost, cost i, associated with it.
+ * 
+ * Given the value of money and the cost of each flavor for t trips to the Ice
+ * Cream Parlor, help Sunny and Johnny choose two distinct flavors such that
+ * they spend their entire pool of money during each visit. For each trip to the
+ * parlor, print the ID numbers for the two types of ice cream that Sunny and
+ * Johnny purchase as two space-separated integers on a new line. You must print
+ * the smaller ID first and the larger ID second.
+ */
+
+public class IceCreamParlor {
+
+	public int[] solve(int money, int[] flavors) {
+		Map<Integer, Integer> hash = new HashMap<>();
+		for (int i = 0; i < flavors.length; i++) {
+			int complement = money - flavors[i];
+			if (hash.containsKey(complement)) {
+				return new int[] { hash.get(complement) + 1, i + 1 };
+			}
+			hash.put(flavors[i], i);
+		}
+		return new int[] {};
+	}
+}
diff --git a/test/main/java/BubbleSortTest.java b/test/main/java/BubbleSortTest.java
@@ -0,0 +1,31 @@
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * @author medany
+ */
+
+public class BubbleSortTest {
+
+	private BubbleSort alg = new BubbleSort();
+	private int[] actual, expected;
+
+	@Test
+	public void Test_1() {
+
+		actual = alg.solve(new int[] { 1, 2, 3 });
+		expected = new int[] { 0, 1, 3 };
+
+		Assert.assertArrayEquals(expected, actual);
+	}
+
+	@Test
+	public void Test_2() {
+
+		actual = alg.solve(new int[] { 3, 2, 1 });
+		expected = new int[] { 3, 1, 3 };
+
+		Assert.assertArrayEquals(expected, actual);
+	}
+
+}
diff --git a/test/main/java/IceCreamParlorTest.java b/test/main/java/IceCreamParlorTest.java
@@ -0,0 +1,39 @@
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * @author medany
+ */
+
+public class IceCreamParlorTest {
+
+	private static IceCreamParlor alg = new IceCreamParlor();
+	private int[] actual, expected;
+
+	@Test
+	public void Test_1() {
+
+		actual = alg.solve(4, new int[] { 1, 4, 5, 3, 2 });
+		expected = new int[] { 1, 4 };
+
+		Assert.assertArrayEquals(expected, actual);
+	}
+
+	@Test
+	public void Test_2() {
+
+		actual = alg.solve(4, new int[] { 2, 2, 4, 3 });
+		expected = new int[] { 1, 2 };
+
+		Assert.assertArrayEquals(expected, actual);
+	}
+
+	@Test
+	public void Test_3() {
+
+		actual = alg.solve(16, new int[] { 2, 7, 8, 5, 8, 3, 8 });
+		expected = new int[] { 3, 5 };
+
+		Assert.assertArrayEquals(expected, actual);
+	}
+}
