I was asked this question on a Phone Interview, I was not able to complete it as I struggled a little bit in order to figure it out how to compare the nested elements, since elements or list wont be of the same type, I was able to figure it out a possible solution after the interview.
Problem Statement: Nested Set Equality Checker
You are given two sets, list1 and list2, each represented as a list. These sets can contain words (strings) or nested sets (lists of words or other sets). Your task is to implement a function areSetsEqual that checks if the two sets are equal, considering their content and structure.
Equality Definition:
Two sets are considered equal if they contain the same string elements, regardless of order.
Sets can contain nested sets.
Possible Solution
Just iterate and sort based on lexical order and call the function recursively whenever we see a list, when we use toString() on Java over a list it would be printed as a flat string which allows to order while backtracking (I struggled on this because I was using java and I though toString method over a list would not work very well as I could get printed memory addresses), at the end, just compare the two generated lists.
public class ListEqualityChecker {
public static boolean areListsEqual(List<Object> list1, List<Object> list2) {
return setEquals(list1, list2);
}
public static boolean setEquals(List<Object> set1, List<Object> set2) {
if (set1.size() != set2.size()) {
return false; // Different sizes
}
List<Object> normalizedSet1 = normalizeList(set1);
List<Object> normalizedSet2 = normalizeList(set2);
return normalizedSet1.equals(normalizedSet2);
}
private static List<Object> normalizeList(List<Object> list) {
List<Object> normalized = new ArrayList<>();
for (Object obj : list) {
if (obj instanceof List) {
normalized.add(normalizeList((List<Object>) obj));
} else {
normalized.add(obj);
}
}
normalized.sort(Comparator.comparing(Object::toString));
return normalized;
}
public static void main(String[] args) {
List<Object> set1 = Arrays.asList("apple", Arrays.asList("banana", "cherry"));
List<Object> set2 = Arrays.asList(Arrays.asList("cherry", "apple"), "banana");
List<Object> set3 = Arrays.asList("banana", Arrays.asList("cherry", "apple"));
List<Object> set4 = Arrays.asList("false", Arrays.asList("cherry", "apple", Arrays.asList("cherry", "apple"), Arrays.asList("word1", "word2")), "cherry");
List<Object> set5 = Arrays.asList("false", "cherry", Arrays.asList("cherry", "apple", Arrays.asList("word1", "word2"), Arrays.asList("apple", "cherry")));
;
System.out.println(setEquals(set1, set2)); // false
System.out.println(setEquals(set2, set3)); // true
System.out.println(setEquals(set4, set5)); // true
}
}