> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/hard/sparse-similarity.md).

# Sparse Similarity

**17.26 Sparse Similarity:** The similarity of two documents (each with distinct words) is defined to be the size of the intersection divided by the size of the union. For example, if the documents consist of integers, the similarity of {1, 5, 3} and {1, 7, 2, 3} is e. 4, because the intersection has size 2 and the union has size 5. We have a long list of documents (with distinct values and each with an associated ID) where the similarity is believed to be "sparse:'That is, any two arbitrarily selected documents are very likely to have similarity O. Design an algorithm that returns a list of pairs of document IDs and the associated similarity. Print only the pairs with similarity greater than O. Empty documents should not be printed at all. For simplicity, you may assume each document is represented as an array of distinct integers.

```
EXAMPLE
Input:
13: {14, 15, 100, 9, 3}
16: {32, 1, 9, 3, 5}
19: {15, 29, 2, 6, 8, 7}
24: {7, l0}

Output:
ID1, ID2 SIMILARITY
13, 19 0.1
13, 16 0.25
19, 24 0.14285714285714285
```

**Complexity:** O(n^2) time and O(n) space\
**The Idea:** Pretty straightforward. It is just a matter of unloading the combinations and calculating the intersection and union between them. No fancy math, but I did want to emphasize the use of the reserve keyword to ensure proper time complexity and cache hit.

```cpp
unordered_set<int> calc_union(const vector<int> &one, const vector<int> &two) {
    unordered_set<int> unioned;
    unioned.reserve(max(one.size(), two.size()));
    for (int i : one) unioned.insert(i);
    for (int i : two) unioned.insert(i);
    return unioned;
}

unordered_set<int> calc_inters(const vector<int> &one, const vector<int> &two) {

    unordered_set<int> inters, set2;
    inters.reserve(max(one.size(), two.size()));
    set2.reserve(two.size());

    for (int i : two) set2.insert(i);

    for (int i : one) 
        if (set2.find(i) != set2.end()) 
            inters.insert(i);

    return inters;
}

long long factorial(int n) {
    long long prod = 1;
    for (int i = 2; i <= n; i++) {
        prod *= i;
    }
    return prod;
}

int combination(int n, int chose) {
    //nCr = n! / r! (n - r)!
    assert(n >= chose);
    return factorial(n) / (factorial(chose) * factorial(n - chose));
}

vector<pair<pair<int, int>, double>> calc_doc_sim(const vector<pair<int, vector<int>>> &doc_data) {

    vector<pair<pair<int, int>, double>> pair_wise_similiarity;
    pair_wise_similiarity.reserve(combination(doc_data.size(), 2));

    double similiarity = 0;
    for (int i = 0; i < doc_data.size(); i++) {
        for (int j = i + 1; j < doc_data.size(); j++) {
            double union_size = calc_union(doc_data.at(i).second, doc_data.at(j).second).size();
            double inters_size = calc_inters(doc_data.at(i).second, doc_data.at(j).second).size();

            if (union_size != 0)
                similiarity = inters_size / union_size;
            else similiarity = 0;

            pair_wise_similiarity.push_back({ { doc_data.at(i).first, doc_data.at(j).first }, similiarity });
        }
    }

    return pair_wise_similiarity;
}

int main()
{
    vector<pair<int,vector<int>>> document_data = {
        { 13, {14, 15, 100, 9, 3} },
        { 16, {32, 1, 9, 3, 5} },
        { 19, {15, 29, 2, 6, 8, 7}},
        { 24, {7, 10}}
    };

    vector<pair<pair<int, int>, double>> doc_sim = calc_doc_sim(document_data);
    for (auto i : doc_sim) {
        if (i.second != 0)
            cout << i.first.first << ", " << i.first.second << ": " << i.second << endl;
    }

}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/hard/sparse-similarity.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.