Weever's Road

Just another WordPress site

Month: December 2016

Pretty Print

Print concentric rectangular pattern in a 2d matrix.

Input: A = 4.
Output:

4 4 4 4 4 4 4
4 3 3 3 3 3 4
4 3 2 2 2 3 4
4 3 2 1 2 3 4
4 3 2 2 2 3 4
4 3 3 3 3 3 4
4 4 4 4 4 4 4

Solution:

Just mark four borders each loop

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
    public ArrayList<ArrayList<Integer>> prettyPrint(int a) {
        ArrayList<ArrayList<Integer>> result = new ArrayList();
        if(a == 0)
            return result;
        int n = 2*a -1;
        int[][] matrix = new int[n][n];
       
        int start = 0;
        int end = n - 1;
       
        for(;a>0;a--){
            //fill top
            for(int i = start; i <=end; i++ ){
                matrix[start][i] = a; //top
                matrix[i][end] = a; //right
                matrix[end][i] = a; // bottom
                matrix[i][start] = a; //left
            }
            start++;
            end--;
        }
       
        for(int j = 0; j < n; j++){
            ArrayList<Integer> temp = new ArrayList();
            for(int m = 0; m<n; m++){
                temp.add(matrix[j][m]);
            }
            result.add(temp);
        }
       
        return result;
    }

151. Reverse Words in a String

Given an input string, reverse the string word by word.

Example:
Given s = “the sky is blue”,
return “blue is sky the”.

Trick: trim before split.

1
2
3
4
5
6
7
8
9
    public String reverseWords(String s) {
        if( s == null || s=="" || s.length() == 0)
            return s;
        String[] strs = s.trim().split("\\s+");
        List<String> list = Arrays.asList(strs);
        Collections.reverse(list);
        strs = (String[]) list.toArray();
        return String.join(" ",strs);
    }

287. Find the Duplicate Number (Hard??)

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
 public int findDuplicate(int[] nums) {
        if(nums == null)
            return -1;
        boolean[] check = new boolean[nums.length];
        for(int i=0 ; i< nums.length; i++){
            if(check[nums[i]])
                return nums[i];
            else
                check[nums[i]] = true;
        }
        return -1;
    }

179. Largest Number (Meduim)

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.

Solution:
1: sort the number, compare the digits of number from left to right, the largest should be first.
like: compare {89,9}, the first digit 9 is largest, sort as {9,89} so the combined 989 is largest.
2. if the digits are same like {2332,23}, we have to compare left digits with shortest number again to determine which is first, 32 > 23, so sorted as {2332,23}
3. We can find trick, for each two number, we can find the law: combine numbers in both way as strings, {89,9} = {899,989}, then compare the strings so we can sort the numbers

For list, override Collections.sort()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String largestNumber(final List<Integer> a) {
        if(a == null)
            return "0";
        Collections.sort(a, new Comparator<Integer>(){
            @Override
            public int compare(Integer n1, Integer n2){
                String s1 = String.valueOf(n1);
                String s2 = String.valueOf(n2);
                return (s2+s1).compareTo(s1+s2);
            }
        });
        if(a.get(0) == 0)
            return "0";
       StringBuffer sb = new StringBuffer();
       for(Integer i : a){
           sb.append(i);
       }
       return sb.toString();
    }

For Arrays, write Comparator function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 public String largestNumber(int[] nums) {
        Integer[] ints = new Integer[nums.length];
        int index = 0;
        for(int i : nums){
            ints[index++] = i;
        }
        Arrays.sort(ints,new Comparator<Integer>(){
            public int compare(Integer n1, Integer n2){
                String s1=String.valueOf(n1);
                String s2=String.valueOf(n2);
                return (s2+s1).compareTo(s1+s2);
            }
        });
       
        if(ints[0] == 0)
            return "0";
        StringBuilder sb = new StringBuilder();
        for(Integer i : ints){
            sb.append(i);
        }
       
        return sb.toString();
    }

416. Partition Equal Subset Sum (Medium)

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.

Solution:
1. If array can be divided two sum of subset equally, the total sum of array should be even.
2. Find subset, target = sum/2
2. Use boolean array dp[i], i = sum of subset, dp[i] = true if the sum exits.
3. Only need to check the sum of subset between [1, target]
4. loop nums array, for each loop, check i in dp[] between [0, min(currSum, target)]
if the previous sums in dp[] are true, plus current num, each i which is true in dp[], each i + num if also true.
5. when there is a one in loop we can find previous i + current num = target, return true; otherwise after loop, dp[target] = false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean canPartition(int[] nums) {
        if(nums == null && nums.length < 2)
            return false;
        int sum = Arrays.stream(nums).sum();
        if(sum%2 == 1)
            return false;
        int target = sum/2;
       
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
       
        int currSum = 0;
        for(int i=0; i < nums.length; i++){
            int max = Math.min(currSum+nums[i],target);
            for(int j = max ; j >= nums[i] ; j-- ){
                dp[j] = dp[j] || dp[j-nums[i]] ;
            }
            if (dp[target]==true)
                return true;
            currSum += nums[i];
        }
        return dp[target];
    }

56. Merge Intervals (hard)

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution:
1. If the given list is sort by start.
2. Check the current intervals is overlap or inside the previous one.
if true: combine the overlap intervals, go next interval
if false: no overlap, save the previous one, set current, go next interval

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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals == null || intervals.size() == 0)
            return intervals;
         Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        List<Interval> result = new ArrayList<>();
        Interval current = intervals.get(0);
        for(int i = 1; i < intervals.size(); i++){
            if(intervals.get(i).end <= current.end){
                 current = intervals.get(i);
            }
            else if( intervals.get(i).start <= current.end){
                current = new Interval(current.start,intervals.get(i).end);
            } else {
                result.add(current);
                current = intervals.get(i);
            }
        }
        result.add(current);
        return result;
    }
}

