C++ solution with hash tree (Merkle tree)
Suprisingly this idea comes not from any algorithm books, but from a system design interview book where they talk about using hash tree to efficiently sync data
Suprisingly this idea comes not from any algorithm books, but from a system design interview book where they talk about using hash tree to efficiently sync databases. They use has tree to find which data block differs between databases and sync only those data blocks, instead of updating the entire database.\n\nIt is the first time I\'ve ever wrote a hash tree. There is no way I could have finished this in time during the competition\nand I do not handle collisions. It works for now but in the future when more test cases are included then my hash won\'t work anymore.\n\n\n\n    class Solution {\n    public:\n\n    typedef long long ll;\n    const ll POWER = 31;\n    const ll MOD = 1000000007;\n    struct Node{\n        vector<string> path;\n        vector<Node*> fChildren;\n        int id = -1;\n        int nNodes = 0;\n        ll hashChildren = 0;\n    };\n\t\n    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {\n        sort(paths.begin(), paths.end()); // e.g. prevent ["a", "x", "y"] from appearing before ["a", "x"]\n        unordered_map<ll, Node*> hashToNodes;\n        auto root = new Node;\n        for(int i = 0; i < paths.size(); ++i) {\n            ll radix = 1;\n            ll hashParent = 0, hash;\n            \n            // hash of parent\'s path (excluding itself)\n            for(int j = 0; j < paths[i].size() - 1; ++j) \n                for(auto ch : paths[i][j]) \n                    hashParent = (hashParent*POWER + (ch - \'a\' + 1)) % MOD; \n            \n            // hash if the entire path (including itself)\n            hash = hashParent;\n            for(auto ch : paths[i].back())\n                hash = (hash*POWER + (ch - \'a\' + 1)) % MOD; \n            \n            auto node = new Node{paths[i]};\n            node -> id = i;\n            // find parent node\n            if(hashToNodes.find(hashParent) != hashToNodes.end()) {\n                hashToNodes[hashParent] -> fChildren.push_back(node);\n            } else root -> fChildren.push_back(node); // if parent node is not found, append to root\n            \n            // save node tables\n            hashToNodes[hash] = node;\n        }\n        \n        // fill the "hashChildren" field of each node\n        fillHash(root);\n        root = removeNode(root);\n        vector<vector<string>> ans;\n        getElements(root, ans);\n        return ans;\n    }\n    \n    void getElements(Node* node, vector<vector<string>>& ans) {\n        if(node -> path.size() > 0)  ans.push_back(node -> path);\n        for(auto child : node -> fChildren)\n            if(child) getElements(child, ans);\n    }\n    \n    ll fillHash(Node* node) {\n        ll power = 1;\n        ll hash = 0;\n        node -> nNodes = 1;\n        for(auto child : node -> fChildren) {\n            ll temp = fillHash(child);\n            hash = (hash + temp*power) % MOD;\n            node -> nNodes += child -> nNodes;\n            power = (power*powMod(POWER, child -> nNodes)) % MOD;\n        }\n        // sum of hashes from all children\n        node -> hashChildren = hash;\n        hashCount[hash]++;\n        \n        // sum of hashes from all children + itself\n        if(node -> path.size() > 0)\n            for(auto& ch : node -> path.back())\n                hash = (hash*POWER + (ch - \'a\' + 1)) % MOD;\n        return hash;\n    }\n    \n    Node* removeNode(Node *node) {\n        if(!node) return nullptr;\n        // remove nodes where the hash appears more than once\n        // node -> hashChildren > 0 because all leaves has hashChildren = 0. Don\'t want to remove that\n        if(node -> hashChildren > 0 && hashCount[node -> hashChildren] > 1) return nullptr;\n        for(int i = 0; i < node -> fChildren.size(); ++i) {\n            node -> fChildren[i] = removeNode(node -> fChildren[i]);\n        }\n        return node;\n    }\n    \n    ll powMod(int pow, int ind) {\n        if(ind == 0) return 1;\n        if(ind == 1) return pow;\n        ll res = powMod(pow, ind/2) % MOD;\n        if(ind % 2 == 0) return (res*res) % MOD;\n        else return (((res*res) % MOD)*pow) % MOD;\n    }\n    \n    unordered_map<ll, int> hashCount;\n    };\n
[]