Facebook Interview Question for iOS Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 7 vote

I see two possible approaches for this :

* Merge the lists by two, then the results by two etc... If there are K lists of total size N, the complexity is O(N * logK)
* Merge all the arrays at once. Create a heap from the first elements of the lists. Take the minimum from the heap, shift the index of the appropriate array and add a new item from the array. Repeat until the heap is empty. It also runs in O(N * logK).

- Danstahr April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Take N elements (first elements from N lists), make them a Heap (logN) i.e N * log N)
Then Remove the items one by one (again a logN operation) -> logN + Log N-1 - log 2 ~ O(logN) N times.
Till now it is total NlogN Then this will be done K times
= O(KN logN)

- byteattack May 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, I believe your first answer is not O(N*logk). For example, K= 100 of size 20:

100 -->merge to 50 of size 40 ea --> 25 of size 80 ea-->
12 of size 160 ea --> 6 of size 320 ea --> 3 of size 640 --> ...

50 + 25 + 12 + 6 + 3 + 2 +1 = 99 = K
Not to mention that the size at each step doubles so each step requires double the work.

So your solution is actually O(N*K)

- naji247 October 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

This problem is part of the "merge sort" algorithm. We only need to code the reunion of each subarray recursively:

- (NSArray*)mergeSortUp:(NSArray*)lists
{
    if (lists.count == 0)
        return nil;
    
    if (lists.count == 1)
        return lists.firstObject;
    
    NSMutableArray *newLists = [NSMutableArray arrayWithCapacity:(lists.count/2+1)];
    
    for (NSInteger i=0; i<lists.count-1; i+=2)
    {
        NSArray *list1 = lists[i];
        NSArray *list2 = lists[i+1];
        
        NSMutableArray *group = [NSMutableArray arrayWithCapacity:list1.count + list2.count];
        
        NSInteger idx1 = 0;
        NSInteger idx2 = 0;
        
        while (idx1 < list1.count && idx2 < list2.count)
        {
            NSInteger value1 = [list1[idx1] integerValue];
            NSInteger value2 = [list2[idx2] integerValue];
            
            if (value1 < value2)
            {
                [group addObject:list1[idx1]];
                idx1++;
            }
            else
            {
                [group addObject:list2[idx2]];
                idx2++;
            }
        }
        
        if (idx1 < list1.count)
            [group addObjectsFromArray:[list1 subarrayWithRange:NSMakeRange(idx1, list1.count-idx1)]];
        
        if (idx2 < list2.count)
            [group addObjectsFromArray:[list2 subarrayWithRange:NSMakeRange(idx2, list2.count-idx2)]];
        
        [newLists addObject:group];
    }
    
    if (lists.count % 2 == 1)
        [newLists addObject:lists.lastObject];
    
    return [self mergeSortUp:newLists];
}

- Anonymous November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And actually, you can call the method with multiple array dimensions:

NSArray *output = [self mergeSortUp:@[@[@12,@19,@22],
                                          @[@02,@15,@19],
                                          @[@44,@56,@77,@79],
                                          @[@24,@25,@40,@91,@94],
                                          @[@13,@33,@42],
                                          @[@14,@35,@46],
                                          @[@16],
                                          @[@31],
                                          @[@9],
                                          ]];

And, because it is based on the merge sort, you have O(nlogn) in performance.

- vilanovi November 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class SortedListExample {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		 List<Integer> l1 = new ArrayList<Integer>();
		 l1.add(2);
		 l1.add(5);
		 l1.add(10);
		 
		 List l2 = new ArrayList<Integer>();
		 l2.add(25);
		 l2.add(10);
		 l2.add(105);
		 
		 List l3 = new ArrayList<Integer>();
		 l3.add(7);
		 l3.add(56);
		 l3.add(42);
		 
		 l1.addAll(l2);
		 l1.addAll(l3);
		 
		 Set sortedSet = new TreeSet<Integer>();
		 for (Object object : l1) {
			 Integer i = (Integer)object;
			 sortedSet.add(i);
		}
		 
		System.out.println("Complete sorted list "+ sortedSet);
	
		Collections.sort(l1);
		System.out.println("Using collection to sort "+ l1);

	}

}