InterviewBit solution:
1. assume the List is sorted, insert the new element in the list
2. Do the logic above

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
 public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        if (newInterval.end  < newInterval.start)
            newInterval = new Interval(newInterval.end, newInterval.start);
        ArrayList<Interval> result = new ArrayList();
        if(intervals == null || intervals.size() == 0){
            result.add(newInterval);
            return result;
        }
        int i = 0;
        while(i < intervals.size() && newInterval.start > intervals.get(i).start)
            i++;
        if(i == intervals.size())
            intervals.add(newInterval);
        else
            intervals.add(i,newInterval);
       
        Interval current = intervals.get(0);
        for(int j=1;j<intervals.size();j++){
            if(intervals.get(j).start <= current.end)
                current = new Interval(current.start, Math.max(current.end,intervals.get(j).end));
            else{
                result.add(current);
                current = intervals.get(j);
            }
        }
        result.add(current);
        return result;
    }

Wave Array

Given an array of integers, sort the array into a wave like array and return it,
In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5..... Example Given [1, 2, 3, 4] One possible answer : [2, 1, 4, 3] Another possible answer : [4, 1, 3, 2] Solution: 1.Sort the array 2.switch each two number along the array 3.boundary condition: a.size()-1 avoid Index out of boundary if array has odd elements.

1
2
3
4
5
6
7
8
9
10
11
    public ArrayList<Integer> wave(ArrayList<Integer> a) {
        if(a == null)
            return a;
       Collections.sort(a);
       for(int i=0; i < a.size()-1; i+=2){
           int temp = a.get(i);
           a.set(i,a.get(i+1));
           a.set(i+1,temp);
       }
       return a;
    }

Add One To Number (Easy)

Given a non-negative number represented as an array of digits,
add 1 to the number ( increment the number represented by the digits ).
The digits are stored such that the most significant digit is at the head of the list.

Example:
If the vector has [1, 2, 3]
the returned vector should be [1, 2, 4]
as 123 + 1 = 124.

Corner case: [0,6,6,0,9] need to remove the 0 at head of array/list

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
    public ArrayList<Integer> plusOne(ArrayList<Integer> a) {
        if(a==null){
            a = new ArrayList<>();
            a.add(1);
            return a;
        }
       
        int carry = 1;
        int sum =0;
        int index = a.size() - 1;
       
        while(carry == 1 && index >=0 ){
            sum = a.get(index) + carry;
            carry = sum/10;
            a.set(index,sum%10);
            index--;
        }
       
        if(carry ==1)
            a.add(0,1);
       
        while(a.get(0) == 0){
            a.remove(0);
        }
       
        return a;
    }

Min Steps in Infinite Grid

You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the first point.

Example :

Input : [(0, 0), (1, 1), (1, 2)]
Output : 2
It takes 1 step to move from (0, 0) to (1, 1). It takes one more step to move from (1, 1) to (1, 2).

This question is intentionally left slightly vague. Clarify the question by trying out a few cases in the “See Expected Output” section.

Solution:
The shortest way from point A to point B is go diagonal as possible as it can. the shortest way is max(x1-x2,y1-y2), sum all of steps between points.

1
2
3
4
5
6
7
    public int coverPoints(ArrayList<Integer> X, ArrayList<Integer> Y) {
        int step = 0;
        for(int i=0; i < X.size() - 1; i++){
            step += Math.abs(X.get(i+1)-X.get(i)) > Math.abs(Y.get(i+1)-Y.get(i)) ? Math.abs(X.get(i+1)-X.get(i)) : Math.abs(Y.get(i+1)-Y.get(i));
        }
        return step;
    }

54. Spiral Matrix (Medium)

Given a matrix of m * n elements (m rows, n columns), return all elements of the matrix in spiral order.

1. Math.min() return int, cast to double then divided by 2, ceil() to find the minimum for loop times
2. check if vertical or horizontal line has only one left, then return the line to finish.

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
40
41
42
public ArrayList<Integer> spiralOrder(final List<ArrayList<Integer>> a) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // Populate result;
        if(a == null || a.size() == 0)
            return result;
        int rs = 0 , cs = 0;
        int re = a.size() - 1, ce = a.get(0).size() -1;
       
        for(int i = 0; i < Math.ceil(((double) Math.min(a.size(),a.get(0).size()))/2); i++){

            if (re - rs == 0) {
                for (int index = cs; index <= ce; index++)
                    result.add(a.get(rs).get(index));
                return result;
            }

            if (ce - cs == 0) {
                for (int index = rs; index <= re; index++)
                    result.add(a.get(index).get(cs));
                return result;
            }
           
            //top
            for(int index = cs ; index <= ce; index++)
                result.add(a.get(rs).get(index));
           
            //right
            for(int index = rs + 1; index <= re ; index ++)
                result.add(a.get(index).get(ce));
           
            //bottom
            for(int index = ce - 1; index >= cs; index --)
                result.add(a.get(re).get(index));
           
            //left
            for(int index = re - 1; index >= rs + 1; index --)
                result.add(a.get(index).get(cs));
           
            rs++;cs++;re--;ce--;
        }
        return result;
    }

Powered by WordPress & Theme by Anders Norén