Pinterest | Phone Screen | Backend Engineer

Phone Screen

Questions: 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 thought 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
    }
}