Amazon Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
I came up with this solution.Is there anywhere I can test my solution.Could be a blunder. Any edits are welcome.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Solution {
public static void main(String... args) {
Scanner in = new Scanner(System.in);
String line1 = in.nextLine();
String[] line1Args = line1.split(" ");
int n = Integer.valueOf(line1Args[0]);
int m = Integer.valueOf(line1Args[1]);
ArrayList<Integer> setValues = new ArrayList<>();
for (int looper = 0; looper < m; looper++) {
int temp = in.nextInt();
setValues.add(temp);
Collections.sort(setValues);
int sum = 0;
for(int i = 0;i<setValues.size();i++){
if(i == 0){
if(setValues.size() == 1){
sum+=1+n;
break;
}else{
sum = 1+(setValues.get(i+1)-1);
}
}
else if(i == setValues.size()-1){
sum+= (setValues.get(i-1)+1)+n;
}
else{
sum+=(setValues.get(i-1)+1)+(setValues.get(i+1)-1);
}
}
System.out.println(sum);
}
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Solution {
public static void main(String... args) {
Scanner in = new Scanner(System.in);
String line1 = in.nextLine();
String[] line1Args = line1.split(" ");
int n = Integer.valueOf(line1Args[0]);
int m = Integer.valueOf(line1Args[1]);
ArrayList<Integer> setValues = new ArrayList<>();
for (int looper = 0; looper < m; looper++) {
int temp = in.nextInt();
setValues.add(temp);
Collections.sort(setValues);
int sum = 0;
for(int i = 0;i<setValues.size();i++){
if(i == 0){
if(setValues.size() == 1){
sum+=1+n;
break;
}else{
sum = 1+(setValues.get(i+1)-1);
}
}
else if(i == setValues.size()-1){
sum+= (setValues.get(i-1)+1)+n;
}
else{
sum+=(setValues.get(i-1)+1)+(setValues.get(i+1)-1);
}
}
System.out.println(sum);
}
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Solution {
public static void main(String... args) {
Scanner in = new Scanner(System.in);
String line1 = in.nextLine();
String[] line1Args = line1.split(" ");
int n = Integer.valueOf(line1Args[0]);
int m = Integer.valueOf(line1Args[1]);
ArrayList<Integer> setValues = new ArrayList<>();
for (int looper = 0; looper < m; looper++) {
int temp = in.nextInt();
setValues.add(temp);
Collections.sort(setValues);
int sum = 0;
for(int i = 0;i<setValues.size();i++){
if(i == 0){
if(setValues.size() == 1){
sum+=1+n;
break;
}else{
sum = 1+(setValues.get(i+1)-1);
}
}
else if(i == setValues.size()-1){
sum+= (setValues.get(i-1)+1)+n;
}
else{
sum+=(setValues.get(i-1)+1)+(setValues.get(i+1)-1);
}
}
System.out.println(sum);
}
}
}
No need to sort
result = 1 + N + 2 * sum(x[i]) - min(x[i]) - max(x[i])
Example:
N = 10
x = {2,5,7,9}
1 + N = 11
sum(x[i]) = 2 + 5 + 7 + 9 = 23
min = 2
max = 9
result = 11 + 2 * 23 - 2 - 9 = 46
I believe this can be done in constant time if M comes in sorted order. Please, brief about this clarification.
- Popeye May 29, 2019