Uber Interview Question
Software DevelopersCountry: India
Interview Type: Phone Interview
package main
import "fmt"
// Given an array of integers find the maximum value of
// a[i] - a[j] + a[k]
// with constraints
// i < j < k and a[i] < a[j] < a[k]
func main() {
a := []int{1, 3, 4, 5, 4}
max := 0 // Will return 0 if the matching combination is never found
for i := 0; i < len(a)-2; i++ {
for j := i + 1; j < len(a)-1; j++ {
for k := j + 1; k < len(a); k++ {
if a[i] < a[j] && a[j] < a[k] && max < a[i]-a[j]+a[k] {
max = a[i] - a[j] + a[k]
}
}
}
}
// O(n^3)
fmt.Printf("Max is %d\n", max)
// Optimization
lookup := make([]int, len(a))
m := a[len(a)-1]
lookup[len(a)-1] = m
for i := len(a) - 2; i > 0; i-- {
if m < a[i] {
m = a[i]
}
lookup[i] = m
}
fmt.Printf("Lookip is %v\n", lookup)
max = 0
for i := 0; i < len(a)-2; i++ {
for j := i + 1; j < len(a)-1; j++ {
if a[i] < a[j] && a[j] < lookup[j+1] && max < a[i]-a[j]+lookup[j+1] {
max = a[i] - a[j] + lookup[j+1]
}
}
}
// O(n^2) + S(n)
fmt.Printf("Max is %d\n", max)
}
/**
* @author Omid Ghiasi Tarzi
*/
static int calculate(int[] arr) {
int max = 0;
boolean isMaxEmpty = true;
for (int i = 0; i < arr.length - 2; i++) {
for (int j = i + 1; j < arr.length - 1; j++) {
for (int k = j + 1; k < arr.length; k++) {
if (arr[i] < arr[j] && arr[j] < arr[k]) {
int value = arr[i] - arr[j] + arr[k];
max = isMaxEmpty || value > max ? value : max;
isMaxEmpty = false;
}
}
}
}
return max;
}
public static int maxSum(int arr[]) {
int max = Integer.MIN_VALUE;
int left[] = new int[arr.length];
int right[] = new int[arr.length];
left[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
left[i] = Math.max(arr[i], left[i-1]);
}
right[arr.length-1] = arr[arr.length-1];
for (int i = arr.length-2; i>=0; i--) {
right[i] = Math.max(arr[i], right[i+1]);
}
for (int i = 1; i < arr.length-1; i++) {
int sum = left[i-1] -arr[i] + right[i+1];
max = Math.max(max, sum);
}
return max;
- Ilya August 02, 2019