- Anonymous April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Without using specialized collections/data structures (of course).

- valheru April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

NSMutableArray *a = [[NSMutableArray alloc] initWithCapacity:30];
        for (NSArray *t in input) {
            [a addObjectsFromArray:t];
        }
        NSArray *b = [a sortedArrayUsingComparator:^NSComparisonResult(NSNumber *obj1, NSNumber *obj2) {
            return [obj1 compare:obj2];
        }];

- peeterparker April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the class for

MinHeapNode

#import <Foundation/Foundation.h>

@interface MinHeapNode : NSObject
@property (nonatomic, strong) NSNumber *num;
@property (nonatomic, assign) NSInteger arrayIndex;
@property (nonatomic, assign) NSInteger nextElement;
@end

Next is the

MinHeap

class required for storing the data.

#import <Foundation/Foundation.h>
#import "MinHeapNode.h"

@interface MinHeap : NSObject

- (id)initWithSize:(NSInteger)size;
- (void)add:(MinHeapNode *)a;
- (MinHeapNode *)findMin;
- (MinHeapNode *)deleteMin;
- (void) heapify;
- (BOOL)isEmpty;
- (void) printHeap;
@end

Next is the

MinHeap

implementation

#import "MinHeap.h"

@interface MinHeap() {
    NSMutableArray *array;
}

@end
@implementation MinHeap

- (id)initWithSize:(NSInteger)size {
    self = [super init];
    if (self) {
        array = [NSMutableArray arrayWithCapacity:size];
    }
    return self;
}

- (void)add:(MinHeapNode *)a {
    [array addObject:a];
    
    if ([array count] == 1) return;
    
    NSInteger i = [array count] - 1;
    NSInteger p = 0;
    while (i >=0 ) {
        p = (i - 1)/2;
        MinHeapNode *a = [array objectAtIndex:i];
        MinHeapNode *b = [array objectAtIndex:p];
        if ([a.num integerValue] < [b.num integerValue]) {
            [self swap:p with:i];
        } else {
            break;
        }
        i = p;
    }
}

- (void) heapify {
    NSInteger i = 0;
    while (i < [array count]) {
        MinHeapNode *min = nil;
        if ([self right:i] < [array count]) {
            MinHeapNode *a = [array objectAtIndex:[self left:i]];
            MinHeapNode *b = [array objectAtIndex:[self right:i]];
            if (a.num < b.num) {
                min = a;
            } else {
                min = b;
            }
        } else {
             min = [array objectAtIndex:[self left:i]];
        }
        MinHeapNode *f = [array objectAtIndex:i];
        if ([f.num integerValue] > [min.num integerValue]) {
            NSInteger k = [array indexOfObject:min];
            [self swap:i with:k];
            i = k;
        } else {
            break;
        }
        
        if ([self left:i] > [array count] || [self right:i] > [array count]) {
            break;
        }
    }
}

- (NSInteger)left:(NSInteger)i {
    return 2*i + 1;
}

- (NSInteger)right:(NSInteger)i {
    return 2*i + 2;
}

- (MinHeapNode *)findMin {
    if ([array count] == 0) {
        return nil;
    } else {
        return [array firstObject];
    }
}

- (MinHeapNode *)deleteMin {
    if ([array count] > 2) {
        MinHeapNode *min = [array firstObject];
        MinHeapNode *last = [array lastObject];
        [array removeLastObject];
        [array replaceObjectAtIndex:0 withObject:last];
        [self heapify];
        return min;
    } else if ([array count] == 2) {
        MinHeapNode *min = [array firstObject];
        [array removeObjectAtIndex:0];
        return min;
    } else if ([array count] == 1) {
        MinHeapNode *min = [array firstObject];
        [array removeLastObject];
        return min;
    }
    return nil;
}

- (void)swap:(NSInteger)i with:(NSInteger)j {
    MinHeapNode *t = [array objectAtIndex:i];
    [array replaceObjectAtIndex:i withObject:[array objectAtIndex:j]];
    [array replaceObjectAtIndex:j withObject:t];
}

