InterviewBit-Day4

发表于 | 分类于
| 字数统计 518 | 阅读时长 3

Sorting

Quick Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static int[] quickSort(int[] A, int start, int end) {
    if (start < end) {
        int partitionIndex = partition(A, start, end);
        quickSort(A, start, partitionIndex - 1);
        quickSort(A, partitionIndx + 1, end);
    }    
}

private static int partition(int[] A, int start, int end) {
    int pivot = A[end];
    int partitionIndex = start;
    for (int i = start; i < end; i++) {
        if (A[i] < pivot) {
            swap(A[i], A[partitionIndex]);
            partitionIndex++;
        }
    }
    swap(A[partitionIndex], A[end]);
    return partitionIndex;
}

Practice

Max Non Negative SubArray

Find out the maximum sub-array of non negative numbers from an array.
The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid.

Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).

Example:

A : [1, 2, 5, -7, 2, 3]
The two sub-arrays are [1, 2, 5][2, 3].
The answer is [1, 2, 5] as its sum is larger than [2, 3]

NOTE: If there is a tie, then compare with segment's length and return segment which has maximum length
NOTE 2: If there is still a tie, then return the segment with minimum starting index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
    public static ArrayList<Integer> maxset(ArrayList<Integer> A) {
        if (A == null || A.size() == 0) {
            return new ArrayList<>();
        }
        ArrayList<ArrayList<Integer>> B = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        for (Integer a : A) {
            if (a >= 0) {
                temp.add(a);
            } else {
                B.add(temp);
                temp = new ArrayList<>();
            }
        }
        B.add(temp);

        ArrayList<Long> sumList = new ArrayList<>();

        long sum = 0;
        for (int i = 0; i < B.size(); i++) {
            ArrayList<Integer> bList = B.get(i);
            for (Integer b : bList) {
                sum += b;
            }
            sumList.add(sum);
            sum = 0;
        }

        long max = 0;
        for (int i = 0; i < sumList.size(); i++) {
            if (sumList.get(i) >= max) {
                max = sumList.get(i);
            }
        }

        return B.get(sumList.indexOf(max));
    }
}

Max Sum Contiguous Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example:

Given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

For this problem, return the maximum sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int maxSubArray(final List<Integer> A) {
        if (A == null || A.size() == 0 ) {
            return 0;
        }
        
        int total = A.get(0), maxSum = A.get(0);
        
        for (int i = 1; i < A.size(); i++) {
            if (total >= 0) {
                total += A.get(i);
            } else {
                total = A.get(i);
            }
            
            if (total > maxSum) {
                maxSum = total;
            }
        }
        
        return maxSum;
    }
}
0%