2

I got one interview question. Write class UnlimitedArrayInt containing the following methods. Each method should be of O[1] complexity: * void setAll(int number) – all integer numbers are set to the given number; * int get(int index) – returns number at the given index. An index may be any positive integer value; * void set(int index, int number) - sets number at the given index. Array isn’t limited so it may be any positive integer value; number may be any integer value. As they told me solution not based on regular array. So could anyone explain me what data structure better for use, and how to implement the method setAll with complexity O(1), because for my opinion it's always complexity O(n) cause we need to iterate over all indices for setting new value of all elements of any data structure.

Александр
  • 21
  • 3

1 Answers1

3

You need to use Map and one common value that you would use in set. Map would act as an override in case if user sets the value.

Something around below:

public class UnlimitedArrayInt {
    Map<Integer, Integer> values;
    int commonValue;//default value to return if not found

    public UnlimitedArrayInt() {
        values = new HashMap<>();
        commonValue = -1;
    }

    /**
        use common value that you are going to use and at the same time reset all the instance of map (GC would clear all the reference at the back and this is a trade off of clear vs new instance that am making). Runs in O(1) time.
    */
    public void setAll(int number) {
        commonValue = number;
        values = new HashMap<>();
    }
    /**
        return if value was set else return the common value across your data structure if any was used. Else return -1. Runs in O(1) time.
     */
    public int get(int index) {
         return values.getOrDefault(index, commonValue);
    }

    /**
        Override the existing common value which would take the priority over common value. Runs in O(1) time.
    */
    public set(int index, int number) {
         return values.put(index, number);
    }
}
SMA
  • 36,381
  • 8
  • 49
  • 73
  • 1
    Yes, map is the correct idea. I think you can make use of a timestamp variable to avoid clearing of map during setAll(). – nice_dev Dec 14 '19 at 12:31
  • 1
    Yeah agree @vivek_23. There are couple of other ways which we can do the same and this is the simplest i think. With above, you are trading off on space with respect to time. – SMA Dec 14 '19 at 13:02
  • Thanks guys, you all helped very much – Александр Dec 14 '19 at 13:30
  • *"to avoid clearing of map during setAll()"* But why would you want to do this? The old values are not needed by any of the methods, it would just be a waste of memory to keep them. – kaya3 Dec 14 '19 at 15:32
  • @kaya3 Tag me else I won't be notified. It really depends on the ordering of calls. If I set a million elements and call a setAll() and again set the same million elements, it's just more job for the garbage collector. You would better keep them in memory and use timestamp based approach for correctness. Of course, on an average case this would consume a bit more memory, but that's fine. – nice_dev Dec 14 '19 at 15:47
  • @vivek_23 It doesn't necessarily take O(*n*) time to garbage-collect a map of size *n* - see https://stackoverflow.com/questions/3750424/big-o-analysis-of-garbage-collection-runtime-cost - the main point is that we don't need to inspect the map's elements to know that the map is garbage. Regarding correctness, clearing the map is eminently correct; it maintains the invariant property that the map contains only the individual values set more recently than the last call to setAll. – kaya3 Dec 14 '19 at 15:52
  • @kaya3 The approach is correct anyway. No questions on that. I was pondering on my timestamp based approach with map. Also, the garbage collector would take O(n) time to flush it. Even if amortized(by JIT), worst case still remains O(n) https://stackoverflow.com/questions/6757868/map-clear-vs-new-map-which-one-will-be-better – nice_dev Dec 14 '19 at 16:02
  • 1
    @vivek_23 Ah, so by "correctness" you mean it is easier to prove that the timestamp-based approach works in O(1) time. I'll concede that, but realistically the time taken by any sensible garbage collector should never be asymptotically higher than the running-time of the algorithm which creates the garbage in the first place, so accepting it as an amortised cost should be better in practice. If it's an abstract question of how to do it in O(1) non-amortised time, then the timestamp-based solution is the correct one. – kaya3 Dec 14 '19 at 16:10