- (BOOL)isEmpty {
    return [array count] == 0;
}

- (void) printHeap {
    for (MinHeapNode *n in array) {
        printf("%d ", [n.num intValue]);
    }
    printf("\n");
}

@end

Finally the method to mergeSort the arrays

void mergeArrays(NSArray *arrays) {
    //k be number of arrays that are present.
    //n be number of elements in each array;
    
    if ([arrays count] == 1) {
        NSLog(@"%@", [arrays firstObject]);
    } else {
        NSInteger k = [arrays count];
        NSInteger n = [[arrays firstObject] count];
        
        MinHeap *minHeap = [[MinHeap alloc] initWithSize:k];
        NSMutableArray *temp = [NSMutableArray arrayWithCapacity:n*k];
        
        for (int i=0; i< k;i++) {
            MinHeapNode *t = [[MinHeapNode alloc] init];
            t.num = [[arrays objectAtIndex:i] objectAtIndex:0];
            t.arrayIndex = i;
            t.nextElement = 1;
            [minHeap add:t];
        }
        
        for (int i=0; i < n*k;i++) {
            MinHeapNode *t = [minHeap findMin];
            [temp addObject:t.num];
            if (t.nextElement < n) {
                t.num = [[arrays objectAtIndex:t.arrayIndex] objectAtIndex:t.nextElement];
                t.nextElement +=1;
            } else {
                t.num = [NSNumber numberWithInt:INT32_MAX];
            }
            [minHeap heapify];
        }
        
        NSLog(@"%@", temp);
    }
}

- peeterparker April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It’s not clear what additional limitations are supposed to be taken into account, if there are no constraints and Foundation can be used then solution is fairly simple.

@import Foundation;

NSArray *mergedAndSortedArrayForArrays(NSArray* arrays) {
  NSMutableSet* elements = [NSMutableSet set];
  for (NSArray* array in arrays) {
    assert([array isKindOfClass:[NSArray class]]);
    [elements addObjectsFromArray:array];
  }

  NSSortDescriptor* sortDescriptor = [NSSortDescriptor
      sortDescriptorWithKey:nil ascending:YES];
  return [elements sortedArrayUsingDescriptors:@[ sortDescriptor ]];
}

- vmagaziy April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If any of the list contained duplicates, you lost some numbers when u went from NSArray to NSSet.

Also, I'd guess a more impressive answer would swap elements manually, not use a built in method for sorting - that's kind of implied with most questions.

- Mike P November 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

vmagaziy 's solution is impressive!

I have a solution is more algorithm involved.

- (NSArray *)mergeArray:(NSArray *)arr {
    NSMutableArray *mArr = [arr mutableCopy];
	while (mArr.count >1) {
        NSMutableArray *result = [NSMutableArray array];
		for (int i =0; i<mArr.count/2; i++) {
			NSMutableArray *arr0 = mArr[2*i];
			NSMutableArray *arr1 = mArr[2*i+1];
			NSMutableArray *merge = [[NSMutableArray alloc] initWithCapacity:arr0.count+arr1.count];
			int i0 =0;
			int i1 =0;
			while (i0 < arr0.count || i1 < arr1.count) {
				if (i0==arr0.count || arr1[i1]<arr0[i0]) {
					[merge addObject:arr1[i1++]];
				} else {
					[merge addObject:arr0[i0++]];
				}
			}
			[result addObject:merge];
		}
        mArr = result;
	}
	return mArr[0];
}

- read010931 May 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Merging two lists at a time. The solution is O(N). Where N is the total number of elements.

def merge(l1,l2):
    len1 = len(l1)-1
    len2 = len(l2)-1
    #expand the l1 to the size of l1+l2
    l1.extend([None]*(len2+1))
    #Traverse in reverse.
    for index in range(len(l1))[::-1]: 
        if len1<0 or len2<0:
            break
        if l1[len1] >= l2[len2]:
            l1[index] = l1[len1]
            len1-=1
        else:
            l1[index] = l2[len2]
            len2-=1
        return l1

def sortList(lol):
    mainl = lol[0]
    for l in range(1,len(lol)):
        mainl = merge(mainl,lol[l])
    return mainl

