top interview questions

Write a program to find length of longest consecutive sequence in array of integers

For example,

Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

-(int)longestConsecutive:(NSMutableArray*)arr{

    int max=1;

    NSMutableSet *set = [NSMutableSet setWithArray:arr];

    for (id obj in arr) {

        NSNumber *num = (NSNumber*)obj;

        int Left = [num intValue]-1;

        int Right = [num intValue]+1;

        int count = 1;

        while ([set containsObject:[NSNumber numberWithInt:Left]]) {

            count++;

            [set removeObject:[NSNumber numberWithInt:Left]];

            Left--;

            

        }

        while ([set containsObject:[NSNumber numberWithInt:Right]]) {

            count++;

            [set removeObject:[NSNumber numberWithInt:Right]];

            Right++;

            

        }

        max =  MAX(count,max);

        

    }

    

    

    return max;

}

Read more: http://javarevisited.blogspot.com/2015/06/top-20-array-interview-questions-and-answers.html#ixzz4PhKAavdz




Find-a-triplet-that-sum-to-a-given-value

http://www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value/



find the kth largest element in an unsorted array http://www.programcreek.com/2014/05/leetcode-kth-largest-element-in-an-array-java/

Find the smallest positive number missing from an unsorted array

http://www.crazyforcode.com/find-smallest-positive-number-missing-array/

Find the minimum element in a sorted and rotated array

http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/\


Selection Sort

http://www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm


Code 

func selectionSort(arr :[Int])-> [Int]{

        var tempArr = arr

        var minIndex : Int

        for i in 0..<arr.count-1 {

            minIndex = i

            for j  in i+1..<arr.count {

                

                if tempArr[j] < tempArr[minIndex] {

                    minIndex = j

                }

                

            }

            

            if minIndex != i {

                let temp : Int = tempArr[minIndex]

                tempArr[minIndex] = tempArr[i]

                tempArr[i] = temp

            }

        }

        return tempArr

    }

Insertion Sort

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheInsertionSort.html

https://en.wikipedia.org/wiki/Insertion_sort

Code

 func insertionSort(arr: [Int]) -> [Int] {

        var sortedArr = arr

        var index : Int

        var targetItem : Int

        

        

        for i in 1..<arr.count {

            targetItem = sortedArr[i]

            index = i-1

                            while index >= 0 && sortedArr[index]>targetItem {

                           //move the item to higer index

                           sortedArr[index+1] = sortedArr[index]

                             index -= 1

}

              //item inserted

                sortedArr[index+1] = targetItem

            }

        print("sorted array is \(sortedArr)")

        return sortedArr

    }


Bubble Sort

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html
https://en.wikipedia.org/wiki/Bubble_sort

Code

 func bubbleSort1(arr: [Int]) -> [Int] {

        var temp: Int

        var sortedArr = arr

        var isSwaped:Bool = false

        for i in 0..<arr.count {

            

            for j in 0..<sortedArr.count-1-i {

                if sortedArr[j]>sortedArr[j+1] {

                    temp = sortedArr[j]

                    sortedArr[j] = sortedArr[j+1]

                    sortedArr[j+1] = temp

                    isSwaped = true

                }

            }

            if(!isSwaped) {

                break;

            }

        }

        return sortedArr

    }