No Initialization Array
Design a data structure that allows one to search, insert, and delete an integer X in O(1) time (i.e. , constant time, independent of the total number of integers stored). Assume that 1 ≤ X ≤ n and that there are m + n units of space available, where m is the maximum number of integers that can be in the table at any one time. (Hint: use two arrays A[1..n] and B[1..m].) You are not allowed to initialize either A or B, as that would take O(m) or O(n) operations. This means the arrays are full of random garbage to begin with, so you must be very careful.
Two arrays both of them with garbage value
dense: contains actual elements in order of insertion
sparse: uses value of [dense] as index and stores the index at which the value is located
So the search value v is legit iff index v of sparse array points to dense's index whose value is also v
package algorithmdesignmanualbook.datastructures
import algorithmdesignmanualbook.print
import java.util.*
import kotlin.random.Random
import kotlin.test.assertFalse
import kotlin.test.assertTrue
/**
* Design a data structure that allows one to search, insert, and delete an integer
* X in O(1) time (i.e. , constant time, independent of the total number of integers
* stored). Assume that 1 ≤ X ≤ n and that there are m + n units of space available,
* where m is the maximum number of integers that can be in the table at any one
* time. (Hint: use two arrays A[1..n] and B[1..m].) You are not allowed to initialize
* either A or B, as that would take O(m) or O(n) operations. This means the arrays
* are full of random garbage to begin with, so you must be very careful.
*
* [Solution link](https://research.swtch.com/sparse):
*
* Two arrays both of them with garbage value
* * dense: contains actual elements in order of insertion
* * sparse: uses *value* of [dense] as index and stores the *index* at which the value is located
*
* So the search value v is legit iff index v of sparse array points to dense's index whose value is also v
*/
class NoInitializationArray(val maxValue: Int, val maxSize: Int) {
private val rand = Random(100)
private val dense = Array(maxSize) { getGarbage() }
private val sparse = Array(maxValue) { getGarbage() }
private var nextIndex = 0
private fun getGarbage() = rand.nextInt(maxValue + 1, maxValue + 1 + 200)
fun print() {
println("dense: ${Arrays.toString(dense)}")
println("sparse: ${Arrays.toString(sparse)}")
}
fun add(value: Int) {
require(value.isNotGarbage())
dense[nextIndex] = value
sparse[value] = nextIndex
nextIndex++
}
private fun hasLegitValue(sparseResult: Int): Boolean {
val value = dense.getOrNull(sparseResult) ?: return false
return value.print().isNotGarbage()
}
private fun Int.isNotGarbage() = this < maxValue
fun delete(value: Int) {
val index = sparse.getOrNull(value) ?: return
if (!hasLegitValue(index)) {
return
}
dense[index] = getGarbage()
sparse[value] = getGarbage()
}
fun search(value: Int): Boolean {
val index = sparse.getOrNull(value) ?: return false
return dense.getOrNull(index) == value
}
}
fun main() {
val solution = NoInitializationArray(maxValue = 20, maxSize = 10)
solution.add(10)
assertTrue { solution.search(10) }
solution.add(6)
assertTrue { solution.search(6) }
solution.add(9)
assertTrue { solution.search(9) }
solution.add(14)
assertTrue { solution.search(14) }
solution.print()
assertFalse { solution.search(100) }
solution.delete(10)
assertFalse { solution.search(10) }
solution.delete(6)
assertFalse { solution.search(6) }
solution.delete(9)
assertFalse { solution.search(9) }
solution.print()
}