input = [ [2, 5, 10], [25, 100, 105], [7, 56, 42]] 
print sortList(input)

- maitreyak May 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it will be N^3/2 (assuming that each row has approx sqrt(N) elements).

- cool.fire.ra May 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do this in O(N) where N is total number of elements.

1. Draw the smallest element from the head of each of each row.
2. Update the head to next element for the element that was last drawn.
3. write to output array.
4. repeat until all elements are read.

public class nWayMerge{

public static void main(String[] args){
	int[][] a = new int[][] {{2,5,6},{1,4},{3,11}};
	doNWayMerge(a);
}
	
public static int[] doNWayMerge(int[][] a){
	
int numRows = a.length;
int[] numCols = new int[numRows];
int totalLen = 0;
for (int i=0;i<numRows; i++){
	numCols[i] = a[i].length;
	totalLen += a[i].length;
}

int[] b = new int[totalLen];

int[] colInd = new int[numRows];
for (int i=0;i<numRows; i++){
	colInd[i] = 0;
}

//actual sorting part
while(1){
int nextMin = Integer.MAX_VALUE, nextMinRow=-1;
	for (int i=0; i<numRows; i++){
if(colInd[i] < numCols[i]){
	if(nextMin > a[i][colInd[i]]){
		nextMin = a[i][colInd[i]];
		nextMinRow = i;
	}
}
	}
	if(nextMinRow == -1){
		//no more remaining elements.
		break;
	}
else{
	b[j] = nextMin;
	colInd[nextMinRow ] = colInd[nextMinRow ]+1;
}
	
}
return b;

}

}

- cool.fire.ra May 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DialPad {
	private static HashMap<Integer, List<String>> dictionary = new HashMap<Integer, List<String>>();
	
	public static void printWord(List<Integer> phoneNum, String str, int idx) {
		if (phoneNum.size() == idx) {
			System.out.println(str);
			return;
		}
		
		Integer key = phoneNum.get(idx);
		
		for (String s : dictionary.get(key)) {
			printWord(phoneNum, str+s, idx+1);
		}
	}
	
	public static void main(String[] args) {
		dictionary.put(2, Arrays.asList("A","B","C"));
		dictionary.put(3, Arrays.asList("D","E","F"));
		dictionary.put(4, Arrays.asList("G","H","I"));
		dictionary.put(5, Arrays.asList("J","K","L"));
		dictionary.put(6, Arrays.asList("M","N","O"));
		dictionary.put(7, Arrays.asList("P","Q","R","S"));
		dictionary.put(8, Arrays.asList("T","U","V"));
		dictionary.put(9, Arrays.asList("X","Y","Z"));
		
		printWord(Arrays.asList(2,3,4), "",0);
	}
}

- Anonymous June 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Standard algorithm : k-way merge sort

- smashit June 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And we can use a priority queue or a heap to keep iterators of all individual arrays. It's O(n*log(k)). n be the total number of integers, k be the number of arrays. Each time when an iterator advances, its next position in heap/priority queue can be determined by insertion with log(k) complexity.

- sabz August 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

class mergeSort{
	public static void main(String[] args) {
		
		LinkedList<int[]> arrs = new LinkedList<int[]>();
		arrs.add(new int[]{1,2,3});
		arrs.add(new int[]{7,8,9});
		arrs.add(new int[]{4,5,6});
		arrs.add(new int[]{10,11,12});
		arrs.add(new int[]{4,9,12});

		while(arrs.size()>1){
			int[] first = arrs.pop();
			int[] second = arrs.pop();

			printArr("first",first);
			printArr("second",second);

			int[] result = merge(first, second);
			printArr("result",result);
			arrs.push(result);
		}		
		
	}

	static void printArr(String name, int[] arr){
		System.out.print(name+": ");
		for (int i=0; i<arr.length;i++) {
			System.out.print(arr[i]);
		}
		System.out.println();
	}

