Facebook Interview Question Solutions Engineers
Country: Israel
Interview Type: Phone Interview
class MyIterator{
PriorityQueue<Integer> pq=new PriorityQueue<>();
int [][]data=null;
int []k=null;
public MyIterator(int [][] data) {
this.data=data;
k=new int[data.length];
this.preProcess(data);}
int next(){
int tmp=pq.remove();
this.postProcess(tmp);
return tmp;}
boolean hashNext(){
return pq.isEmpty();
}
public void preProcess(int [][]data){
for (int i = 0; i < k.length; i++) {
pq.add(data[i][k[i]]);
}}
public void postProcess(int removedData){
for (int i = 0; i < k.length; i++) {
if(k[i]<data[i].length && data[i][k[i]]==removedData){
k[i]=k[i]+1;
if(k[i]<data[i].length){
pq.add(data[i][k[i]]);
}
return;}}}}
public class IteratorInKSortedArray {
public static void main(String[] args) {
int [][]in={
{1,5,7},
{2,3,10},
{4,6,9}
};
MyIterator itr=new MyIterator(in);
while(!itr.hashNext()){
System.out.print(itr.next()+" ");
}}}
Use K length array and priority queue
class MyIterator{
PriorityQueue<Integer> pq=new PriorityQueue<>();
int [][]data=null;
int []k=null;
public MyIterator(int [][] data) {
this.data=data;
k=new int[data.length];
this.preProcess(data);
}
int next(){
int tmp=pq.remove();
this.postProcess(tmp);
return tmp;}
boolean hashNext(){
return pq.isEmpty();}
public void preProcess(int [][]data){
for (int i = 0; i < k.length; i++) {
pq.add(data[i][k[i]]);
}}
public void postProcess(int removedData){
for (int i = 0; i < k.length; i++) {
if(k[i]<data[i].length && data[i][k[i]]==removedData){
k[i]=k[i]+1;
if(k[i]<data[i].length){
pq.add(data[i][k[i]]);
}
return;}}}
import java.util.ArrayList;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.lang.Comparable;
import java.util.List;
import static java.util.Arrays.*;
class MyIter<T extends Comparable> implements Iterator {
class IterState implements Comparable<IterState> {
private Iterator<T> iter;
private T currVal;
public IterState(Iterator<T> i) {
iter = i;
next();
}
public T getVal() { return currVal; }
public boolean hasNext() { return iter.hasNext(); }
public void next() {
if (iter.hasNext()) {
currVal = iter.next();
} else {
currVal = null;
}
}
public int compareTo(IterState o) {
return currVal.compareTo(o.getVal());
}
}
private PriorityQueue<IterState> states;
public MyIter(List<List<T>> listOfList) {
states = new PriorityQueue<IterState>();
for (List<T> l:listOfList) {
Iterator<T> it = l.iterator();
if (it.hasNext()) {
states.add(new IterState(it));
}
}
};
public T next() {
IterState n = states.poll();
T retval = n.getVal();
// if there is more in the current list, then put it back in the queue
if (n.hasNext()) {
n.next();
states.add(n);
}
return retval;
};
public boolean hasNext() {
return !states.isEmpty();
}
}
class Main {
private static <T extends Comparable> ArrayList toArray(List<List<T>> listOfList) {
MyIter<T> i = new MyIter<T>(listOfList);
ArrayList retval = new ArrayList();
while (i.hasNext()) {
retval.add(i.next());
}
return retval;
}
public static void main(String[] args) {
System.out.println("Hello world!");
ArrayList arr = toArray(asList(
asList(1,3,5),
asList(2,4,6),
asList(7,9),
asList(8),
asList(0,10),
asList()));
for (Object i:arr) {
System.out.println(i);
}
arr = toArray(asList());
for (Object i:arr) {
System.out.println(i);
}
}
}
import java.io.*;
import java.util.*;
public class Solution {
public void testMyIterator() {
Integer[][] inputData = new Integer[][] {{1,2,3,10},{},{-1,4,5}};
MyIterator<Integer> it = new MyIterator<>(inputData);
while(it.hasNext()) {
System.out.println(it.next());
}
}
public static void main(String[] args) {
Solution s = new Solution();
s.testMyIterator();
}
public class MyIterator<T extends Comparable<T>> {
private T[][] data;
private int[] nextElementIndexByArrayIndex;
public MyIterator(T[][] data) {
if(data == null) {
throw new IllegalArgumentException("data can't be null");
}
nextElementIndexByArrayIndex = new int[data.length];
for(int i = 0; i < data.length; i++) {
nextElementIndexByArrayIndex[i] = 0;
}
this.data = data;
}
public T next() {
if(!hasNext()) {
return null;
}
T retval = null;
int selectedArrayIndex = -1;
int selectedElementIndex = -1;
for(int i = 0; i < data.length; i++) {
int elementIndex = nextElementIndexByArrayIndex[i];
if(data[i].length <= elementIndex) {
continue;
}
T toCompare = data[i][elementIndex];
if(retval == null || retval.compareTo(toCompare) > 0) {
retval = toCompare;
selectedArrayIndex = i;
selectedElementIndex = elementIndex;
}
}
selectedElementIndex++;
nextElementIndexByArrayIndex[selectedArrayIndex] = selectedElementIndex;
return retval;
}
public boolean hasNext() {
for(int i = 0; i < data.length; i++) {
if(data[i].length > nextElementIndexByArrayIndex[i]) {
return true;
}
}
return false;
}
}
}
public class Solution{
public static void main(String[] args) {
int[][] in = { { 1, 5, 7 }, { 2, 3, 10 }, { 4, 6, 9 } };
Runner1 itr = new Runner1(in);
while (itr.hashNext()) {
System.out.print(itr.next() + " ");
}
}
public int next() {
PeekingIterator itr = queue.remove();
int result = itr.next();
if(itr.hasNext()){
queue.add(itr);
}
return result;
}
public boolean hashNext() {
return !queue.isEmpty();
}
private final Queue<PeekingIterator> queue;
public Solution(int[][] data) {
queue = new PriorityQueue<>(data.length, (i1, i2) -> Integer.compare(i1.peek(), i2.peek()));
for (int[] in : data) {
if (in != null && in.length != 0) {
queue.add(new PeekingIterator(in));
}
}
}
public class PeekingIterator {
boolean hasNext;
int index = 0;
int next;
int[] array;
PeekingIterator(int[] array) {
this.array = array;
moveAhead();
}
private void moveAhead() {
if (index < this.array.length) {
hasNext = true;
next = array[index];
index++;
} else {
hasNext = false;
}
}
public boolean hasNext() {
return hasNext;
}
public int next() {
int res = next;
moveAhead();
return res;
}
public int peek() {
return next;
}
}
}
Since the problem uses T as a generics:
public class MyIterator<T> {
private MyIterator<T> current;
private MyIterator<T> next;
private MyIterator<T> last; // optimization
private T value;
private MyIterator(T element) {
this.value = element;
}
public MyIterator(T[][] elements) {
this.current = this;
int[] pos = new int[elements.length];
boolean isOver = false;
while(!isOver){
int j = -1;
int counter = 0;
T minElement = null;
for(int i = 0; i < elements.length ; ++i) {
if(pos[i] < elements[i].length) {
if(minElement == null) {
minElement = elements[i][pos[i]];
}
if(compareElements(minElement,elements[i][pos[i]])) {
minElement = elements[i][pos[i]];
j = i;
}
}else {
counter++;
}
}
if(j != -1) {
pos[j]++;
}
if(counter == elements.length) {
isOver = true;
break;
}
if(this.current.value == null) {
this.current.value = minElement;
}else {
if(this.next == null) {
this.next = new MyIterator<T>(minElement);
this.last = this.next;
}else {
this.last.next = new MyIterator<T>(minElement);
this.last = this.last.next;
}
}
}
}
private boolean compareElements(T minElement, T element) {
if(minElement instanceof String) {
return ((String)minElement).compareTo((String)element) >= 0;
}
if(minElement instanceof Integer) {
return ((Integer)minElement).compareTo((Integer)element) >= 0;
}
if(minElement instanceof Double) {
return ((Double)minElement).compareTo((Double)element) >= 0;
}
if(minElement instanceof Long) {
return ((Long)minElement).compareTo((Long)element) >= 0;
}
if(minElement instanceof Character) {
return ((Character)minElement).compareTo((Character)element) >= 0;
}
Method m;
Object result = null;
try {
m = minElement.getClass().getMethod("compareTo", element.getClass());
result = m.invoke(minElement, element);
} catch (NoSuchMethodException | SecurityException | IllegalAccessException | IllegalArgumentException | InvocationTargetException e) {
throw new RuntimeException("Provided Object have to have comparator method");
}
return ((Integer)result).intValue() >= 0;
}
public T next() {
T value = this.current.value;
this.current = this.current.next;
return value;
}
public boolean hasNext(){
return this.current.next == null;
}
}
class MyIter(object):
def __init__(self, ll):
self._ll = ll
def __iter__(self):
self._list_len = len(self._ll[0])
self._list_count = len(self._ll)
self._indices = [0] * self._list_count
return self
def __next__(self):
i = 0
m = int(25535)
m_ind = None
while i < self._list_count:
index = self._indices[i]
if index < self._list_len:
temp = self._ll[i][index]
if temp < m:
m = temp
m_ind = i
i += 1
if m_ind is not None:
self._indices[m_ind] += 1
return m
else:
raise StopIteration
if __name__ == '__main__':
ll = [[1,5,7], [2,3,10],[4,6,9]]
it = MyIter(ll)
print(list(it))
public class AscendingIterator implements Iterator<Integer> {
int[] nums;
int currentIndex = -1;
AscendingIterator(int[] num1, int[] num2, int[] num3) {
int size = num1.length + num2.length + num3.length;
nums = new int[size];
int i = 0, j = 0, k = 0, l = 0;
while (i < num1.length || j < num2.length || k < num3.length) {
int intOne, intTwo, intThree;
intOne = intTwo = intThree = Integer.MAX_VALUE;
if (i < num1.length)
intOne = num1[i];
if (j < num2.length)
intTwo = num2[j];
if (k < num3.length)
intThree = num3[k];
if (getMin(intOne, intTwo, intThree) == 0) {
nums[l] = num1[i];
l++;
i++;
} else if (getMin(intOne, intTwo, intThree) == 1) {
nums[l] = num2[j];
l++;
j++;
} else {
nums[l] = num3[k];
l++;
k++;
}
}
}
private int getMin(int i, int i1, int i2) {
if (i < i1 && i < i2)
return 0;
else if (i1 < i && i1 < i2)
return 1;
else
return 2;
}
@Override
public boolean hasNext() {
return (currentIndex + 1) < nums.length;
}
@Override
public Integer next() {
currentIndex++;
if (currentIndex < nums.length)
return nums[currentIndex];
else
throw new IndexOutOfBoundsException("reached limit");
}
public static void main(String args[]) {
AscendingIterator ascendingIterator = new AscendingIterator(new int[]{1, 5, 7}, new int[]{2, 3, 10}, new int[]{4, 6, 9});
while (ascendingIterator.hasNext()){
System.out.print(ascendingIterator.next()+"");
}
}
}
public class AscendingIterator implements Iterator<Integer> {
int[] nums;
int currentIndex = -1;
AscendingIterator(int[] num1, int[] num2, int[] num3) {
int size = num1.length + num2.length + num3.length;
nums = new int[size];
int i = 0, j = 0, k = 0, l = 0;
while (i < num1.length || j < num2.length || k < num3.length) {
int intOne, intTwo, intThree;
intOne = intTwo = intThree = Integer.MAX_VALUE;
if (i < num1.length)
intOne = num1[i];
if (j < num2.length)
intTwo = num2[j];
if (k < num3.length)
intThree = num3[k];
if (getMin(intOne, intTwo, intThree) == 0) {
nums[l] = num1[i];
l++;
i++;
} else if (getMin(intOne, intTwo, intThree) == 1) {
nums[l] = num2[j];
l++;
j++;
} else {
nums[l] = num3[k];
l++;
k++;
}
}
}
private int getMin(int i, int i1, int i2) {
if (i < i1 && i < i2)
return 0;
else if (i1 < i && i1 < i2)
return 1;
else
return 2;
}
@Override
public boolean hasNext() {
return (currentIndex + 1) < nums.length;
}
@Override
public Integer next() {
currentIndex++;
if (currentIndex < nums.length)
return nums[currentIndex];
else
throw new IndexOutOfBoundsException("reached limit");
}
public static void main(String args[]) {
AscendingIterator ascendingIterator = new AscendingIterator(new int[]{1, 5, 7}, new int[]{2, 3, 10}, new int[]{4, 6, 9});
while (ascendingIterator.hasNext()){
System.out.print(ascendingIterator.next()+"");
}
}
}
public class AscendingIterator implements Iterator<Integer> {
int[] nums;
int currentIndex = -1;
AscendingIterator(int[] num1, int[] num2, int[] num3) {
int size = num1.length + num2.length + num3.length;
nums = new int[size];
int i = 0, j = 0, k = 0, l = 0;
while (i < num1.length || j < num2.length || k < num3.length) {
int intOne, intTwo, intThree;
intOne = intTwo = intThree = Integer.MAX_VALUE;
if (i < num1.length)
intOne = num1[i];
if (j < num2.length)
intTwo = num2[j];
if (k < num3.length)
intThree = num3[k];
if (getMin(intOne, intTwo, intThree) == 0) {
nums[l] = num1[i];
l++;
i++;
} else if (getMin(intOne, intTwo, intThree) == 1) {
nums[l] = num2[j];
l++;
j++;
} else {
nums[l] = num3[k];
l++;
k++;
}
}
}
private int getMin(int i, int i1, int i2) {
if (i < i1 && i < i2)
return 0;
else if (i1 < i && i1 < i2)
return 1;
else
return 2;
}
@Override
public boolean hasNext() {
return (currentIndex + 1) < nums.length;
}
@Override
public Integer next() {
currentIndex++;
if (currentIndex < nums.length)
return nums[currentIndex];
else
throw new IndexOutOfBoundsException("reached limit");
}
public static void main(String args[]) {
AscendingIterator ascendingIterator = new AscendingIterator(new int[]{1, 5, 7}, new int[]{2, 3, 10}, new int[]{4, 6, 9});
while (ascendingIterator.hasNext()){
System.out.print(ascendingIterator.next()+"");
}
}
}
public class AscendingIterator implements Iterator<Integer> {
int[] nums;
int currentIndex = -1;
AscendingIterator(int[] num1, int[] num2, int[] num3) {
int size = num1.length + num2.length + num3.length;
nums = new int[size];
int i = 0, j = 0, k = 0, l = 0;
while (i < num1.length || j < num2.length || k < num3.length) {
int intOne, intTwo, intThree;
intOne = intTwo = intThree = Integer.MAX_VALUE;
if (i < num1.length)
intOne = num1[i];
if (j < num2.length)
intTwo = num2[j];
if (k < num3.length)
intThree = num3[k];
if (getMin(intOne, intTwo, intThree) == 0) {
nums[l] = num1[i];
l++;
i++;
} else if (getMin(intOne, intTwo, intThree) == 1) {
nums[l] = num2[j];
l++;
j++;
} else {
nums[l] = num3[k];
l++;
k++;
}
}
}
private int getMin(int i, int i1, int i2) {
if (i < i1 && i < i2)
return 0;
else if (i1 < i && i1 < i2)
return 1;
else
return 2;
}
@Override
public boolean hasNext() {
return (currentIndex + 1) < nums.length;
}
@Override
public Integer next() {
currentIndex++;
if (currentIndex < nums.length)
return nums[currentIndex];
else
throw new IndexOutOfBoundsException("reached limit");
}
public static void main(String args[]) {
AscendingIterator ascendingIterator = new AscendingIterator(new int[]{1, 5, 7}, new int[]{2, 3, 10}, new int[]{4, 6, 9});
while (ascendingIterator.hasNext()){
System.out.print(ascendingIterator.next()+"");
}
}
}
class MyIter(object):
def __init__(self, ll):
self._ll = ll
def __iter__(self):
self._list_len = len(self._ll[0])
self._list_count = len(self._ll)
self._indices = [0] * self._list_count
return self
def __next__(self):
i = 0
m = int(25535)
m_ind = None
while i < self._list_count:
index = self._indices[i]
if index < self._list_len:
temp = self._ll[i][index]
if temp < m:
m = temp
m_ind = i
i += 1
if m_ind is not None:
self._indices[m_ind] += 1
return m
else:
raise StopIteration
if __name__ == '__main__':
ll = [[1,5,7], [2,3,10],[4,6,9]]
it = MyIter(ll)
print(list(it))
public class MyIterator<T> {
private List<T> data;
private int index;
public MyIterator(List<List<T>> lists) {
data = new ArrayList<T>();
for (List<T> list : lists) {
data.addAll(list);
}
Collections.sort(data);
index = 0;
}
public T next() {
if (hasNext()) {
return list.get(index++);
}
throw new IllegalStateException("No next element");
}
public boolean hasNext() {
return index < data.size();
}
}
public class MyIterator<T> {
private List<T> data;
private int index;
public MyIterator(List<List<T>> lists) {
data = new ArrayList<T>();
for (List<T> list : lists) {
data.addAll(list);
}
Collections.sort(data);
index = 0;
}
public T next() {
if (hasNext()) {
return list.get(index++);
}
throw new IllegalStateException("No next element");
}
public boolean hasNext() {
return index < data.size();
}
}
class Iterator{
constructor(arrays) {
this.arrays = arrays;
}
next(){
if(!this.hasNext()) return;
const K = this.arrays.length;
let minObject = {
val: Number.MAX_VALUE,
index: null
};
for(let i=0;i<K ; i++){
if(this.arrays[i].length > 0){
let min = Math.min(this.arrays[i][0]);
if(min < minObject.val){
minObject.val = min;
minObject.index = i;
}
}
}
return this.arrays[minObject.index].shift();
}
hasNext(){
let hasItems = false;
this.arrays.forEach(arr => {
if(arr.length > 0){
hasItems = true;
}
});
return hasItems;
}
}
const iter = new Iterator([[1,5,7], [2,3,10], [4,6,9]])
const iterated_values = [];
while(iter.hasNext()){
iterated_values.push(iter.next());
}
assert.deepEqual(iterated_values, [1,2,3,4,5,6,7,9,10], 'The two arrays are not equal')
class MyIter(object):
"""Iterator implementation for sorted iterables (lists)"""
def __init__(self, lists):
lst = [item for sublist in lists for item in sublist]
lst.sort() # ensure the list is sorted (asc)
self._lst = lst
self._iter = None
self._idx = None
def __iter__(self):
if self._iter is None:
self._iter = iter(self._lst)
self._idx = 0
return self
def __next__(self):
if self._iter is None:
raise StopIteration
try:
_next = next(self._iter)
self._idx += 1
return _next
except StopIteration:
self._iter = None
self._idx = None
raise
def hasNext(self):
"""check if iterator is exhausted"""
# note: this is not python iterator needed, implemented as part of requirements
#print('index:', self._idx)
if self._idx is None:
return False
elif self._idx >= len(self._lst):
return False
return True
if __name__ == '__main__':
ll = [[1,5,7], [2,3,10], [4,6,9]]
# python way
it = MyIter(ll)
print(list(it))
# using the hasNext
it = iter(it)
while it.hasNext():
print(next(it))
import heapq
class Mylists:
def __init__(self, lists):
k = len(lists)
self.lists = lists
self.min_heap = []
self.constructHeap(k)
def constructHeap(self,k):
# insert first elemnt of all the lists in the heap
for i, list1 in enumerate(self.lists):
heapq.heappush(self.min_heap, (list1[0], 0, i))
# element val, index and list referance
def next(self):
# it first return the top element
# modify the heap which add the next element in the heap for next iteration
if not self.min_heap:
return "No more element present"
val, idx, list_ref = heapq.heappop(self.min_heap)
if idx+1 < len(self.lists[list_ref]):
heapq.heappush(self.min_heap, (self.lists[list_ref][idx+1], idx+1,list_ref))
return val
temp = Mylists([[1,5,7], [2,3,10],[4,6,9]])
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
import heapq
class Mylists:
def __init__(self, lists):
k = len(lists)
self.lists = lists
self.min_heap = []
self.constructHeap(k)
def constructHeap(self,k):
# insert first elemnt of all the lists in the heap
for i, list1 in enumerate(self.lists):
heapq.heappush(self.min_heap, (list1[0], 0, i))
# element val, index and list referance
def next(self):
# it first return the top element
# modify the heap which add the next element in the heap for next iteration
if not self.min_heap:
return "No more element present"
val, idx, list_ref = heapq.heappop(self.min_heap)
if idx+1 < len(self.lists[list_ref]):
heapq.heappush(self.min_heap, (self.lists[list_ref][idx+1], idx+1,list_ref))
return val
temp = Mylists([[1,5,7], [2,3,10],[4,6,9]])
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
class MyIterator:
def __init__(self, A):
self._A = A
self._ind = [0] * len(A)
self._K = len(A)
self._N = len(A[0])
self._maxA = max([A[i][-1] for i in range(len(A))]) + 1
def __iter__(self):
return self
def __next__(self):
if not self.hasNext():
raise StopIteration
output = self._maxA
inc_i = 0
for i in range(self._K):
j = self._ind[i]
if j < self._N and self._A[i][j] < output:
output = self._A[i][j]
inc_i = i
self._ind[inc_i] += 1
return output
def hasNext(self):
return min(self._ind) < self._N
if __name__ == '__main__':
mi = MyIterator([[1, 5, 7], [2, 3, 10], [4, 6, 9]])
print([i for i in mi])
package com.rpm.practise.ds;
import java.util.Arrays;
public class MyMultiArray4 {
static Integer[][] in = { { 1, 5, 7 }, { 2, 3, 10 }, { 4, 6, 9 } };
public static void main(String[] args) {
MyMultiIterator4 it = new MyMultiIterator4(in);
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
class MyMultiIterator4<T> {
T[][] myData;
T[] singleArray;
int pos = 0;
public MyMultiIterator4(Integer[][] in) {
this.myData = (T[][]) in;
singleArray = preProcess(myData);
}
public boolean hasNext() {
if (singleArray.length > pos) {
return true;
} else
return false;
}
public T next() {
if (hasNext()) {
if (hasNext()) {
return singleArray[pos++];
}
return null;
}
return null;
}
public T[] preProcess(T[][] myData) {
int subArrayLength = myData[0].length;
int arrayLength = myData.length;
singleArray = (T[]) new Integer[arrayLength*subArrayLength];
int x = 0;
int y = 0;
int count = 0;
do {
singleArray[count++] = myData[y][x++];
if (x == subArrayLength) {
x = 0;
y++;
}
} while (y!=arrayLength);
Arrays.sort(singleArray);
return singleArray;
}
}
1. Create a min_heap of just the first element of each array (using priority_queue in C++ STL). O(k) space
2. A hash table contains <element, index of its array> mapping. O(k) space
3. An array contains the index of this element in its respective array. O(k) space
For next(), fetch the top of min heap. look up this element in the hash table and increment the index in the sorted array. add this element to the heap.
For hasnext(), we just need to return <pq>.empty()==false
package main
import (
"fmt"
"math"
)
/*
Given K sorted (ascending) arrays with N elements in each array, implement an iterator for iterating over the elements of the arrays in ascending order.
The constructor receives all of the input as array of arrays.
You need to implement the MyIterator class with a constructor and the following methods:
class MyIterator<T> {
T next();
boolean hasNext();
}
You are allowed to use only O(K) extra space with this class.
example:
input:
[[1,5,7], [2,3,10],[4,6,9]]
The iterator should return:
1,2,3,4,5,6,7,9,10
*/
// only O(K) extra space -> k pointer of k array
type MyIterator struct {
data [][]int
numOfArrays int
arraySize int
// k + 2 extra space
arrayPointer []int
nextArray int
nextElement int
}
func New(input [][]int, numOfArrays int, arraySize int) *MyIterator {
mi := &MyIterator{
data: input,
numOfArrays: numOfArrays,
arraySize: arraySize,
arrayPointer: make([]int, numOfArrays),
nextArray: -1,
nextElement: -1,
}
minArrayIndex, minElementIndex := mi.findNextMin()
mi.nextArray = minArrayIndex
mi.nextElement = minElementIndex
return mi
}
// worst case O(K)
func (m *MyIterator) next() int {
if !m.hasNext() {
return -1
}
min := m.data[m.nextArray][m.nextElement]
m.arrayPointer[m.nextArray] = m.nextElement + 1
minArrayIndex, minElementIndex := m.findNextMin()
m.nextArray = minArrayIndex
m.nextElement = minElementIndex
return min
}
// worst case O(1)
func (mi *MyIterator) hasNext() bool {
return mi.nextArray != -1
}
func(mi MyIterator) findNextMin() (nextArray int, nextElement int) {
nextMin := math.MaxInt32
minArrayIndex := -1
minElementIndex := -1
for i, p := range mi.arrayPointer {
if p < mi.arraySize && mi.data[i][p] < nextMin {
minArrayIndex = i
minElementIndex = p
nextMin = mi.data[i][p]
}
}
return minArrayIndex, minElementIndex
}
func main() {
mi := New([][]int{
[]int{1,4,7},
[]int{2,3,10},
[]int{4,6,9},
}, 3, 3)
for mi.hasNext() {
fmt.Println(mi.next())
}
}
import java.util.*;
public class Test {
public static void main(String[] args) {
Integer[][] inputData = new Integer[][] {{1,5,7},{2,3,10},{4,6,9}};
MyIterator<Integer> it = new MyIterator<>(inputData);
while(it.hasNext()) {
System.out.println(it.next());
}
}
}
class MyIterator<T extends Comparable<T>> {
PriorityQueue<T[]> priorityQueue;
public MyIterator(T[][] t) {
Comparator<T[]> comparator = Comparator.comparing(o -> o[0]);
priorityQueue = new PriorityQueue<>(t.length, comparator);
priorityQueue.addAll(Arrays.asList(t));
}
T next() {
T[] elem = priorityQueue.remove();
T t = elem[0];
if (elem.length == 1) {
return t;
}
elem = Arrays.copyOfRange(elem, 1, elem.length);
priorityQueue.add(elem);
return t;
}
boolean hasNext() {
return !priorityQueue.isEmpty();
}
}
import heapq
class myInterator:
def __init__(self, arr):
self.arr = arr
#self.last = (-1, -1)
self.passed = 0
self.heads = []
self.n_total = 0
for i in range(len(arr)):
heapq.heappush(self.heads, (self.arr[i][0], i, 0))
self.n_total += len(a)
def next(self):
x = heapq.heappop(self.heads)
item = x[0]
l = x[1]
index = x[2]
self.passed += 1
if len(self.arr[l]) > index + 1:
heapq.heappush(self.heads, (self.arr[l][index+1], l, index+1))
return item
pass
def has_next(self):
if self.passed == self.n_total:
return False
return True
public class SortedArraysIterator {
private int[] positions;
private int[][] arrays;
public SortedArraysIterator(int[][] arrays){
this.positions = new int[arrays.length];
this.arrays = arrays;
}
public Integer next(){
int min = Integer.MAX_VALUE;
int k = -1;
for (int i = 0; i < arrays.length; i++){
int[] array = arrays[i];
int position = positions[i];
if (position < array.length && position > -1){
if (array[position] < min){
k = i;
min = array[position];
}
}else{
positions[i] = -1;
}
}
if (k == -1){
throw new NoSuchElementException(); //will this be thrown and has next return true?
}
positions[k] = positions[k] < arrays[k].length -1 ? positions[k] + 1 : -1; //forgot to update this
return min;
}
public boolean hasNext(){
for (int i = 0; i < arrays.length; i++){
if (positions[i] > -1) return true;
}
return false;
}
}
Go Lang: MinHeap
func main() {
mi := NewMyIterator([][]int{{1, 2, 3}, {5, 8, 9}, {4, 6, 7, 10}})
for mi.hasNext() {
// fmt.Println(mi.ap)
fmt.Println(mi.next())
}
}
type MyIterator struct {
data [][]int
ap []int
mHeap *minHeap
}
func NewMyIterator(data [][]int) *MyIterator {
iterator := MyIterator{
data: data,
ap: make([]int, len(data)), //array porinters
mHeap: &minHeap{},
}
iterator.preProcess()
return &iterator
}
func (m *MyIterator) preProcess() {
for _, curr_data := range m.data {
heap.Push(m.mHeap, curr_data[0])
}
}
func (m *MyIterator) postProcess(removedElement int) {
for array_index, curr_array := range m.data {
if m.ap[array_index] < len(curr_array) && removedElement == curr_array[m.ap[array_index]] {
m.ap[array_index] += 1
if m.ap[array_index] < len(curr_array) {
heap.Push(m.mHeap, curr_array[m.ap[array_index]])
}
return
}
}
}
func (m *MyIterator) next() int {
curr_element := heap.Pop(m.mHeap).(int)
m.postProcess(curr_element)
return curr_element
}
func (m *MyIterator) hasNext() bool {
return m.mHeap.Len() > 0
}
type minHeap []int
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) {
curr_value := x.(int)
(*h) = append((*h), curr_value)
}
func (h *minHeap) Pop() interface{} {
n := h.Len()
x := (*h)[n-1]
(*h) = (*h)[:n-1]
return x
}
public interface IMultiArrayIterator<T> {
T next();
bool hasNext();
}
public class MultiArrayAsc : IMultiArrayIterator<int>
{
private readonly int[][] _arrays;
private readonly int[] _currentElementIndexes;
public MultiArrayAsc(int[][] arrays) {
_arrays = arrays;
_currentElementIndexes = new int[_arrays.GetLength(0)];
}
public bool hasNext()
{
for (var i = 0; i < _currentElementIndexes.Length; i++) {
if (_currentElementIndexes[i] < _arrays[i].Length) {
return true;
}
}
return false;
}
public int next()
{
var arrayIndex = -1;
for (var i = 0; i < _currentElementIndexes.Length; i++) {
if (_currentElementIndexes[i] < _arrays[i].Length) {
if (arrayIndex == -1 || _arrays[i][_currentElementIndexes[i]] < _arrays[arrayIndex][_currentElementIndexes[arrayIndex]]) {
arrayIndex = i;
}
}
}
if (arrayIndex != -1) {
var value = _arrays[arrayIndex][_currentElementIndexes[arrayIndex]];
_currentElementIndexes[arrayIndex]++;
return value;
}
throw new System.IndexOutOfRangeException();
}
}
{{
from heapq import heappop, heappush
class MyIterator:
def __init__(self, arrays):
self.arrays = arrays
self.mh = []
for i, arr in enumerate(self.arrays):
heappush(self.mh, (arr[0], 0, i))
def next(self):
if not self.hasNext():
raise Exception()
el, j, i = heappop(self.mh)
if j + 1 < len(self.arrays[i]):
heappush(self.mh, (self.arrays[i][j+1], j+1, i))
return el
def hasNext(self):
return len(self.mh) > 0
def test(arrays, expected):
mi = MyIterator(arrays)
res = []
while mi.hasNext():
res += [mi.next()]
print(f'test: {arrays} -> {res}')
assert res == expected, f'{res} == {expected}'
test([[1], [2]], [1,2])
test([[2], [1]], [1,2])
test([[1,5,7], [2,3,10], [4,6,9]], [1,2,3,4,5,6,7,9,10])
test([[1,5,7], [2,3,10]], [1,2,3,5,7,10])
}}
{{
from heapq import heappop, heappush
class MyIterator:
def __init__(self, arrays):
self.arrays = arrays
self.mh = []
for i, arr in enumerate(self.arrays):
heappush(self.mh, (arr[0], 0, i))
def next(self):
if not self.hasNext():
raise Exception()
el, j, i = heappop(self.mh)
if j + 1 < len(self.arrays[i]):
heappush(self.mh, (self.arrays[i][j+1], j+1, i))
return el
def hasNext(self):
return len(self.mh) > 0
def test(arrays, expected):
mi = MyIterator(arrays)
res = []
while mi.hasNext():
res += [mi.next()]
print(f'test: {arrays} -> {res}')
assert res == expected, f'{res} == {expected}'
test([[1], [2]], [1,2])
test([[2], [1]], [1,2])
test([[1,5,7], [2,3,10], [4,6,9]], [1,2,3,4,5,6,7,9,10])
test([[1,5,7], [2,3,10]], [1,2,3,5,7,10])
}}
public class ContiguousSubArrays {
public static void main(String[] args) {
Random rand = new Random();
int[] input = new int[20];
for(int i = 0; i < input.length; i++) {
input[i] = rand.nextInt(15);
System.out.print(input[i] + " ");
}
final int k = 10;
List<List<Integer>> contiguousSubArray = getContiguousSubArray(input, k);
List<List<Integer>> nonOverlappingPair = getNonOverlappingUnorderpai(input, k);
}
private static List<List<Integer>> getContiguousSubArray(int[] input, int k) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> subArray = new ArrayList<>();
for(int i = 0; i < input.length; i++) {
if(input[i] < k) {
subArray.add(input[i]);
}else {
if(!subArray.isEmpty()) {
result.add(subArray);
subArray = new ArrayList<>();
}
}
}
if(!subArray.isEmpty()) {
result.add(subArray);
}
return result;
}
private static List<List<Integer>> getNonOverlappingUnorderpai(int[] input, int k){
List<List<Integer>> result = new ArrayList<>();
List<Integer> pair = new ArrayList<>();
for(int i = 0; i < input.length; i++) {
if(input[i] < k) {
if(pair.size() == 2) {
result.add(pair);
pair = new ArrayList<>();
}
pair.add(input[i]);
}else {
if(pair.size() == 2) {
result.add(pair);
}
pair = new ArrayList<>();
}
}
if(pair.size() == 2) {
result.add(pair);
}
return result;
}
}
You can implement this in O(K) time and space. The approach I did was store an array of size K with all values set to 0. This will store the index for the K-th list.
The hasNext() function can be implemented by iterating through K-lists and checking if at least one of the indices is less than N. The next() function can be implemented by iterating through the K indices, and taking the index with a minimum value. The index with the minimum value is then incremented by one.
class MyIterator:
def __init__(self, lists):
self.lists = lists
self.listCount = len(lists)
self.listLen = len(lists[0])
self.indices = [0] * self.listCount
def next(self):
val = float('inf')
idx = -1
for i in range(self.listCount):
index = self.indices[i]
if index < self.listLen:
current_val = self.lists[i][index]
if current_val < val:
val = current_val
idx = i
if idx >= 0:
self.indices[idx] += 1
return val
def hasNext(self):
for i in range(self.listCount):
if self.indices[i] < self.listLen:
return True
return False
lists = [[1,5,7], [2,3,10],[4,6,9]]
it = MyIterator(lists)
while it.hasNext():
print(it.next())
class MyIter(object):
def __init__(self, ll):
self._ll = ll
def __iter__(self):
self._list_len = len(self._ll[0])
self._list_count = len(self._ll)
self._indices = [0] * self._list_count
return self
def __next__(self):
i = 0
m = int(25535)
m_ind = None
while i < self._list_count:
index = self._indices[i]
if index < self._list_len:
temp = self._ll[i][index]
if temp < m:
m = temp
m_ind = i
i += 1
if m_ind is not None:
self._indices[m_ind] += 1
return m
else:
raise StopIteration
if __name__ == '__main__':
ll = [[1,5,7], [2,3,10],[4,6,9]]
it = MyIter(ll)
print(list(it))
class MyIterator{
- Achyut January 15, 2020PriorityQueue<Integer> pq=new PriorityQueue<>();
int [][]data=null;
int []k=null;
public MyIterator(int [][] data) {
this.data=data;
k=new int[data.length];
this.preProcess(data);
}
int next(){
int tmp=pq.remove();
this.postProcess(tmp);
return tmp;
}
boolean hashNext(){
return pq.isEmpty();
}
public void preProcess(int [][]data){
for (int i = 0; i < k.length; i++) {
pq.add(data[i][k[i]]);
}
}
public void postProcess(int removedData){
for (int i = 0; i < k.length; i++) {
if(k[i]<data[i].length && data[i][k[i]]==removedData){
k[i]=k[i]+1;
if(k[i]<data[i].length){
pq.add(data[i][k[i]]);
}
return;
}
}
}
}
public class IteratorInKSortedArray {
public static void main(String[] args) {
int [][]in={
{1,5,7},
{2,3,10},
{4,6,9}
};
MyIterator itr=new MyIterator(in);
while(!itr.hashNext()){
System.out.print(itr.next()+" ");
}
}
}