Design a Data Structure that supports get(int idx), set(int idx, int val), and setAll(int val) all in constant time.


  • 1
    A

    Design a custom datastructure that can store numbers like a dynamically sized array and supports all of the following operations
    get(int index)
    set(int idx, int value)
    setAll(int value)

    For example:

    // Assuming that you named your data-structure as "CustomDS"
    
    CustomDS customDS = new CustomDS();
    customDS.set(0,100); // should set the element at index 0 to value 100
    customDS.set(1,200); // should set the element at index 1 to value 200
    
    get(0); // will return the value at index 0. in our case it will return 100
    
    setAll(1000);  // should set all the elments in the datastructure to value 1000
    
    

  • 0

    This is one possible approach. Waiting for trickier

    class CustomDS:
        def __init__(self):        
            self.cache = dict()
            self.update = dict()
            self.updateAll = False  
                
        def get(self, key):
            if self.updateAll:
                return self.all
            elif key in self.update:
                return self.cache[key]
            elif key in self.cache:
                return self.all
            else:
                return None       
                  
    
        def set(self, key, value):
            self.cache[key] = value   
            self.update[key] = True          
            self.updateAll = False  
            
        def setAll(self, key):
            self.all = key 
            self.updateAll = True 
            self.update = dict()

  • 1
    E

    class Cell{
    int timeStamp;
    int value;
    }

    int allValue;
    cell[] array;

    we store the time and current value for each operation.

    Every time we have the setAllValue(x), we need to store the value and current time.

    Every time we use getValue(index), we just need to compare the timeStamp of we stored setAllValue and it’s original value;

    Every time we use set(index, value); we just need to set array[index] = {current time, value};


  • 0

    Easy to understand and use a trick.
    Use Hash Table to store value, Using a int variable to track the default "global setAll". When call getValue, if the index# is not in the Hash Table, return the "global" int. And When call setAll, simplicity update the "global" int. Below it's my code in C#,hope it helps:

    
       class MyDS
       {
           private int defaultValue;
           private Dictionary<int, int> dict;
    
           public MyDS()
           {
               defaultValue = 0;  //initialize default value
               dict = new Dictionary<int, int>();
           }
    
           public void setAll(int val)
           {
               defaultValue = val;
               dict = new Dictionary<int, int>();
           }
    
           public void setValue(int index, int val)
           {
               if(dict.ContainsKey(index))
                   dict[index] = val;
               else
                   dict.Add(index,val); 
           }
    
           public int getVal(int index)
           {
               if (dict.ContainsKey(index))
                   return dict[index];
               else
                   return defaultValue;
           }
       }
    

  • 0
    E

    Hashtable (set) + Hashmap (dict) structure. I used the set to keep track of containment and the map (dictionary) for value assignments. For setAll, I reset the assignment map and only reassign the special key of 'all' to keep track of the global assignment. As I'm keeping track of containment using the set, when the getter is called and the set indicates the key being called upon exists in our data structure but the map indicates there isn't a value assigned to the key in question, I returned the global value retrieved from the special 'all' key.

    class SetMap:
        
        def __init__(self, _map):
            self._map = _map
            self._set = set(list(_map.keys()))
        
        def _get_(self, key):
            if key in self._map: 
                return self._map[key]
            elif self.contains(key): 
                return self._map['all']
            else: 
                print("Item does not exist..")
                return None
        
        def _set_(self, key, val):
            self._set.add(key)
            self._map[key] = val
            
        def contains(self, key):
            return key in self._set
        
        def remove(self, key):
            if not self.contains(key): return False
            self._set.remove(key) # remove from set
            self._map.pop(key) # remove from map if assignment exists
            return True
    
        def setAll(self, val):
            self._map = {}
            self._map['all'] = val
    

  • 1
    G
     public class CustomDS
            {
                private Dictionary<int, int> d = new Dictionary<int, int>();
                public void set(int idx,int val)
                {
                    if (d.ContainsKey(idx))
                    {
                        d[idx] = val;
                    }
                    else d.Add(idx, val);
                }
                public int get(int idx)
                {
                    if (d.ContainsKey(idx))
                    {
                        return d[idx];
                    }
                    else return -1;
    
                }
                public void setAll(int x)
                {
                    foreach (int item in d.Keys.ToArray())
                    {
                        d[item] = x;
                    }
                }
            }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.