	static int[] merge(int[] first_arr, int[] second_arr){
		int first=0;
		int second=0;

		int offset = 0;
		int[] result = new int[first_arr.length+second_arr.length];

		while(first<first_arr.length && second<second_arr.length){
			if(first_arr[first] < second_arr[second]){
				result[offset++] = first_arr[first++];				
			} else if(first_arr[first] > second_arr[second]){
				result[offset++] = second_arr[second++];				
			} else {
				result[offset++] = second_arr[second++];				
				result[offset++] = first_arr[first++];				
			}
		}

		while(first<first_arr.length)
			result[offset++] = first_arr[first++];

		while(second<second_arr.length)
			result[offset++] = second_arr[second++];

		return result;
	}
}

- idan June 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- (void)sortAndMergeArrayOfArrays:(NSArray *)arrays
{
    NSLog(@"original : %@",arrays);
    NSMutableArray *merged = [NSMutableArray array];
    for(NSArray *array in arrays)
    {
        assert([array isKindOfClass:[NSArray class]]);
        [merged addObjectsFromArray:array];
    }
    NSLog(@"merged : %@",merged);
    
    // NSNumericSearch
    NSArray *sorted = [merged sortedArrayUsingComparator:^(id obj1, id obj2) {
        return [obj1 compare:obj2 options:NSNumericSearch];
    }];
    NSLog(@"sorted (NSNumericSearch): %@",sorted);
    
    // NSLiteralSearch
    NSSortDescriptor *sortDescriptor = [NSSortDescriptor sortDescriptorWithKey:nil ascending:YES];
    NSArray *arr = [merged sortedArrayUsingDescriptors:@[sortDescriptor]];

    NSLog(@"sorted (NSLiteralSearch): %@",arr);
}
[self sortAndMergeArrayOfArrays:[NSArray arrayWithObjects:@[@"100",@"200",@"0"],@[@"10",@"9",@"1000"],@[@"3",@"1",@"40"],nil]];

- Anonymous September 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Couldn't you just do the following?

``` objective-c
- (NSArray *)from:(NSArray *)inputArray {

NSMutableArray *sortedMutableArray = [[NSMutableArray alloc] init];

for (NSArray *subArray in inputArray) {

for (NSNumber *n in subArray) {

[sortedMutableArray addObject:n];
}
}

NSSortDescriptor *sort = [NSSortDescriptor sortDescriptorWithKey:@"self" ascending:YES];
[sortedMutableArray sortUsingDescriptors:[NSArray arrayWithObject:sort]];

return sortedMutableArray;
}

```

- DressedInHermes September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

- (NSArray *)from:(NSArray *)inputArray {
    
    NSMutableArray *sortedMutableArray = [[NSMutableArray alloc] init];
    
    for (NSArray *subArray in inputArray) {
        
        for (NSNumber *n in subArray) {
            
            [sortedMutableArray addObject:n];
        }
    }
    
    NSSortDescriptor *sort = [NSSortDescriptor sortDescriptorWithKey:@"self" ascending:YES];
    [sortedMutableArray sortUsingDescriptors:[NSArray arrayWithObject:sort]];
    
    return sortedMutableArray;
}

- DressedInHermes September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe I didn't get the question properly, but wouldn't this be enough (apart of specialized methods, like sortedArray)?

- (NSArray *)sortedArrayFromInput:(NSArray *)input {
	NSMutableArray *output = [@[] mutableCopy];
	for (NSArray *arr in input) {
		for (NSNumber *i in arr) {
			if (output.count == 0) {
				[output addObjectsFromArray:arr];
				break;
			}
			else {
				int index = 0;
				for (NSNumber *j in output.reverse) {
					if (i.integerValue >= j.integerValue) {
						index = [output indexOfObject:j] + 1;
						break;
					}
				}
				[output insertObject:i atIndex:index];
			}
		}
	}

}

- Roland October 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@implementation CombineSortedArrays

+ (NSArray*)combineArrays:(NSArray*)arrays {
    
    if (!arrays || [arrays count] == 0) {
        return nil;
    }
    
    NSMutableArray *finalArray = [NSMutableArray arrayWithArray:[arrays objectAtIndex:0]];
    for (NSUInteger i = 1; i < [arrays count]; i++) {
        
        [CombineSortedArrays mergeArray:[arrays objectAtIndex:i] intoArray:finalArray];
    }
    
    return finalArray;
}

