CODEWITHSUNDEEP
javaperformancealgorithm
Tad
Tad

Reputation: 838

Checking whether intersection of two lists is valid, returning intersection itself not necessary

I have two lists ( List1 and List2) containing objects of type Column. Column has two private variables - Name and Type. The intersection of List1 and List2 is done by Column's name. For example:

List1 = { Column (name = "A", type = "STRING"), Column (name = "B", type = "INT") }
List2 = { Column (name = "A", type = "STRING"), Column (name = "D", type = "INT") }

then intersection of List1 and List2 = { Column (name = "A", type = "STRING") }

How can I efficiently write code in Java 8 without using a double for loop (O(n^2)) to check whether an intersection is valid (if it is not valid, then I would like to know the Column names along with conflicting types, if it is valid, just returning True is good enough for me - I don't need the intersection itself). A valid intersection is defined as follows: the columns in the intersection done by comparing the field name, must have the same type. For example, the following is invalid:

List1 = { Column (name = "A", type = "STRING"), Column (name = "B", type = "INT") }
List2 = { Column (name = "A", type = "INT"), Column (name = "D", type = "INT") }

then an invalid intersection of List1 and List2 = { Column (name = "A", type = "STRING") } since the types do not match. Another way of thinking about it is Given a list of columns in a List1 and a list of columns in List2, I would like to check whether columns which are in both List1 and List2 have the same type.

First attempt:

 for (final Column newColumn : newMySQLTableMetaData.getColumns()) {
            for (final Column originalColumn : originalMySQLTableMetaData.getColumns()) {
                if (newColumn.getName().equals(originalColumn.getName())) {
                    if (!newColumn.getType().equals(ColumnTypeConverter.toLogicalColumnType(originalColumn.getType()))) {
                        throw new UploadException("The column types have a mismatch. Original column" +
                                " named " + originalColumn.getName() + " a type of " + originalColumn.getType().toString() + " " +
                                "while new column with the same name has a type of " + newColumn.getType().toString());
                    }
                }
            }
        }

Upvotes: 1

Views: 146

Answers (1)

maaartinus
maaartinus

Reputation: 46422

Put all elements from list1 into a HashMap index by name. Go throw the second list and look if there's a matching column from the first one (O(1) per element). If so, check for conflict.

private List<String> conflictList = new ArrayList<String>();

private final Map<String, Column> map = new HashMap<>();
for (Column c1: list1) map.put(c1.name, c1);
for (Column c2: list2) {
    Column c1 = map.put(c2.name, c2);
    if (c1==null) continue;
    if (c1.type.equals(c2.type)) continue;
    conflictList.add(c1); // or add the name only or both elements or whatever
}

If conflictList is empty, then you've won. If you don't care about the details, return early instead of processing the remaining elements.

Upvotes: 2

Related Questions