Weever's Road

Just another WordPress site

Category: InterviewBit

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;
    }

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();
    }

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;
    }

Powered by WordPress & Theme by Anders Norén