Top 30 interview array-problem (Ongoing)

1. How to find the missing number in integer array of 1 to 100?

Missing numbers in integer array [1, 2, 3, 4, 6, 7, 9, 8, 10], with total number 10 is
5

Sum this array, and subtract with n*(n+1)/2
The diff is the answer 
Advanced：find two missing number in array?

https://www.geeksforgeeks.org/find-two-missing-numbers-set-1-an-interesting-linear-time-solution/
(a) For a given array [1,100], we build a new Boolean array (size = 100) to store the existence of corresponding integer. If the corresponding integer exists, assign true, assign false if not exist.
Go through Boolean array the output false element.
Time = O(n) Space = O(n)
(b) If we want better space complexity:
Sum the input array and subtract with n*(n+1)/2. This number is the sum of two missing number.
Divide this number by 2 and we get the average of two missing number. So we make sure one of the missing number if in [1: Avg] , while another missing value is in [Avg: 100]. Use method(a) to find single missing value in both interval separately
Time = O(n) Space = O(1)

Advanced：find second biggest number in array?

(a) Bad method：sorting, and get the second element from last = O(nlogn)
(b) Two times sequence search: First time the find the biggest and record. Second time find the biggest that less than biggest.
(c) Better than method(b): One time sequence search:

Assign array[0] and array[1] to biggest MAX and second biggest MAX' (depending which one is bigger)
Star from array[2:end]：
    if bigger than MAX: replace MAX
    elif bigger than MAX': replace MAX'
    else next element
return MAX'

2. How to find duplicate number on Integer array
For example, if an array with length 6 contains numbers {0, 3, 1, 2, 3}, then duplicated number is 3

Insert every element in array to set. When we get a insertion false, we get the duplicate number

3. How to check if array contains a number

Does array [1, 2, 3, 4, 5] has 5?  true

If array is sorted, use binary search = O(logn)

If not, sequence search = O(n)

4. How to find largest and smallest number in unsorted array?

(a) Sorting, Return first from head and  first from tail = O(nlogn)

(b) Use tmp.max和tmp.min sequence一遍 = O(n)

(like Advanced problem in problem_1)

5. How to find all pairs on integer array whose sum is equal to given number?
For example if input integer array is {2, 6, 3, 9, 11} and given sum is 9, output should be {6,3}

(a) For every element in array, compare with the rest of element and see if we can sum them to given number = O(n^2)

(b) Build a hash table. For every element, we check the table if there is any complement number. Return if we get one, insert in to hash table otherwise.
Time = O(n) (insert and check in hash table takes O(1), awesome!! )
    C++ use unordered_map to implement

(c) method(a) is too slow, method(b) takes too much space. method(c) use in-place method
Sorting first and use two pointer. One starts from head, another starts from tail. Both move toward mid.

if: sum(*it_head, *it_tail) < given_number it_head++

elif: sum(*it_head, *it_tail) > given_number it_tail--

else: got a pair, it_head++, it_tail--

Time = O(nlogn)

6.  How to find repeated numbers in an array if it contains multiple duplicates

( An array contains n numbers ranging from 0 to n-1 and there are 5 duplicates on it, how do you find it?)
A little difference in the example provided from website: To find the first non-repeated character from a String
http://javarevisited.blogspot.sg/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html#axzz5BjXt0Sil
in word "swiss" 'w' is the first non-repeated character

(a) Insert every element in to hash table. Go through hash table and find every element which value is 1 (insert has to be in-order, which is east in JAVA but complicate in CPP)
C++ use map<string, count> to implement, and use another vector to record the order in input array
Or we can use map<string, iterator>, the iterator is the location of element in vector. The vector is a pair <string, count> When we insert fail (means this element is duplicate), we update the count in vector.
After go through all element in array, we check all element in map and the correspond vector (since we can get vector.at(*iterator) in O(1)) to choose the minimal iterator among the count = 1 element

(b) Use a set to put repeat number, use a list to put non-repeat number. (put in to list at the first place. If we find out duplicate, we put into set. Since the duplicate element will be moved out from list, we expect the size of list has a upper bound)

7. Write a program to remove duplicates from array
For example if given array is {1, 2, 1, 2, 3, 4, 5} then your program should return an array which contains just {1, 2, 3, 4, 5}.

( May contain multiple duplicate)
( Maybe not a easy task in JAVA? Is length of array in JAVA un-changable?)

geek has a similar problem :https://www.geeksforgeeks.org/remove-duplicates-sorted-array/
(remove duplicates from sorted array)

(a) Use an auxiliary array ret[] to store return value
Go through input element and copy to ret[] (skip the duplicate).
Recored the MAX_DUP, to know to maximal number of duplicate
(b) Method(a) takes extra space. Method(b) use in-place:

    for (int i=0; i < n-1; i++)

        if (arr[i] != arr[i+1])

            arr[j++] = arr[i];

    arr[j++] = arr[n-1];

