Microsoft Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
public class SortedIterator<K extends Comparable> implements Iterator<K>{
private List<K> sortedList;
private int currentIdx = 0;
public SortedIterator(K[][] sortedArrays){
iterateListOfLists(sortedArrays);
}
@Override
public boolean hasNext() {
return (currentIdx < sortedList.size());
}
@Override
public K next() {
K item = null;
if(currentIdx < sortedList.size()){
item = sortedList.get(currentIdx);
currentIdx++;
}
return item;
}
private class SortedNode implements Comparable<SortedNode>{
K val;
int size;
int nextIdx;
int arrNum;
SortedNode(int arrNum, K val, int nextIdx, int size){
this.val = val;
this.nextIdx = nextIdx;
this.size = size;
this.arrNum = arrNum;
}
public int compareTo(SortedNode n){
if(n == null) return -1;
if(n.val == null && this.val == null) return 0;
if(n.val == null && this.val != null) return -1;
if(n.val != null && this.val == null) return 1;
return this.val.compareTo(n.val);
}
}
private List<K> iterateListOfLists(K[][] arr){
PriorityQueue<SortedNode> q = new PriorityQueue<SortedNode>((a, b) -> {return a.compareTo(b);});
int n = arr.length;
int size = 0;
for(int i=0; i < n; i++){ //O(n)
int m = arr[i].length;
if(m > 0 && arr[i][0] != null) {
q.offer(new SortedNode(i,arr[i][0],1, m));
}
size += m;
}
sortedList = new ArrayList<>(size);
while(!q.isEmpty()) { //O(n + m)
SortedNode next = q.poll();
sortedList.add(next.val);
int arrNum = next.arrNum;
if(next.nextIdx < next.size && arr[arrNum][next.nextIdx] != null) {
q.offer(new SortedNode(arrNum, arr[arrNum][next.nextIdx],next.nextIdx+1, next.size ));
}
}
return sortedList;
}
public static void main(String[] args) {
Integer[][] arr = {{1 ,2, 8}, {6,9,10}, {1, 4, 5 , 12 }};
SortedIterator<Integer> it = new SortedIterator(arr);
while(it.hasNext()) {
System.out.println(it.next()+"");
}
}
}
public class SortedIterator<K extends Comparable> implements Iterator<K>{
private List<K> sortedList;
private int currentIdx = 0;
public SortedIterator(K[][] sortedArrays){
iterateListOfLists(sortedArrays);
}
@Override
public boolean hasNext() {
return (currentIdx < sortedList.size());
}
@Override
public K next() {
K item = null;
if(currentIdx < sortedList.size()){
item = sortedList.get(currentIdx);
currentIdx++;
}
return item;
}
private class SortedNode implements Comparable<SortedNode>{
K val;
int size;
int nextIdx;
int arrNum;
SortedNode(int arrNum, K val, int nextIdx, int size){
this.val = val;
this.nextIdx = nextIdx;
this.size = size;
this.arrNum = arrNum;
}
public int compareTo(SortedNode n){
if(n == null) return -1;
if(n.val == null && this.val == null) return 0;
if(n.val == null && this.val != null) return -1;
if(n.val != null && this.val == null) return 1;
return this.val.compareTo(n.val);
}
}
private List<K> iterateListOfLists(K[][] arr){
PriorityQueue<SortedNode> q = new PriorityQueue<SortedNode>((a, b) -> {return a.compareTo(b);});
int n = arr.length;
int size = 0;
for(int i=0; i < n; i++){ //O(n)
int m = arr[i].length;
if(m > 0 && arr[i][0] != null) {
q.offer(new SortedNode(i,arr[i][0],1, m));
}
size += m;
}
sortedList = new ArrayList<>(size);
while(!q.isEmpty()) { //O(n + m)
SortedNode next = q.poll();
sortedList.add(next.val);
int arrNum = next.arrNum;
if(next.nextIdx < next.size && arr[arrNum][next.nextIdx] != null) {
q.offer(new SortedNode(arrNum, arr[arrNum][next.nextIdx],next.nextIdx+1, next.size ));
}
}
return sortedList;
}
public static void main(String[] args) {
Integer[][] arr = {{1 ,2, 8}, {6,9,10}, {1, 4, 5 , 12 }};
SortedIterator<Integer> it = new SortedIterator(arr);
while(it.hasNext()) {
System.out.println(it.next()+"");
}
}
}
public class SortedIterator<K extends Comparable> implements Iterator<K>{
private List<K> sortedList;
private int currentIdx = 0;
public SortedIterator(K[][] sortedArrays){
iterateListOfLists(sortedArrays);
}
@Override
public boolean hasNext() {
return (currentIdx < sortedList.size());
}
@Override
public K next() {
K item = null;
if(currentIdx < sortedList.size()){
item = sortedList.get(currentIdx);
currentIdx++;
}
return item;
}
private class SortedNode implements Comparable<SortedNode>{
K val;
int size;
int nextIdx;
int arrNum;
SortedNode(int arrNum, K val, int nextIdx, int size){
this.val = val;
this.nextIdx = nextIdx;
this.size = size;
this.arrNum = arrNum;
}
public int compareTo(SortedNode n){
if(n == null) return -1;
if(n.val == null && this.val == null) return 0;
if(n.val == null && this.val != null) return -1;
if(n.val != null && this.val == null) return 1;
return this.val.compareTo(n.val);
}
}
private List<K> iterateListOfLists(K[][] arr){
PriorityQueue<SortedNode> q = new PriorityQueue<SortedNode>((a, b) -> {return a.compareTo(b);});
int n = arr.length;
int size = 0;
for(int i=0; i < n; i++){ //O(n)
int m = arr[i].length;
if(m > 0 && arr[i][0] != null) {
q.offer(new SortedNode(i,arr[i][0],1, m));
}
size += m;
}
sortedList = new ArrayList<>(size);
while(!q.isEmpty()) { //O(n + m)
SortedNode next = q.poll();
sortedList.add(next.val);
int arrNum = next.arrNum;
if(next.nextIdx < next.size && arr[arrNum][next.nextIdx] != null) {
q.offer(new SortedNode(arrNum, arr[arrNum][next.nextIdx],next.nextIdx+1, next.size ));
}
}
return sortedList;
}
public static void main(String[] args) {
Integer[][] arr = {{1 ,2, 8}, {6,9,10}, {1, 4, 5 , 12 }};
SortedIterator<Integer> it = new SortedIterator(arr);
while(it.hasNext()) {
System.out.println(it.next()+"");
}
}
}
What's the space complexity of this algo according to you? I was asked to submit something with O(1) space complexity.
The space complexity is O(1) since the priority queue will keep only 1 item of each list at a time that should be negligible as compared to O(n).
e.g. if there are 3 lists {2, 3, 7, ,6} , {1,3,5} , {8,7,9}
In this scenario: There will be 3 items in the priority queue at max at a time, which will decrease to 2 as soon as we poll the third element of the 2nd list that is
Create a minheap of size M storing the currentIndex of each List but sorted by the value at the index. This way the as we remove the root values, we update the root key cuurentindex, thus trigerring heapify.
When we exhaust all indices of a list, the node for the list is removed from heap.
Finally heap will go empty when algo terminates
This is space O(M) -> and this will be treated constant
I am missing the point where is the extra space requirement for heap is coming from? As soon as you move the element to heap you do not have to keep it in the list so at any point in time total number of items stays the same.. if you move n items to heap then you have n less items on lists. So there is no extra space requirement...
The following implementation construct the iterator lazily and avoid storing the data before it is accessed. so still O(1)
- azrarabbani February 12, 2019public class SortedIterator<K extends Comparable> implements Iterator<K> { private int currentIdx = 0; private K[][] sortedArrays; private int size = 0; private PriorityQueue<SortedNode> q = new PriorityQueue<SortedNode>((a, b) -> {return a.compareTo(b);}); public SortedIterator(K[][] sortedArrays){ this.sortedArrays = sortedArrays; initIterator(); } @Override public boolean hasNext() { return (currentIdx < size); } @Override public K next() { K item = null; if(this.sortedArrays != null && hasNext()) { SortedNode next = q.poll(); item = next.val; int arrNum = next.arrNum; if (next.nextIdx < next.size && this.sortedArrays[arrNum][next.nextIdx] != null) { q.offer(new SortedNode(arrNum, this.sortedArrays[arrNum][next.nextIdx], next.nextIdx + 1, next.size)); } currentIdx++; } return item; } private void initIterator() { if(this.sortedArrays != null) { int n = this.sortedArrays.length; for (int i = 0; i < n; i++) { //O(n) int m = this.sortedArrays[i].length; if (m > 0 && this.sortedArrays[i][0] != null) { q.offer(new SortedNode(i, this.sortedArrays[i][0], 1, m)); } size += m; } } } public static void main(String[] args) { Integer[][] arr = {{1 ,2, 8}, {6,9,10}, {1, 4, 5 , 12 }}; SortedIterator<Integer> it = new SortedIterator(arr); while(it.hasNext()) { System.out.println(it.next()+""); } } private class SortedNode implements Comparable<SortedNode>{ K val; int size; int nextIdx; int arrNum; SortedNode(int arrNum, K val, int nextIdx, int size){ this.val = val; this.nextIdx = nextIdx; this.size = size; this.arrNum = arrNum; } public int compareTo(SortedNode n){ if(n == null) return -1; if(n.val == null && this.val == null) return 0; if(n.val == null && this.val != null) return -1; if(n.val != null && this.val == null) return 1; return this.val.compareTo(n.val); } } }