Can anyone tell me what is wrong this this SaltedInt approach (Map+Set)


  • 0
    B
        private Map<Integer, SaltedInt> map;
        private Set<SaltedInt> set;
    
        publicRandomizedSet() {
          map = new HashMap<>();
          set = new HashSet<>();
        }
    
        @Override
        public boolean insert(int val) {
          if(map.containsKey(val)) return false;
          SaltedInt si = new SaltedInt(val);
          map.put(val, si);
          set.add(si);
          return true;
        }
    
        public boolean remove(int val) {
          if(!map.containsKey(val)) return false;
          SaltedInt si = map.remove(val);
          set.remove(si);
          return true;
        }
    
        public int getRandom() {
          SaltedInt next = set.iterator().next();
          remove(next.val);
          insert(next.val);
          return next.val;
        }
    
        private static class SaltedInt {
    
          private static final Random RANDOM = new Random();
    
          int val;
          int salt;
    
          SaltedInt(int val) {
            this.val = val;
            this.salt = RANDOM.nextInt();
          }
    
          public boolean equals(Object other) {
            if(other instanceof SaltedInt) {
              SaltedInt otherInt = (SaltedInt) other;
              return val == otherInt.val && salt == otherInt.salt;
            }
            return false;
          }
    
          public int hashCode() {
            return salt * 31 + val;
          }
        }
    

    The result seems reasonably random to me. I don't know why it does not pass the test. Not enough randomness???


Log in to reply
 

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