Remember the effective array is arr[0:j] the rest is trash

8. How to sort an array in place using QuickSort algorithm?

Review quick sort:choose pivot. Put element larger than pivot in one sub-array, put element less than pivot in another sub-array
Time: expected=O(nlogn). worst case=O(n^2)


We can see psuedo code from wiki. It shows how we use memory space
https://en.wikipedia.org/wiki/Quicksort
Common case is O(n), we can achieve O(logn) by in-place:
Choose pivot and put pivot to the tail of array. Swap the element less than pivot to the first part of input array. Swap pivot to the end of first part in the end (which connect two sub-array)

9. Write a program to find intersection of two sorted arrays
geek has a problem ask for union and intersect
https://www.geeksforgeeks.org/union-and-intersection-of-two-sorted-arrays-2/
union:
if: x_i < y_j
    output x_i; i++
elif: x_i > y_j
    output y_j; j++
else:
    output x_i or y_j; i++; j++
if: i==m || j==n output the rest
Time = O(m+n)

intersection:
union:
if: x_i < y_j
    i++
elif: x_i > y_j
    j++
else:
    output x_i or y_j; i++; j++
if: i==m || j==n EndOfProgram
Time = O(m+n)

10. There is an array with every element repeated twice except one. Find that element?

For example if given array is {1, 1, 2, 2, 3, 4, 4, 5, 5} then your program should return 3

(a) Xor all element. The repeat bit will xor to zero. So the result of xor all element is the answer.

(b) Subtract the (sum of each element)*2 with the (sum of array). The diff is the answer.

(1+2+3+4+5)*2 - (1+1+2+2+3+4+4+5+5) = 3

Advanced from geek:

https://www.geeksforgeeks.org/find-the-element-that-appears-once/

Only one element comes out once, the rest comes out three times. Find out the unique element

(a) Sorting. And go through array = O(nlogn)

(b) hash table, Time = O(n) with extra space

(c) We can achieve Time = O(n),Space = O(1) by bitwise. Maintain two number:

ones: The bits that have appeared 1st time or 4th time or 7th time .. etc.

twos: The bits that have appeared 2nd time or 5th time or 8th time .. etc.

Return one in the end, this is the answer

Take [5,5,5,8] for example, initialize one and two to 0
First 5: two=0; one=5
Second 5: two=5; one=0
Third 5: two=0; one=0 ( both are 5;5, become 0;0 after bitmask)
First 8: two=0; one=8
(d) Sum every bit and divided by 3, the one with remainder is the answer
Take [5,5,5,8] = [101, 101, 101, 1000] for example
Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0;
Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of fourth bits%3 = (1)%3 = 1;
Hence number which appears once is 1000

(e) Subtract the (sum of each element)*3 with the (sum of array). The (diff/ 2) is the answer.

Array [] : [a, a, a, b, b, b, c, c, c, d]
Mathematical Equation = ( 3*(a+b+c+d) – (a + a + a + b + b + b + c + c + c + d) ) / 2

11.How to find k-th smallest element in unsorted array

For example if given array is {1, 2, 3, 9, 4} and k=2

12. How to find k-th largest element in unsorted array?

For example if given array is {10, 20, 30, 50, 40} and k = 3 then your program should return 30 
Two same problem, one for smallest, another for largest
geek:https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

(a) Simplest method: sorting and return k-th element = O(nlogn)

(b) Build a Heap = O(n), and extractMin()/extractMax() k times = O(klogn)

Review about Heap:
https://tmp4by.blogspot.com/2018/02/c-std-map-set.html
O(n + klogn)

(c) Quick sort selection

Choose pivot and separate two sub-arrat like quick sort. But this time we only deal with one of the sub-array since we don't really need to know exactly order of both sub-array.

For example, the pivot separate the array into 2+1+4 (less_than/ pivot/ greater_than), while our k is 4. The problem become finding the 1-th smallest number if the second sub-array (we already know there is 3 smallest number in the first sub-array and pivot)
Same with quick sort, worst case time = O(n^2), but we can expect time = O(n)

13. How to find common elements in three sorted array?

Examples:

input1 = {1, 5, 10, 20, 40, 80}

input2 = {6, 7, 20, 80, 100}

input3 = {3, 4, 15, 20, 30, 70, 80, 120}

Output: 20, 80

(a) Simplest method: The same with problem_9. Intersection between input1 and input2, store as input4. The intersection between input3 and input4 is the answer.
Time = O(n1+n2+n3), need extra space
(b) We can achieve the same O(n1+n2+n3) without using extra space
while( i != input1.len() && j != input2.len() && k != input3.len())
if: x_i == y_j == z_k

    Output x_i or y_j or z_k
    i++; j++; k++;
