Facebook Interview Question
iOS DevelopersCountry: United States
Interview Type: In-Person
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)
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)
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];
}
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.
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);
}
}
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);
}
}
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 '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];
}
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)
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;
}
}
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);
}
}
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.
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;
}
}
- (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]];
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;
}
```
- (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;
}
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];
}
}
}
}
@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
@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
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];
}];
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
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]
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]
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;
}
- (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;
}
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);
- (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]]];
}
- (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];
}
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)
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);
}
}
I see two possible approaches for this :
- Danstahr April 23, 2014* 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).