Facebook Interview Question
Country: Israel
Interview Type: Phone Interview
code for above, without the duplicate extension
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Iterator
{
private:
const vector<vector<int>> arrays_; // (lame) copy of input arrays
vector<pair<size_t, size_t>> offsets_; // array-idx, array-pos
struct HeapComparer {
Iterator* it_;
HeapComparer(Iterator* it) : it_(it) { }
bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
return it_->arrays_[a.first][a.second] > it_->arrays_[b.first][b.second];
}
};
public:
Iterator(const vector<vector<int>>& arrays) : arrays_(arrays) {
reset();
}
bool hasNext() const { return offsets_.size() > 0; }
int getNext() {
pop_heap(offsets_.begin(), offsets_.end(), HeapComparer(this));
pair<int, int> smallest = offsets_.back();
if (smallest.second < arrays_[smallest.first].size() - 1) {
offsets_.back().second++; // more to fetch
push_heap(offsets_.begin(), offsets_.end(), HeapComparer(this)); // bubble element up (O(lg(m))
} else {
offsets_.pop_back(); // this array is exceeded
}
return arrays_[smallest.first][smallest.second];
}
void reset() {
for (size_t i = 0; i < arrays_.size(); ++i) {
if (arrays_[i].size() > 0) {
offsets_.push_back({ i, 0 });
}
}
make_heap(offsets_.begin(), offsets_.end(), HeapComparer(this));
}
};
int main()
{
Iterator it({ {1,2,3,4,5,10},{2,2,7,7,11},{0,9},{6,22} });
while (it.hasNext()) {
cout << it.getNext() << ", ";
}
}
package rough;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class NextInLine {
int[][] arrs;
int[] indexes = null;
int n = 0;
Queue<Integer> queue;
Integer prev = null;
boolean removeDuplicate;
public NextInLine( boolean removeDuplicate, int[]... arrs) {
this.n = arrs.length;
this.arrs = arrs;
indexes = new int[n];
queue = new LinkedList<Integer>();
this.removeDuplicate = removeDuplicate;
}
public Integer getNext() {
List<Integer> kList = new ArrayList<>();
while (!queue.isEmpty()) {
kList.add(queue.poll());
}
for (int i = 0; i < n; i++) {
if(arrs[i].length > indexes[i]){
kList.add(arrs[i][indexes[i]]);
}
indexes[i] += 1;
}
Integer[] arr = kList.toArray(new Integer[kList.size()]);
minHeap(arr);
for (int i = 0; i < arr.length; i++)
queue.add(arr[i]);
if (!removeDuplicate && !queue.isEmpty()){
return queue.poll();
}else if(!queue.isEmpty()){
int poll = queue.poll();
if(prev == null || (prev != null && poll != prev)){
prev = poll;
return poll;
}
return getNext();
}
return null;
}
private void minHeap(Integer[] arr) {
int n = arr.length;
while (n > 0) {
if ((n / 2) > 0 && arr[n - 1] < arr[(n / 2) - 1]) {
swap(arr, (n - 1), ((n / 2) - 1));
minHeap(arr);
}
n--;
}
}
private void swap(Integer[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
NextInLine nxtLine = new NextInLine(true, new int[] { 1, 2, 3, 4, 7, 9 }, new int[] { 3, 5, 6, 8, 10 });
Integer n = -1;
while (n != null) {
n = nxtLine.getNext();
if(n != null)
System.out.print(n + " ");
}
}
}
package rough;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class NextInLine {
int[][] arrs;
int[] indexes = null;
int n = 0;
Queue<Integer> queue;
Integer prev = null;
boolean removeDuplicate;
public NextInLine( boolean removeDuplicate, int[]... arrs) {
this.n = arrs.length;
this.arrs = arrs;
indexes = new int[n];
queue = new LinkedList<Integer>();
this.removeDuplicate = removeDuplicate;
}
public Integer getNext() {
List<Integer> kList = new ArrayList<>();
while (!queue.isEmpty()) {
kList.add(queue.poll());
}
for (int i = 0; i < n; i++) {
if(arrs[i].length > indexes[i]){
kList.add(arrs[i][indexes[i]]);
}
indexes[i] += 1;
}
Integer[] arr = kList.toArray(new Integer[kList.size()]);
minHeap(arr);
for (int i = 0; i < arr.length; i++)
queue.add(arr[i]);
if (!removeDuplicate && !queue.isEmpty()){
return queue.poll();
}else if(!queue.isEmpty()){
int poll = queue.poll();
if(prev == null || (prev != null && poll != prev)){
prev = poll;
return poll;
}
return getNext();
}
return null;
}
private void minHeap(Integer[] arr) {
int n = arr.length;
while (n > 0) {
if ((n / 2) > 0 && arr[n - 1] < arr[(n / 2) - 1]) {
swap(arr, (n - 1), ((n / 2) - 1));
minHeap(arr);
}
n--;
}
}
private void swap(Integer[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
NextInLine nxtLine = new NextInLine(true, new int[] { 1, 2, 3, 4, 7, 9 }, new int[] { 3, 5, 6, 8, 10 });
Integer n = -1;
while (n != null) {
n = nxtLine.getNext();
if(n != null)
System.out.print(n + " ");
}
}
}
#include <vector>
#include <unordered_set>
#include <queue>
#include <iostream>
using namespace std;
class Iterator {
public:
Iterator(vector<vector<int>> const *a)
{
a_ = a;
idxes_.resize(a_->size(), 0);
for (int i = 0; i < a_->size(); ++i) {
Enqueue(i);
}
val_ = 0;
done_ = false;
GetNext();
}
int Value() const
{
return val_;
}
int operator++()
{
GetNext();
return val_;
}
bool Done() const
{
return done_;
}
private:
class PQElement {
public:
PQElement(int val, int idx)
{
val_ = val;
idx_ = idx;
}
bool operator>(PQElement const &other) const
{
return val_ > other.val_;
}
int val_, idx_;
};
void GetNext()
{
if (pq_.empty()) {
done_ = true;
return;
}
PQElement el = pq_.top();
pq_.pop();
pq_vals_.erase(el.val_);
val_ = el.val_;
while (idxes_[el.idx_] < (*a_)[el.idx_].size()) {
if (Enqueue(el.idx_)) {
break;
}
}
}
bool Enqueue(int i)
{
bool enqueued = false;
if (idxes_[i] < (*a_)[i].size()) {
if (pq_vals_.find((*a_)[i][idxes_[i]]) == pq_vals_.end()) {
pq_.push(PQElement((*a_)[i][idxes_[i]], i));
pq_vals_.insert((*a_)[i][idxes_[i]]);
enqueued = true;
}
idxes_[i]++;
}
return enqueued;
}
vector<vector<int>> const *a_;
vector<int> idxes_;
priority_queue<PQElement, vector<PQElement>, greater<PQElement>> pq_;
unordered_set<int> pq_vals_;
int val_;
bool done_;
};
int main()
{
vector<vector<int>> a = {
{1,2,3,4,7,9},
{3,5,6,8,10}
};
for (Iterator it = Iterator(&a); !it.Done(); ++it) {
cout << it.Value() << ",";
}
cout << "\n";
return 0;
}
edit: cleaned up code
The idea with returning only unique elements is to prevent duplicates from entering
the heap, because when there, they are ordered O(log(m)) just to be ignored (which is unnecessary work).
I did it using a set, containing all "next-values" of the current positions in the
arrays (probably streams in reality). When advancing in an array, I check if the
element I am about to put into the heap is already in the set. If so, I advance further
until I find an element that is not already in the heap. This way, to skip a single duplicate
takes O(1) vs. O(lg(m)) when entering the heap.
#include <vector>
#include <algorithm>
#include <iostream>
#include <unordered_set>
#include <cassert>
using namespace std;
class Iterator
{
private:
// struct that is uses within the heap, contains a reference to the "array"
// and it's current position (basically a reference to a stream)
struct StreamRef
{
const vector<int>* array_; // reference to array
size_t pos_; // index index in array
void next() { pos_++; }
bool isValid() const { return pos_ < array_->size(); }
int value() const { return array_->at(pos_); }
bool operator < (const StreamRef& rhs) const { return value() > rhs.value(); }
};
vector<vector<int>> arrays_; // copy of arrays to "simulate" streams
vector<StreamRef> streams_; // heap of streams
unordered_set<int> headValues_; // all valid values of current stream-positions
public:
Iterator(const vector<vector<int>>& arrays) : arrays_(arrays) {
for (auto& arr : arrays_) {
StreamRef first{ &arr, static_cast<size_t>(-1) };
if (advanceToNextUniqueValue(first)) streams_.push_back(first);
}
make_heap(streams_.begin(), streams_.end());
}
// is there a next element
bool hasNext() const { return streams_.size() > 0; }
// get next element
int getNext()
{
assert(hasNext());
pop_heap(streams_.begin(), streams_.end());
auto& next = streams_.back();
int current = next.value();
if (advanceToNextUniqueValue(next)) push_heap(streams_.begin(), streams_.end());
else streams_.pop_back(); // this stream is exceeded
return current;
}
private:
// advances stream until it encounters an element that is not already in
// the heap. Maintains the headValues_ set containing all values in the heap
bool advanceToNextUniqueValue(StreamRef& e)
{
bool removePrevious = e.isValid();
int previousValue = removePrevious ? e.value() : 0;
do { e.next(); } while (e.isValid() && headValues_.count(e.value()) > 0);
if (removePrevious) headValues_.erase(previousValue);
if (e.isValid()) headValues_.insert(e.value());
return e.isValid();
}
};
int main()
{
Iterator it({ {1,2,3,4,5,10},{1,2,2,7,7,11},{0,9},{6,22},{-1,-1,-1,-1,-1} });
while (it.hasNext()) {
cout << it.getNext() << ", ";
}
}
class SortedArrayIterator
{
private List<int[]> sortedArrays;
private int[] currentIndexes;
public SortedArrayIterator(List<int []> sortedArrays)
{
this.sortedArrays = sortedArrays;
currentIndexes = new int[sortedArrays.Count];
}
public int? GetNext()
{
int minValue = int.MaxValue;
int indexForArray = -1;
for (int i = 0; i < currentIndexes.Length; i++)
{
int currentIndexForThisArray = currentIndexes[i];
if (currentIndexForThisArray < sortedArrays[i].Length)
{
int value = sortedArrays[i][currentIndexForThisArray];
if (value < minValue)
{
minValue = value;
indexForArray = i;
}
}
}
if (indexForArray != -1)
{
currentIndexes[indexForArray] = currentIndexes[indexForArray] + 1;
return minValue;
}
else
{
return null;
}
}
}
javascript solution with ES6 feauture
compare = (a, b) => {
return a - b;
};
test = (ar, ra) => {
let arr = [...ar,...ra];
return [...(new Set(arr.sort(compare)))];
}
2nd Method
m = (A,B) => {
let arr = [];
while (A.length > 0 || B.length > 0) {
if (B.length < 0 || (A.length > 0 && A[0] < B[0]))
arr.push(A.shift());
else
arr.push(B.shift());
}
return arr[...(new Set(arr.sort(compare)))];
}
import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Set;
import java.util.HashSet;
public class KSortedArrayIterator implements Iterator
{
//use priority queue to maintain the values in order
Queue<Value> pq;
List<Integer[]> kSortedList;
boolean removeDuplicates;
//to remove duplicates
Set<Integer> set;
public KSortedArrayIterator(List<Integer[]> kSortedList, boolean removeDuplicates)
{
this.pq = new PriorityQueue<Value>(10, new Value(0,0,0));
this.kSortedList = kSortedList;
this.removeDuplicates = removeDuplicates;
this.set = new HashSet<>();
if(this.kSortedList!=null && !this.kSortedList.isEmpty())
{
for(int i=0;i<this.kSortedList.size();i++)
{
Integer[] arr = this.kSortedList.get(i);
int index = 0;
while(this.removeDuplicates && index < arr.length && set.contains(arr[0]))
index++;
if(index < arr.length)
{
pq.offer(new Value(arr[index], i, index));
if(this.removeDuplicates)
set.add(arr[index]);
}
}
}
}
public static void main(String[] args)
{
List<Integer[]> list = new ArrayList<>();
Integer[] a = new Integer[]{1, 2, 3, 4, 7, 9 };
Integer[] b = new Integer[]{3, 5, 6, 8, 10};
Integer[] c = new Integer[]{1, 2, 3};
list.add(a);
list.add(b);
list.add(c);
KSortedArrayIterator k = new KSortedArrayIterator(list, false);
while(k.hasNext())
{
//System.out.println(k.pq);
System.out.println(k.next());
}
}
public Object next()
{
Value v = pq.poll();
Integer[] a = kSortedList.get(v.arrIndex);
int index= v.elementIndex+1;
while(this.removeDuplicates && index < a.length && set.contains(a[index]))
{
index++;
}
if(index < a.length)
{
pq.offer(new Value(a[index], v.arrIndex, index));
if(this.removeDuplicates)
set.add(a[index]);
}
return v.val;
}
public boolean hasNext()
{
return !this.pq.isEmpty();
}
}
class Value implements Comparator<Value>
{
int val;
int arrIndex;
int elementIndex;
public Value(int val, int arrIndex, int elementIndex)
{
this.val = val;
this.arrIndex = arrIndex;
this.elementIndex = elementIndex;
}
@Override
public int compare(Value a, Value b)
{
return Integer.compare(a.val, b.val);
}
@Override
public String toString()
{
return this.val+"|"+this.arrIndex+"|"+this.elementIndex;
}
}
public class IteratorArray {
public static void main(String[] argv) {
int[] arr1 = {1,2,3,4, 4,7,9};
int[] arr2 = {3,4, 5,6,8,10};
IteratorArray ia = new IteratorArray(arr1, arr2);
while (ia.hasNext()) {
System.out.println(ia.next());
}
}
int[] A;
int[] B;
int Ai;
int Bi;
Integer pre;
IteratorArray(int[] arr1, int[] arr2) {
A = arr1;
B = arr2;
}
int next() {
int res;
if (Ai >= A.length) {
return B[Bi++];
}
if (Bi >= B.length) {
return A[Ai++];
}
if (A[Ai] <= B[Bi]) {
res = A[Ai++];
} else {
res = B[Bi++];
}
if (pre == null) {
pre = res;
return res;
} else if (pre == res){
//return res;
return next();
} else {
pre = res;
return res;
}
}
boolean hasNext() {
return Ai < A.length || Bi < B.length;
}
}
binary heap, to select next lowest element. In the heap there must be all next elements of the m arrays and a pointer or index to the array, so when accessing the top of min heap one can as well access the array and fetch the next element if not at end.
- Chris September 29, 20171) O(m*lg(m)) to build the heap first time, assuming m is the number of arrays
2) in each iteration O(lg(m)) is required for "heapify"
3) total time is O(n*lg(m)) assuming n is the number of all distinct elements in the arrays
to remove duplicates, it's when taking an element compare it against the last element fetched. This is inefficient when long sequences with same values exists. So, we should skip elements when inserting to the heap (when fetching the next element from the array). If very long sequences of equal elements are expected, we could try some binary search approach to skip elements from the input array. Maybe implement a cache friendly version of this.