educative.io

Isnt the naive approach and the Optimized approach the same?

Courses
, ,
#1

I don’t understand how the optimized approach is a better solution. Both naïve and optimized solutions have the same space and time complexity.

#2 
package com.company;

import java.util.ArrayList;
import java.util.HashMap;

public class SnapShot {

    int snapId = -1;
    HashMap<Integer, Integer[]> snapshots = new HashMap<Integer,Integer[]>();
    Integer[] arr;


    public void init(int length){
        arr = new Integer[length];
        for(int x = 0;x<arr.length;x++) {
            arr[x] = 0;
        }
    }

    public void setValue(int idx, int val){
        if(idx < arr.length){
            arr[idx] = val;
        }
    }

    public int Snapshot(){ //this is a naive approach
        snapId++;
        Integer[] copy = new Integer[arr.length];
        for(int x =0;x< copy.length;x++){
            copy[x] = arr[x];
        }
        snapshots.put(snapId, copy);
        return snapId;
    }

    public Integer getValue(int idx, int snapId){
        Integer[] ssArr = snapshots.get(snapId);
        if(ssArr != null && ssArr.length >0){
            if(idx < ssArr.length){
                return ssArr[idx];
            }
            else{
                return null;
            }
        }
        else{
            return null;
        }
    }
}

Even the setVal ftn will have the O(1) time complexity according to this solution

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Snapshot Array - Grokking Coding Interview Patterns in Java

#3

Hello @Furrukh_Khan

Thank you for pointing out this issue. We have updated the discussions of the naive approach and of the optimized approach to make the difference clearer. We’ll update you once the changes go live.

1 Like
#4

The updated version is live now, thank you for the feedback.
Feel free to drop in any further suggestions.