summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2019-03-03 21:25:10 -0600
committerHaidong Ji2019-03-03 21:25:10 -0600
commitbf3c1de9f72097bc5a6937344f9402854ce18abc (patch)
tree78bfbed03d3fc8578b40a1a503bc0434a54594b4
parent3a6cbab3d53e5b04a6ea10df7854e4f3bce4f3a3 (diff)
Merging tables done!
Another interesting problem to solve. I gained a much better understanding of disjoint sets (aka Union/Find) through the coding challenge. A few takeaways: 1. Writing test cases is so important. I can sink my teeth into it and have something concrete to work on, instead of wasting time beating around the bush; 2. Modify starter code to make it testable, if it's not easy to test to begin with; 3. Get started early, so I can use my "sleep on it" technique. It really improves understanding! 4. I'm slightly bothered by the fact that I don't have a test case to catch the issue with grader test case 8. I looked at the code and added line 61 which enabled me to pass the grader.
-rw-r--r--src/main/MergingTables.java139
-rw-r--r--src/test/MergingTablesTest.java83
2 files changed, 222 insertions, 0 deletions
diff --git a/src/main/MergingTables.java b/src/main/MergingTables.java
new file mode 100644
index 0000000..bf0e337
--- /dev/null
+++ b/src/main/MergingTables.java
@@ -0,0 +1,139 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.io.OutputStream;
+import java.io.PrintWriter;
+import java.util.Locale;
+import java.util.StringTokenizer;
+
+public class MergingTables {
+ private final InputReader reader;
+ private final OutputWriter writer;
+
+ int maximumNumberOfRows = -1;
+ int[] parent;
+ int[] rank;
+ Table[] tables;
+
+ MergingTables(InputReader reader, OutputWriter writer) {
+ this.reader = reader;
+ this.writer = writer;
+ }
+
+ public static void main(String[] args) {
+ InputReader reader = new InputReader(System.in);
+ OutputWriter writer = new OutputWriter(System.out);
+ new MergingTables(reader, writer).run();
+ writer.writer.flush();
+ }
+
+ static class Table {
+ Table setID;
+ int numberOfRows;
+
+ Table(int numberOfRows) {
+ this.numberOfRows = numberOfRows;
+ setID = this;
+ }
+
+ }
+
+ private int find(int i) {
+ if (i != parent[i])
+ parent[i] = find(parent[i]);
+ return parent[i];
+ }
+
+ void merge(int destination, int source) {
+ Table realDestination = tables[find(destination)];
+ Table realSource = tables[find(source)];
+ if (realDestination == realSource) {
+ return;
+ }
+ maximumNumberOfRows = Math.max(maximumNumberOfRows, realDestination.setID.numberOfRows + realSource.setID.numberOfRows);
+ realDestination.numberOfRows = realDestination.setID.numberOfRows + realSource.setID.numberOfRows;
+ realSource.numberOfRows = 0;
+ realSource.setID = realDestination;
+ // The code below fixed the issue with test case 8 from the grader.
+ // My code then passed all tests. I'm slightly bothered that I don't
+ // have a test case to capture it.
+ realDestination.setID = realDestination;
+ union(destination, source);
+ }
+
+ private void union(int destination, int source) {
+ int destination_id = find(destination);
+ int source_id = find(source);
+ if (destination_id == source_id)
+ return;
+ if (rank[destination_id] > rank[source_id])
+ parent[source_id] = destination_id;
+ else {
+ parent[destination_id] = source_id;
+ if (rank[destination_id] == rank[source_id])
+ rank[source_id] = rank[source_id] + 1;
+ }
+ }
+
+ private void run() {
+ int n = reader.nextInt();
+ int m = reader.nextInt();
+ parent = new int[n];
+ rank = new int[n];
+ tables = new Table[n];
+ for (int i = 0; i < n; i++) {
+ int numberOfRows = reader.nextInt();
+ tables[i] = new Table(numberOfRows);
+ parent[i] = i;
+ rank[i] = 0;
+ maximumNumberOfRows = Math.max(maximumNumberOfRows, numberOfRows);
+ }
+ for (int i = 0; i < m; i++) {
+ int destination = reader.nextInt() - 1;
+ int source = reader.nextInt() - 1;
+ merge(destination, source);
+ writer.printf("%d\n", maximumNumberOfRows);
+ }
+ }
+
+
+ static class InputReader {
+ BufferedReader reader;
+ StringTokenizer tokenizer;
+
+ InputReader(InputStream stream) {
+ reader = new BufferedReader(new InputStreamReader(stream), 32768);
+ tokenizer = null;
+ }
+
+ String next() {
+ while (tokenizer == null || !tokenizer.hasMoreTokens()) {
+ try {
+ tokenizer = new StringTokenizer(reader.readLine());
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+ return tokenizer.nextToken();
+ }
+
+ int nextInt() {
+ return Integer.parseInt(next());
+ }
+
+ }
+
+ static class OutputWriter {
+ PrintWriter writer;
+
+ OutputWriter(OutputStream stream) {
+ writer = new PrintWriter(stream);
+ }
+
+ void printf(String format, Object... args) {
+ writer.print(String.format(Locale.ENGLISH, format, args));
+ }
+ }
+}
+
diff --git a/src/test/MergingTablesTest.java b/src/test/MergingTablesTest.java
new file mode 100644
index 0000000..fcb5829
--- /dev/null
+++ b/src/test/MergingTablesTest.java
@@ -0,0 +1,83 @@
+import org.junit.jupiter.api.Test;
+
+import java.io.*;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class MergingTablesTest {
+ @Test
+ void test() {
+ MergingTables.InputReader reader = new MergingTables.InputReader(System.in);
+ MergingTables.OutputWriter writer = new MergingTables.OutputWriter(System.out);
+ MergingTables mergingTables = new MergingTables(reader, writer);
+ mergingTables.tables = new MergingTables.Table[5];
+
+ MergingTables.Table t0 = new MergingTables.Table(1);
+ MergingTables.Table t1 = new MergingTables.Table(1);
+ MergingTables.Table t2 = new MergingTables.Table(1);
+ MergingTables.Table t3 = new MergingTables.Table(1);
+ MergingTables.Table t4 = new MergingTables.Table(1);
+
+ mergingTables.tables[0] = t0;
+ mergingTables.tables[1] = t1;
+ mergingTables.tables[2] = t2;
+ mergingTables.tables[3] = t3;
+ mergingTables.tables[4] = t4;
+ mergingTables.maximumNumberOfRows = 1;
+ mergingTables.rank = new int[]{0, 0, 0, 0, 0};
+ mergingTables.parent = new int[]{0, 1, 2, 3, 4};
+
+ mergingTables.merge(2, 4);
+ assertEquals(2, mergingTables.maximumNumberOfRows);
+
+ mergingTables.merge(1, 3);
+ assertEquals(2, mergingTables.maximumNumberOfRows);
+
+ mergingTables.merge(0, 3);
+ assertEquals(3, mergingTables.maximumNumberOfRows);
+
+ mergingTables.merge(4, 3);
+ assertEquals(5, mergingTables.maximumNumberOfRows);
+
+ mergingTables.merge(4, 2);
+ assertEquals(5, mergingTables.maximumNumberOfRows);
+ }
+
+ @Test
+ void test1() {
+ MergingTables.InputReader reader = new MergingTables.InputReader(System.in);
+ MergingTables.OutputWriter writer = new MergingTables.OutputWriter(System.out);
+ MergingTables mergingTables = new MergingTables(reader, writer);
+ mergingTables.tables = new MergingTables.Table[6];
+
+ MergingTables.Table t0 = new MergingTables.Table(10);
+ MergingTables.Table t1 = new MergingTables.Table(0);
+ MergingTables.Table t2 = new MergingTables.Table(5);
+ MergingTables.Table t3 = new MergingTables.Table(0);
+ MergingTables.Table t4 = new MergingTables.Table(3);
+ MergingTables.Table t5 = new MergingTables.Table(3);
+
+ mergingTables.tables[0] = t0;
+ mergingTables.tables[1] = t1;
+ mergingTables.tables[2] = t2;
+ mergingTables.tables[3] = t3;
+ mergingTables.tables[4] = t4;
+ mergingTables.tables[5] = t5;
+ mergingTables.maximumNumberOfRows = 10;
+ mergingTables.rank = new int[]{0, 0, 0, 0, 0, 0};
+ mergingTables.parent = new int[]{0, 1, 2, 3, 4, 5};
+
+ mergingTables.merge(5, 5);
+ assertEquals(10, mergingTables.maximumNumberOfRows);
+
+ mergingTables.merge(5, 4);
+ assertEquals(10, mergingTables.maximumNumberOfRows);
+
+ mergingTables.merge(4, 3);
+ assertEquals(10, mergingTables.maximumNumberOfRows);
+
+ mergingTables.merge(3, 2);
+ assertEquals(11, mergingTables.maximumNumberOfRows);
+ }
+
+} \ No newline at end of file