Guest User

SparseArray - Daily Coding Problem

a guest
Jul 23rd, 2019
81
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """
  2. This problem was asked by Facebook.
  3.  
  4. You have a large array with most of the elements as zero.
  5.  
  6. Use a more space-efficient data structure, SparseArray, that implements the same interface:
  7.  
  8. init(arr, size): initialize with the original large array and size.
  9. set(i, val): updates index at i with val.
  10. get(i): gets the value at index i.
  11. """
  12. class SparseArray:
  13. def __init__(self, arr, size):
  14. self.sparseMap = {}
  15.  
  16. for i, element in enumerate(arr):
  17. if element:
  18. self.sparseMap[i] = element
  19.  
  20. def set(self, i, val):
  21. self.sparseMap[i] = val
  22.  
  23. def get(self, i):
  24. return self.sparseMap[i]
  25.  
  26.  
  27.  
  28. s = SparseArray([0,0,0,0,0,0,0,3,0,0,0,4,0,0,0,2], 16)
  29. print(s.get(15))
  30. s.set(1, 9)
  31. print(s.get(1))
RAW Paste Data