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;
           }
       }
    

Log in to reply
 

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