+ (void)mergeArray:(NSArray*)arrayToMerge intoArray:(NSMutableArray*)baseArray {
    
    for (NSUInteger i = 0; i < [arrayToMerge count]; i++) {
        
        NSNumber *n = [arrayToMerge objectAtIndex:i];
        
        NSUInteger j = [baseArray count] - 1;
        for (; j > 0; j--) {
            
            if ([[baseArray objectAtIndex:j] compare:n] == NSOrderedAscending) {
                break;
            }
        }
        
        if (j +1 == [baseArray count]) {
            [baseArray addObject:n];
        } else {
            [baseArray insertObject:n atIndex:j + 1];
        }
    }
}

@end

- Mike P November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@implementation CombineSortedArrays

+ (NSArray*)combineArrays:(NSArray*)arrays {
    
    if (!arrays || [arrays count] == 0) {
        return nil;
    }
    
    NSMutableArray *finalArray = [NSMutableArray arrayWithArray:[arrays objectAtIndex:0]];
    for (NSUInteger i = 1; i < [arrays count]; i++) {
        
        [CombineSortedArrays mergeArray:[arrays objectAtIndex:i] intoArray:finalArray];
    }
    
    return finalArray;
}

+ (void)mergeArray:(NSArray*)arrayToMerge intoArray:(NSMutableArray*)baseArray {
    
    for (NSUInteger i = 0; i < [arrayToMerge count]; i++) {
        
        NSNumber *n = [arrayToMerge objectAtIndex:i];
        
        NSUInteger j = [baseArray count] - 1;
        for (; j > 0; j--) {
            
            if ([[baseArray objectAtIndex:j] compare:n] == NSOrderedAscending) {
                break;
            }
        }
        
        if (j +1 == [baseArray count]) {
            [baseArray addObject:n];
        } else {
            [baseArray insertObject:n atIndex:j + 1];
        }
    }
}

@end

- Mike P November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a

- Joan Martin November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

NSArray* input = @[@[@2, @5, @10],@[@25, @100, @105],@[@7, @56, @42]];
    NSMutableArray *unsortedArray = [NSMutableArray new];
    NSArray *sortedArray = [NSArray new];
    [input enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSArray *currentArray = obj;
        for (id object in currentArray) {
            [unsortedArray addObject:object];
        }
    }];
    sortedArray = [unsortedArray sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        return [obj1 compare:obj2];
    }];

- deepak.hebbar November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There's an error in the supplied data: the question specifies that the arrays are each already sorted, so it's a merging operation. The last array isn't sorted.

In any case, this is easy to do if you push the arrays themselves onto the heap, and the heap's comparison operation examines the first object in each array.

1. Create heap with comparison operation that compares an array's first object.
2. To prepare, push each array onto the heap
3. Then while all of the heaps aren't empty
3a. Pop the minimum array
3b. Push its first object into the result
3c. Push the minimum array back onto the heap

Complexity:
Time O(n log k) -> k = number of arrays
Space O(k) -> the number of arrays

Ruby implementation. Cocoa has CFBinaryHeap, but it's a pain to use.

require 'algorithms'

def merge_arrays(arrays)
	result = Array.new
	heap = Containers::Heap.new { |x, y| (x.first <=> y.first) == -1	}

	for array in arrays
		heap.push(array)
	end

	loop do
		min_array = heap.pop
		result << min_array.shift
		if min_array.count > 0 
			heap.push(min_array) 
		end
		break if heap.empty?
	end

	result
end

- fungled January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

python solution O(nlogn) time, not space.

def merge_list(l):
	if len(l) == 1:
		return merge(l[0],[])
	mid = len(l)/2
	return merge(merge_list(l[:mid]), merge_list(l[mid:]))
	
def merge(l,m):
	return list(set((l+m)))

merge_list([[2, 7, 13], [4, 9, 11, 16, 20], [1, 8], [6, 13, 23, 30]])
output: [1, 2, 4, 6, 7, 8, 9, 11, 13, 16, 20, 23, 30]

