amazon.js

// Find the first string in a list that is unique

// ['abc', 'd', 'j', 'abc', 'j'] => 'd'


// time complexity O(n^2) and space complexity is constant O(1)
const bruteForceSolution = strings => {
    const n = strings.length;

    for (let i = 0; i < n && !result; i++) {
        const curr = strings[i];

        let found = true;
        for (let j = 0; j < n; j++) {
            if (i === j) continue;
            if (curr === strings[j]) {
                found = false;
                break;
            }
        }

        if (found) return curr;
    }

    return curr;
}

// Optimal solution O(n) time complexity and O(n) space complexity
const solution1 = strings => {
    const seen = new Set();
    const possible_results = new Set();

    for (let i = 0; i < strings.length; i++) {
        const curr = strings[i];
        if (seen.has(curr) && possible_results.has(curr)) {
            possible_results.delete(curr);
        } else if (!seen.has(curr)) {
            possible_results.add(curr);
        }
        seen.add(curr);
    }

    for (let result of possible_results) {
        return result;
    }

    return false;
};

// Functional solution
const iOfSet = (i, set, next = set.values().next(), curr = 0) =>
    next.done ? 
        false : 
        i === curr ? 
            next.value : 
            iOfSet(i, set, next.next(), curr + 1);

const findFirstUniq = strs => strs.length === 0 ? false : strs.reduce(
    ([seen, uniq], str, i, orig) => {
        if (seen.has(str) && uniq.has(str)) {
            uniq.delete(str);
        } else if (!seen.has(str)) {
            uniq.add(str);
        }
        seen.add(str);

        return i === orig.length - 1 ? iOfSet(0, uniq) : [seen, uniq];
    },
    [new Set(), new Set()]
);

console.log(findFirstUniq(['a', 'b', 'a', 'b', 'a', 'c']));
console.log(findFirstUniq(['a', 'b', 'j', 'b', 'a', 'c']));
console.log(findFirstUniq(['a', 'b', 'a', 'k', 'a', 'a']));