InterviewBit-Day7

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

Practice

MAXSPPROD

You are given an array A containing N integers. The special product of each i^th^ integer in this array is defined as the product of the following:

  1. LeftSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] (i>j). If multiple A[j]’s are present in multiple positions, the LeftSpecialValue is the maximum value of j.

  2. RightSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] (j>i). If multiple A[j]s are present in multiple positions, the RightSpecialValue is the minimum value of j.

Write a program to find the maximum special product of any integer in the array.

Input: You will receive array of integers as argument to function.

Return: Maximum special product of any integer in the array modulo 1000000007.

Note: If j does not exist, the LeftSpecialValue and RightSpecialValue are considered to be 0.

Constraints 1 <= N <= 10^5^ 1 <= A[i] <= 10^9^

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
public class Solution {
    public int maxSpecialProduct(ArrayList<Integer> A) {
        int n = A.size();
        int[] left = new int[n];
        int[] right = new int[n];
        
        Deque<Integer> q = new ArrayDeque<>();
        q.addLast(0);
        
    	for(int i = 1; i < n; i++){
    		while(!q.isEmpty()){
    			if(A.get(q.getLast()) > A.get(i)) break;
    			q.removeLast();
    		}
    		left[i] = (q.isEmpty()) ? 0 : q.getLast();
    		q.addLast(i);
    	}
    	q = new ArrayDeque<>();
    	q.addLast(n - 1);
    	for(int i = n - 2; i >= 0; i--){
    		while(!q.isEmpty()){
    			if(A.get(q.getLast()) > A.get(i)) break;
    			q.removeLast();
    		}
    		right[i] = (q.isEmpty()) ? 0 : q.getLast();
    		q.addLast(i);
    	}
    	long mx = -1;
    	for(int i = 0; i < n; i++){
    		mx = Long.max(mx, 1L * left[i] * right[i]);
    	}
    	return (int)(mx % 1000000007);
    }
}

Prime Sum

Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number.

NOTE A solution will always exist. read Goldbach’s conjecture

Example:

1
2
Input : 4
Output: 2 + 2 = 4

If there are more than one solutions possible, return the lexicographically smaller solution.

1
2
3
4
5
6
If [a, b] is one solution with a <= b,
and [c,d] is another solution with c <= d, then

[a, b] < [c, d] 

If a < c OR a==c AND b < d.
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 {
    public ArrayList<Integer> primesum(int A) {
        ArrayList<Integer> ret = new ArrayList<>();
        for (int i = 2; i < A; i++) {
            if (isPrime(i) && isPrime(A - i)) {
                ret.add(i);
                ret.add(A - i);
                return ret;
            }
        }
        return ret;
    }
    
    private boolean isPrime(int num) {
        int s = (int) Math.sqrt(num);
        for (int i = 2; i <= s; i++) {
            if (num%i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

Excel Column Number

Given a column title as appears in an Excel sheet, return its corresponding column number.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
A -> 1

B -> 2

C -> 3

...

Z -> 26

AA -> 27

AB -> 28
1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int titleToNumber(String A) {
        int len = A.length(), t = 0, ret = 0;
        for (int i = len - 1; i >= 0; i--) {
            char temp = A.charAt(i);
            ret += (temp - 'A' + a) * (int)Math.pow(26, t);
            t++;
        }
        
        return ret;
    }
}
0%