- txciggy March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

python solution O(nlogn) time, not space.

def merge_list(l):
	if len(l) == 1:
		return merge(l[0],[])
	mid = len(l)/2
	return merge(merge_list(l[:mid]), merge_list(l[mid:]))
	
def merge(l,m):
	return list(set((l+m)))

merge_list([[2, 7, 13], [4, 9, 11, 16, 20], [1, 8], [6, 13, 23, 30]])
output: [1, 2, 4, 6, 7, 8, 9, 11, 13, 16, 20, 23, 30]

- txciggy March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use merge sort like algorithm

- (NSArray *)mergeSortedArrays:(NSArray *)arrs
{

return [self mergeHelper:arrs start:0 end:arrs.count-1];
}

- (NSArray*)mergeHelper:(NSArray*)arrs start:(NSInteger)start end:(NSInteger)end{

if (start >= end) {
return arrs[start];
}

NSInteger mid = start + (end-start)/2;

NSArray *left = [self mergeHelper:arrs start:start end:mid];
NSArray *right = [self mergeHelper:arrs start:mid+1 end:end];

return [self merge:left And:right];
}

- (NSArray*)merge:(NSArray*)arr1 And:(NSArray*)arr2{

NSMutableArray *res = [NSMutableArray array];
NSInteger i = 0;
NSInteger j = 0;
while (i < arr1.count && j < arr2.count) {
NSNumber *num1 = arr1[i];
NSNumber *num2 = arr2[j];
if (num1.integerValue < num2.integerValue) {
[res addObject:num1];
i++;
}else{
[res addObject:num2];
j++;
}
}

while (i < arr1.count) {
[res addObject:arr1[i]];
i++;
}

while (j < arr2.count) {
[res addObject:arr2[j]];
j++;
}

return res;
}

- ghostdiemn April 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- (NSArray *)mergeSortedArrays:(NSArray *)arrs
{

return [self mergeHelper:arrs start:0 end:arrs.count-1];
}

- (NSArray*)mergeHelper:(NSArray*)arrs start:(NSInteger)start end:(NSInteger)end{

if (start >= end) {
return arrs[start];
}

NSInteger mid = start + (end-start)/2;

NSArray *left = [self mergeHelper:arrs start:start end:mid];
NSArray *right = [self mergeHelper:arrs start:mid+1 end:end];

return [self merge:left And:right];
}

- (NSArray*)merge:(NSArray*)arr1 And:(NSArray*)arr2{

NSMutableArray *res = [NSMutableArray array];
NSInteger i = 0;
NSInteger j = 0;
while (i < arr1.count && j < arr2.count) {
NSNumber *num1 = arr1[i];
NSNumber *num2 = arr2[j];
if (num1.integerValue < num2.integerValue) {
[res addObject:num1];
i++;
}else{
[res addObject:num2];
j++;
}
}

while (i < arr1.count) {
[res addObject:arr1[i]];
i++;
}

while (j < arr2.count) {
[res addObject:arr2[j]];
j++;
}

return res;
}

- ghostdiemn April 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

NSArray *dataArray = [[NSArray alloc]initWithObjects:@"2",@"5",@"10",@"25",@"100",@"105",@"7",@"56",@"42", nil];

NSSortDescriptor *descriptor=[[NSSortDescriptor alloc] initWithKey:@"self" ascending:YES]; //Creates and returns an NSSortDescriptor with the specified key and ordering

NSArray *descriptors=[NSArray arrayWithObject: descriptor]; //create sort description array

NSArray *reverseOrder=[dataArray sortedArrayUsingDescriptors:descriptors];//Returns a copy of the receiving array sorted as specified by a given array of sort descriptors.

NSLog(@"Sorted Array:::%@", reverseOrder);

