Facebook Software Engineer Phone Interview

Job Hunting Interview
, , , , , ,
1

Status: BS CS, 5 Years of Experince
Position: Software Engineer at Facebook
Location: New York, NY
Technical phone screen (1 hour):

Implement a sorted java iterator that returns a sorted list over k sorted lists

Input: 
[[1, 4, 5, 8, 9],
[3, 4, 4, 6],
[0, 2, 8]]
Output:
0, 1, 2, 3, 4, 4, 4, 5, 6, 8, 8, 9

Example class definition:
class SortedIterator implements Iterator<Integer> {
   public SortedIterator(List<List<Integer>> lists) {}
   public boolean hasNext() {}
   public Integer next() {}
}
2 

    public class SortedIterator implements Iterator<Integer> {
    private PriorityQueue<ListIterator> pq;

    private Integer nextVal;
    public SortedIterator(List<List<Integer>> lists) {

        this.pq = new PriorityQueue(lists.size(), new Comparator<ListIterator>(){
            @Override
            public int compare(ListIterator o1, ListIterator o2) {
                return Integer.compare(o1.peek(), o2.peek());
            }
        });

        for (List<Integer> lst : lists) {
            if (lst.size() > 0) {
                pq.offer(new ListIterator(lst.iterator()));
            }
        }
    }

    public boolean hasNext() {
        if (nextVal != null) {
            return true;
        }
        if (pq.isEmpty()) return false;

        ListIterator cur = pq.poll();
        nextVal = cur.next();
        if (cur.hasNext()) {
            pq.offer(cur);
        }
        return true;
    }

    public Integer next() {
        if (!hasNext()) {
            throw new NoSuchElementException("");
        }
        Integer t = nextVal;
        nextVal = null;
        return t;
    }

    /***************************************************************************************************/
    public static void main(String[] args) {
        List<List<Integer>> lst = new ArrayList<>();
        lst.add(Arrays.asList(1, 4, 5, 8, 9));
        lst.add(Arrays.asList(3, 4, 4, 6));
        lst.add(Arrays.asList(0, 2, 8));

        SortedIterator st = new SortedIterator(lst);

        while(st.hasNext()) {
            System.out.print(st.next() + " ");
        }
    }
    /***************************************************************************************************/
    class ListIterator implements Iterator<Integer> {
        private Iterator<Integer> iter;
        private Integer nextVal;

        public ListIterator(Iterator<Integer> iter) {
            this.iter = iter;
        }

        public Integer peek() {
            if (!hasNext()) {
                throw new NoSuchElementException("");
            }
            return nextVal;
        }

        public boolean hasNext() {
            if (nextVal != null) {
                return true;
            }
            if (!iter.hasNext()) return false;

            nextVal = iter.next();
            return true;
        }

        public Integer next() {
            if (!hasNext()) {
                throw new NoSuchElementException("");
            }
            Integer t = nextVal;
            nextVal = null;
            return t;
        }
    }

}