else:

    if: x_i < y_j
        i++
    elif: y_j < z_k
        j++
    else:
        k++
(which means we shift the minimal among three candidate)

14. How find the first repeating element in an array of integers?
If there are multiple repeating, return the one in the earliest order in input array

Examples: Input:  input [] = {10, 5, 3, 4, 3, 5, 6}

Output: 5 [5 is the first element that repeats]

(a) Simplest method: Choose a number and see if there is repeat = O(n^2)

(b) Sorting: Copy input array into tmp[] and sort tmp[]
By the order of the input array, count the number of occurrence in tmp[]. Return the first element which count != 1
Sorting time = O(nlogn) count occurrence =  n*O(logn)
ps.
Count the frequency of element in a sorted array can be done in O(logn), refer from geek:
https://www.geeksforgeeks.org/count-number-of-occurrences-or-frequency-in-a-sorted-array/
(c) Hash table, notice that we scan array from right to left(i=n-1:0), when we find a duplicate we save index as i. The array[i] in the end is the answer ( if we scan from left to right, we get the last repeating number)

15. How to find first non-repeating element in array of integers?

Similar with problem_14, method(a) and method(b) would do
Similar with problem_6, method(c) would do

(c) Use hash table, record every number and the count = O(n)

Scan table again for any element count =1, return the element with earliest order

Use unordered_map and vector in c++ to implement

16. How to find top two numbers from an integer array

Similar with advanced of problem_1
geek has a solution in Time = O(n) with one time scan

https://www.geeksforgeeks.org/find-the-largest-three-elements-in-an-array/

(Little different problem here: top three number)

set first, second, third = INF

for( i in array)

    if: x_i > first

        third = second; second = first; first = x_i; // order matters

    elif: x_i > second

        third = second; second = x_i;

    elif:x_i > third

        third = x_i;

Output first, second, third

17. How to find the smallest positive integer value that cannot be represented as sum of any subset of a given array?
geek有
https://www.geeksforgeeks.org/find-smallest-value-represented-sum-subset-given-array/

Examples:

Input:       arr[] = {1, 3, 6, 10, 11, 15 };

Output: 2

Input:  arr[] = {1, 1, 1, 1};
Output: 5
Input:  arr[] = {1, 1, 3, 4};
Output: 10

(a) Simplest method: For[1: sum_of_array]. We check every of them to see if possible to represent
(b) assign tmp_return = 1, and go through every element x_i in input array. Two cases here:
1. if: x_i > tmp_return
    tmp_return is the solution
    Since the maximal number we can represent in [x_0..x_i-1] is tmp_return. It impossible to represent tmp_return+1 since x_i afterward is bigger
2. else:
    tmp_return += x_i
    i++

18. How to rearrange array in alternating positive and negative number

Input:  arr[] = {1, 2, 3, -4, -1, 4}
Output: arr[] = {-4, 1, -1, 2, 3, 4}
Input:  arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
output: arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0} 

geek: 

https://www.geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/

(a) Simplest method: use extra space O(n) and copy input array one by one

(b) in-place method：Starts from 0, looking for out-of-place element (x_s), start from x_s, looking for the first element which has opposite sign. Right rotate the [x_s: x_t] in input_array, until x_s > length or x_t > length

out-of-place: the negative number appear at index 1, 3, 5,... or positive number appear at index 0, 2, 4, 6,.... which they are not supposed to be

Example of right rotate:

[...-3, -4, -5, 6...] -->   [...6, -3, -4, -5...]

