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


  • 6

    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
    This post is deleted!

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

  • 0
    M

    @githika How is it a constant time when you are looping the whole array in setAll?
    The time complexity there is O(n) where n is the size of the array.


  • 0
    G
    This post is deleted!

  • 0
    E

    @new2500 setAll is technically still O(n), this just transfers the work to garbage collector


  • 0

    @elastico

    I don't think we even have to consider the garbage collector. The foreach block loops through each key. This alone will be a O(n) operation.


  • 1
    U

    I think i'd go with the timestamp option. any better solutions?

    class DS(object):
      def __init__(self):
        self.storage = {}
        self.allValue = (time.time())
    
      def get(idx):
        if idx not in self.storage:
          return None
        val = self.storage[idx]
        if val[0] < self.allValue[0]:
          self.allValue[1]
        return val[1]
    
      def set(idx, val):
        self.storage[idx] = (time.time(), val)
      
      def setAll(val):
        self.allValue = (time.time(), val)
    

  • 0
    E

    @user2967 nice idea


Log in to reply
 

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