Databricks: Go solution with Binary Search
Intuition\n\nInitial intuition pushed me to use maps with version and a lookup in them, but then I understood that I missed a conditions of how we needed to loo
# Intuition\n\nInitial intuition pushed me to use maps with version and a lookup in them, but then I understood that I missed a conditions of how we needed to look for elements with earlier snapshots.\n\nI tried to implement binary search on map of version, only to realise that I need to do it over an array of versions.\n\nAnd then I was sloppy not to update the element at the top of the array if the version didn\'t change.\n\n# Approach\n\n## Structure\n\nAn array of arrays. Every array stores elemenet values at snapshots.\n\n## Get\n\nBinary search over that array, finding exact version or the first before it.\n\n# Complexity\n- Time complexity:\nSet is $$O(1)$$ and Get is $$O(LogN)$$ for binary search.\n\n- Space complexity:\n$$O(Length * Snapshots Count)$$\n\n# Code\n```\ntype Elem struct {\n    val int\n    version int\n}\n\ntype SnapshotArray struct {\n    data [][]Elem\n    version int\n}\n\nfunc Constructor(length int) SnapshotArray {\n    return SnapshotArray{ make([][]Elem, length), 0 }\n}\n\nfunc (sa *SnapshotArray) Set(index int, val int)  {\n    // Update value if we are at the same version\n    if len(sa.data[index]) > 0 {\n        arr := sa.data[index]\n        if arr[len(arr)-1].version == sa.version {\n            sa.data[index][len(arr)-1].val = val\n            return\n        }\n    }\n    // Add new record if we are at the higher version\n    sa.data[index] = append(sa.data[index], Elem{val, sa.version})\n}\n\nfunc (sa *SnapshotArray) Snap() int {\n    old := sa.version\n    sa.version++\n    return int(old)\n}\n\nfunc (sa *SnapshotArray) Get(index int, snap_id int) int {\n    // Binary search for the exact snap_id or the first below it\n    arr := sa.data[index]\n    l, r := 0, len(arr) - 1\n    for l <= r {\n        m := (l + r) / 2\n        if arr[m].version == snap_id {\n            return arr[m].val\n        } else if arr[m].version < snap_id {\n            l, r = m + 1, r\n        } else {\n            l, r = l, m - 1\n        }\n    }\n    if l - 1 <= len(arr) && l - 1 >= 0 {\n        return arr[l-1].val\n    }\n    return 0\n}\n```
['Array', 'Binary Search', 'Go']