- Satz July 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- (NSArray*)mergeLists:(NSArray*)lists
{
  NSMutableArray *mergedList = [NSMutableArray new];
  for (NSArray *list in lists) {
    mergedList = [[mergedList arrayByAddingObjectsFromArray:list] mutableCopy];
  }
  
  // If array of NSNumbers
  NSSortDescriptor *sortDescriptor = [NSSortDescriptor sortDescriptorWithKey:@"self" ascending:YES];
  return [mutableArrayOfNumbers sortUsingDescriptors:[NSArray arrayWithObject:sortDescriptor]];
  
  
  // If array of NSStrings
  return [mergedList sortedArrayUsingDescriptors:
                    @[[NSSortDescriptor sortDescriptorWithKey:@"doubleValue" 
                                                    ascending:YES]]];
}

- Etay Luz April 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- (NSMutableArray*)sortArrays: (NSMutableArray*)arrayList{
	if([arrayList count]==0){
		return nil;
	}
	NSMutableArray *giantArray = [NSMutableArray new];
	for(NSMutableArray*nestedArray in arrayList){
		[giantArray addObjectsFromArray: nestedArray];
	}
	if([giantArray count]==0){
		return nil;
	}
	return [self mergeSort:giantArray];		
}


-(NSArray *)mergeSort:(NSArray *)unsortedArray
{
    if ([unsortedArray count] < 2){
        return unsortedArray;
    }
    long middle = ([unsortedArray count]/2);   
    NSRange left = NSMakeRange(0, middle);
    NSRange right = NSMakeRange(middle, ([unsortedArray count] - middle));
    NSArray *rightArr = [unsortedArray subarrayWithRange:right];
    NSArray *leftArr = [unsortedArray subarrayWithRange:left];

    NSArray *resultArray =[self merge:[self mergeSort:leftArr] andRight:[self mergeSort:rightArr]];
    return resultArray;
}

-(NSArray *)merge:(NSArray *)leftArr andRight:(NSArray *)rightArr
{
    NSMutableArray *result = [[NSMutableArray alloc] init];
    int right = 0;
    int left = 0;
    while (left < [leftArr count] && right < [rightArr count])
    {
        if ([[leftArr objectAtIndex:left] intValue] < [[rightArr objectAtIndex:right] intValue])
        {
            [result addObject:[leftArr objectAtIndex:left++]];
        }
        else
        {
            [result addObject:[rightArr objectAtIndex:right++]];
        }
    }
    NSRange leftRange = NSMakeRange(left, ([leftArr count] - left));
    NSRange rightRange = NSMakeRange(right, ([rightArr count] - right));
    NSArray *newRight = [rightArr subarrayWithRange:rightRange];
    NSArray *newLeft = [leftArr subarrayWithRange:leftRange];
    newLeft = [result arrayByAddingObjectsFromArray:newLeft];
    return [newLeft arrayByAddingObjectsFromArray:newRight];
}

- Anonymous February 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use power of Swift

struct User {
var emails: [String]
}

let userOne = User(emails: ["durgesh@yahoo.com", "lal@yahoo.com", "gupta@yahoo.com"])

let userTwo = User(emails: ["durgesh@live.com", "lal@live.com", "gupta@live.com"])

let userThree = User(emails: ["durgesh@gmail.com", "lal@gmail.com", "gupta@gmail.com"])

let allUsers = [userOne, userTwo, userThree]

let allEmails = allUsers.flatMap( {$0.emails} )
print(allEmails)
let allEmailsWithMap = allUsers.map( {$0.emails} )
print(allEmailsWithMap)

- Durgesh April 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public void merge(LinkedList<List<Integer>> queue){
		
		while (queue.size() >= 2){
		  List <Integer> listA = queue.pop() ;  
		  List <Integer> listB = queue.pop() ;
		  List<Integer> tmp = new LinkedList<Integer>();
		  int i = 0 ;
		  int j = 0 ;
		  while (i < listA.size() && j < listB.size()){
			  if (listA.get(i) <= listB.get(j)){
				  tmp.add(listA.get(i++)) ;				  
			  }else{
				  tmp.add(listB.get(j++)) ;
			  }
		  }
		  
		  while (i < listA.size()){
			  tmp.add(listA.get(i++)) ;
		  }
		  
		  while (j < listB.size()){
			  tmp.add(listB.get(j++)) ;
		  }
		  
		  queue.push(tmp);
		}

}

- Scott May 06, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More