## Google Interview Question for Software Engineers

Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

This solution does not have any additional memory requirements. No heap, array needed.
Space complexity = 1
Time complexity = nk or more specifically n*(k^2) where k is number of streams (small number) and n is number of elements in a stream (worst case - number of elements in the longest stream.

1. K streams; read the first element of the first non-empty stream
2. Compare it with the first element of all streams. Find the smallest. Store the pointer to the stream to which the smallest number belongs to
3. Pop out the first element from the stream to which pointer points to.
4. Keep on doing until all streams are empty.

``````public class MergeSortedStreamsDemo {
static ArrayList<Integer> mergeStreams(ArrayList<ArrayList<Integer>> streams) {

ArrayList<Integer> resultStream = new ArrayList<>();
int streamPointer = 0;

int numberOfStreams = streams.size();
int emptyStreams = 0;
int numberToBeKickedOut = Integer.MAX_VALUE;

while (emptyStreams != numberOfStreams) {

emptyStreams = 0;  //set empty stream to 0 everytime
//Get the first element of first non-empty stream
for(int i = 0; i < numberOfStreams; i++) {
if(streams.get(i).size() != 0) {
numberToBeKickedOut = streams.get(i).get(0);  //Just peek the value
streamPointer = i;      //stream number needs to be remembered, for the pop operation later
break;
} else {
emptyStreams += 1;
if(emptyStreams == numberOfStreams) return resultStream;
}
}
for (int i = 0; i < numberOfStreams; i++) {
ArrayList<Integer> stream = streams.get(i);
if (stream.size() != 0) {
if (numberToBeKickedOut > stream.get(0)) {
numberToBeKickedOut = stream.get(0);  //peek the value
streamPointer = i;                    //stream number to for pop operation later
}
}
}
resultStream.add(streams.get(streamPointer).remove(0));    //Pop the value and put it in the result stream
//            streamPointer = 0;
}

return resultStream;
}

public static void main(String[] args) {
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
ArrayList<Integer> list3 = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> inputStreams = new ArrayList<>();
System.out.println(mergeStreams(inputStreams));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use min heap to hold M values from M sorted arrays, O(N*log M), N total number of elements

``````static class Row<T> {
Iterator<T> aRow;
T currentValue;

public Row(Iterator<T> aRow) {
this.aRow = aRow;
// currentValue is undefined
}

T getV() {return currentValue ;}

if (aRow.hasNext()) {
currentValue = aRow.next();
return true;
} else {
return false;
}
}

@Override
public String toString() {
return  currentValue + ":" + aRow.hasNext();

}
}
@SafeVarargs
static <T extends Comparable<T>> void merge(Consumer<T> downStream,
Collection<T> ... sources) {

PriorityQueue<Row<T>> heap = new PriorityQueue<>(sources.length,
Comparator.comparing(Row::getV));

for (Collection<T> it : sources) {

Row<T> row = new Row<>(it.iterator());
// row has any data?
}
}

while(! heap.isEmpty()) {
Row<T> row = heap.remove();
downStream.accept(row.getV());

// row has more data ?
}
}
}

public static void main(String[] args) {

List<Integer> l1 = Arrays.asList(1,3, 6, 10);
List<Integer> l2 = Arrays.asList(3,3, 10, 20);
List<Integer> l3 = Arrays.asList(1,1, 3);
List<Integer> l4 = Collections.emptyList();

merge(System.out::println, l1, l2, l3, l4);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A straightforward way is to use TreeSet. Build a N elements treeset uses O(nlogn) time.
With treeset, we don't need even require the 2 streams are sorted. I'm guessing should be a much better way.

Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.
Complexity: less than O(n*log n).
I use the merging part of MergeSort algorithm. (According to the task - all the arrays are sorted.)
As the complexity of the whole MergeSort algorithm is O(n*log n), so the solution is at least not worse, and even faster, due to the absence of sorting step.

``````using System;
using System.Collections.Generic;

namespace MergeOfSortedArrays {

static class Program {

private static int[] Merge( int[] arr1, int[] arr2, SortOrder sortOrder ) {

if ( arr1 == null ) { return arr2; }
if ( arr2 == null ) { return arr1; }

int[] tail = null;

if ( arr1.Length > 1 ) {
tail = new int[arr1.Length - 1];
}

if ( GetConditionWithSortOrder( arr1[ 0 ], arr2[ 0 ], sortOrder) ) {
for ( int i = 0; i + 1 < arr1.Length; i++ ) {
tail[ i ] = arr1[ i + 1 ];
}
return Concat( arr1[ 0 ], Merge( tail, arr2, sortOrder) );
}

tail = null;
if ( arr2.Length > 1 ) {
tail = new int[arr2.Length - 1];
}

for ( int i = 0; i + 1 < arr2.Length; i++ ) {
tail[i] = arr2[ i + 1 ];
}
return Concat( arr2[ 0 ], Merge( arr1, tail, sortOrder ) );
}

private static bool GetConditionWithSortOrder( int i1, int i2, SortOrder sortOrder ) {
return sortOrder.Equals(SortOrder.Desc) ? i1 > i2 : i1 < i2;
}

private static int[] Concat( int firstElm, int[] arr ) {

var res = new int[ arr.Length + 1 ];
res[ 0 ] = firstElm;

for ( int i = 0; i < arr.Length; i++ ) {
res[ i + 1 ] = arr[ i ];
}
return res;
}

static void Main(string[] args) {

foreach ( var arr in GetResult() ) {
for ( int i = 0; i < arr.Length; i++ ) {
Console.Write( \$"{arr[i]} " );
}
Console.WriteLine(\$"{Environment.NewLine}-------------------------------");
}
}

private static IEnumerable<int[]> GetResult() {

var listOfArrays = new List<int[]> ();

while ( listOfArrays.Count < 11 ) {

var order = SortOrder.Asc;
listOfArrays.Add( GetNewSortedArrayFromStream( order ) );

int[] res = null;
foreach ( var item in listOfArrays ) {
res = Merge( res, item, order );
}

yield return res;
}
}

private static int[] GetNewSortedArrayFromStream( SortOrder order ) {

Random rand = new Random();
var startVal = rand.Next( 0, 101 );
var step = rand.Next( 1, 20 );
var length = rand.Next( 3, 10 );

var arr = new int[ length ];
for ( int i = 0; i < length; i++ ) {
arr[ i ] = startVal + ( order.Equals( SortOrder.Asc ) ? i : -i ) * step;
}
return arr;
}

}

public enum SortOrder {
Asc,
Desc
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

If I relax stream and array keyword from the question , it translates into common problem of merging 2 sorted linked list.

``````// Program to merge 2 sorted list

}
}
else {
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I'd use some sort of heap with a reasonably fast merge operation that can be constructed fast from a sorted array.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.