-3 is out-of-place (the negative number shouldn't appear here), looking for the next positive number and rotate this interval

19. How to find if there is a sub array with sum equal to zero?

Input: {4, 2, -3, 1, 6}
Output: true 
There is a subarray with zero sum from index 1 to 3.
Input: {4, 2, 0, 1, 6}
Output: true 
There is a subarray with zero sum from index 2 to 2.
Input: {-3, 2, 3, 1, 6}
Output: false
There is no subarray with zero sum.

geek: https://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

(a) Brute force: An indicator as starting point, another indicator as ending point. sum every sub-array[start: end] and see if it is zero =O(n^2)

(b) By hashing time = O(n)

unordered_map<int,bool> sumMap;

for( i in input)

    sum += x_i

    if: sum == 0

        we get a sum-zero sub-array

    elif: sumMap[sum] = true

        we get a sum-zero sub-array

    sumMap.insert(<sum, true>);
The idea is: is the sum of array once achieve x, there is only one chance it reach x again: there is a interval of sum is zero

 

20. How to remove duplicates from array in place?

Similar with problem_7, but limit space using

7. (b) Better space complexity:

    for (int i=0; i < n-1; i++)

        if (arr[i] != arr[i+1])

            arr[j++] = arr[i];

    arr[j++] = arr[n-1];

Remember the effective array is arr[0:j] the rest is trash

這題找leetcode練一下

21. How to remove a given element from array in Java?

Similar with problem_22, one time scan would be done

(Hard in JAVA? fixed array length?)

22. How to merge sorted array?

geek:https://www.geeksforgeeks.org/merge-two-sorted-arrays/
Algorithm is simple, but got to trade-off between time and apce
(a) Time = O(n1*n2) Extra-space = O(1)
Take array_1 as ouput_array
for(j in array_2)
    insert y_j to array_1
    // find insert one by one, time = O(n1)
Total time = n2*O(n1)
(b) Time = O(n1+n2) Extra-space = O(n1+n2)

allocate a return_array[n1+n2]
while(i<n1 && j<n2)
    if (x_i < y_j) copy x_i to return_array; i++
    elif (x_i > y_j) copy y_j to return_array; j++

    elif (x_i == y_j) copy x_i to return_array; i++; j++

if anything left, all copy to return_array

23. How to find sub array with maximum sum in an array of positive and negative number?

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous sub-array [4,−1,2,1] has the largest sum = 6.

Equivalent with maximal sum sub-array problem

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

(a) Brute force = O(n^2)
(b) Kadane's Algorithm
The idea is: look for all continuous segment of positive number(max_end_here) and the compare it with max_so_far
initialize both variable with zero, in case that all number are negative. Return zero in this case, which means we choose nothing ( choose any number for a all-negative array may decrease sum)

Initialize: max_so_far=0, max_ending_here=0
For (every element x_i in input_array)
    max_ending_here += x_i
    if: max_ending_here < 0
        max_ending_here = 0
    if: max_so_far < max_ending_here
        max_so_far = max_ending_here
return max_so_far

Lets take the example:{-2, -3, 4, -1, -2, 1, 5, -3}

at element 4 :max_ending_here = 4; max_so_far = 4

at element -1:max_ending_here = 3; max_so_far = 4

at element  1:max_ending_here = 2; max_so_far = 4

at element  5:max_ending_here = 7; max_so_far = 7

at element -3:max_ending_here = 4; max_so_far = 7

Basically this is the idea of dynamic programming. P_i means the maximal sum of sub-array from [0:i] of input array. We can write the formula:
P_i = MAX(P_i-1, P_i-1+x_i)
P_n is the answer, where n is the length of input array

24. How to find sub array with largest product in array of both positive and negative number?

Similar with problem 23

geek: https://www.geeksforgeeks.org/maximum-product-subarray/ 

Input: arr[] = {6, -3, -10, 0, 2}
Output:   180  // The sub-array is {6, -3, -10}
Input: arr[] = {-1, -3, -10, 0, 60}
Output:   60  // The sub-array is {60}
Input: arr[] = {-2, -3, 0, -2, -40}
Output:   80  // The sub-array is {-2, -40}

The idea is the same as problem 23. P_i means the maximal product from [0:i] of input array. Formula: P_i = MAX(P_i-1, P_i-1*x_i). P_n is the answer, where n is the length of input array. We record another min_end_here to obtain the minimal, in case some negative value multiplies some negative can replace max_ending_here (so we obtain a min_end_here, the absolute of negative is larger, the actual value is smaller)
Notice we it is special case when x_i is zero. max_end_here and min_end_here all set back to initial value 1.

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

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

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

We can see this is geek, 算法珠璣, and leetcode

https://www.geeksforgeeks.org/longest-consecutive-subsequence/

https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/remove-duplicates-from-sorted-array.html

https://leetcode.com/problems/longest-consecutive-sequence/description/

(a) Simplest method, sort this array and find the consecutive = O(nlogn)

(b) Insert all element into hash table = n*O(1)

for (every element in input array x_i)
    if (x_i is starting element ) // mean we can't find (x_i -1 ) in hash table
        while( we can find x_i +1 in hash table)
            return_val++
        update return_val

total = O(n)

26. How to find minimum value in a rotated sorted array?
geek: https://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/

Input: {5, 6, 1, 2, 3, 4}
Output: 1
Input: {1, 2, 3, 4}
Output: 1
Input: {2, 1}
Output: 1

(a) use binary search in O(logn), check mid element, and decide 

which half to find

Find(array) 

if array[mid]<array[mid-1]:

    output array[mid+1] 

elif array[mid]>array[mid+1]:

    output array[mid]

if array[end]>array[mid]:

    output Find(array[:mid])

else:
    output Find(array[mid:])

27. Given an array of of size n and a number k, find all elements that appear more than n/k times?

Reference:
Top 30 interview array-problem:
http://javarevisited.blogspot.com/2015/06/top-20-array-interview-questions-and-answers.html#axzz574IcQlGj
geek
https://www.geeksforgeeks.org/
wiki