I thought this problem is to implement an Iterator. Are we supposed to use the java class Iterator?


  • 3
    S

    I thought this problem is to implement an Iterator. Are we supposed to use the java class Iterator in our implementation?

    Here is my 5ms AC solution (not using class Iterator).

    public class ZigzagIterator {

    int arrNum;        //indicates which vector should we use next time
    int[] indexArray;  //index of the next val for vector[i]
    List<List<Integer>> vectors;
    int k;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        k = 2;
        arrNum = 0;
        indexArray = new int[k];
        vectors = new ArrayList<List<Integer>>();
        vectors.add(new ArrayList<Integer>(v1));
        vectors.add(new ArrayList<Integer>(v2));
    }
    
    public int next() {
        while (indexArray[arrNum] >= vectors.get(arrNum).size()){
            arrNum = (arrNum + 1) % k;
        }
        
        int res = vectors.get(arrNum).get(indexArray[arrNum]);
        indexArray[arrNum]++;
        arrNum = (arrNum + 1) % k;
        return res;
    }
    
    public boolean hasNext() {
        for (int i = 0; i < indexArray.length; i++){
            if (indexArray[i] < vectors.get(i).size()){
                return true;
            }
        }
        return false;
    }
    

    }


  • 1

    I recently had a technical interview similar to this question (design an iterator class), and the interviewer did not allow me to use built-in iterators. Just a heads up.

    Here's my solution without iterators or additional data structures:

    public class ZigzagIterator {
        private int currInt;
        private boolean isv2;
        private List<Integer> v1;
        private List<Integer> v2;
    
        public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
            this.currInt = 0;
            this.v1 = v1;
            this.v2 = v2;
        }
    
        public int next() {
            int out;
            if(!isv2 && currInt < v1.size()) {
                out = v1.get(currInt);
                if(currInt < v2.size())
                    isv2 = true;
                else
                    ++currInt;
            }
            else {
                out = v2.get(currInt++);
                if(currInt < v1.size())
                    isv2 = false;
            }
            return out;
        }
    
        public boolean hasNext() {
            return currInt < v1.size() || currInt < v2.size();
        }
    }
    

  • 0
    E

    I don't see the point of not using existing iterators to implement ZigzagIterator. Yes they are all iterators, and yes, they have the same interface, but they behave in VERY DIFFERENT WAYS. What's wrong with building a house with bricks? Avoid using existing iterators just makes the code less readable and less efficient(think about the case when v1 and v2 are linked lists, what's the time complexity of v1.get(index)?). Even if you copy them to array lists, you'll use much more space than simply using iterators. Would you really not use iterators if you encounter the same problem in real world?

    An interview problem is supposed to be a simplified version of a real-world problem. And you are supposed to give a solution just like what you would give when you encountered it during work. It makes sense to add time or space constraints as we have seen, since those are also what we are facing in real world. And it makes sense to forbid using existing libraries or APIs only when it would achieve a better performance if without them, which happens when what we want to implement are very basic, like some string operations. So @aaron_iglesias no offense, your interviewer was very ridiculous.


Log in to reply
 

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