Uber Interview Question
SDE1sCountry: India
public void findIndex(int[] nums) {
//find index on the right side
int[] indexLeft = new int[nums.length];
for(int i = 0; i < nums.length; i++) {
int index = findIndex(indexLeft, nums, i, true);
indexLeft[i] = index;
}
int[] indexRight = new int[nums.length];
for(int i = nums.length - 1; i >= 0; i--) {
int index = findIndex(indexRight, nums, i, false);
indexRight[i] = index;
}
for(int i = 0; i< nums.length; i++) {
if(indexRight[i] == -1) System.out.print(indexLeft[i]+" ");
else if(indexLeft[i] == -1) System.out.print(indexRight[i]+" ");
else if(i - indexLeft[i] <= indexRight[i] - i) System.out.print(indexLeft[i]+" ");
else System.out.print(indexRight[i]+" ");
}
}
private int findIndex(int[] indexes, int[] nums, int i, boolean left) {
int index = left? i - 1: i + 1;
if(i == 4 && !left) System.out.println(index);
while(index >= 0 && index < nums.length) {
if(nums[index] <= nums[i]) index = indexes[index];
else return index;
}
return -1;
}
Python implementation -- worst case O(n^2), avg case can be better
start from i and move left and right till u find a number greater than that at index i
def nearestGreater(l):
lengthL = len(l)
k=[None]*lengthL
for i,num in enumerate(l):
j1 = j2 = i
while True:
j1 -= 1
j2 += 1
if j1>0 or j2<lengthL:
if j1>0 and l[j1]>num:
k[i]=j1
break
elif j2<lengthL-1 and l[j2]>num:
k[i]=j2
break
else:
break
return k
// ZoomBA :: Simple but non-optimal way to solve it
def find_nearest ( arr , i ){
li = index ( [0:i] ) :: { arr[ $.o ] > arr[i] }
ri = rindex ( [i+1: #|arr|] ) :: { arr[ $.o ] > arr[i] }
if ( li == -1 && ri == -1 ) return -1
if ( li == -1 ) return ri
return li
}
lfold ( arr ){
printf ('%d -> %d\n', $.i, find_nearest(arr, $.i))
}
If we create a Binary search tree. Check for every i if there exists a right child. If there exists then return 1 or else return 0. The complexity would be nlogn.
The other way could be to sort the array using mergesort and then print 1's for all the elements in the sorted array except last element. Complexity= nlogn
Please correct me, I am not sure whether it is right.
This approach will not be correct. Using the approach of binary search, you will be able to find greater element than a[i], but that would not mean that it is the nearest maximum element for a[i].
c# implementation.
O(n^2).
using System;
namespace NearestBiggerValue {
class Program {
private static int FindBigger( int[] arr, int i ) {
int indexL = i;
int indexR = i;
int? rightVal = null;
int? leftVal = null;
while ( indexL >= 0 || indexR < arr.Length ) {
indexR++;
indexL--;
if (indexR < arr.Length ) {
rightVal = arr[ indexR ];
} else {
rightVal = null;
}
if ( indexL >= 0 ) {
leftVal = arr[ indexL ];
} else {
leftVal = null;
}
if ( ( rightVal != null && rightVal > arr[ i ] ) || ( leftVal != null && leftVal > arr[ i ] ) ) {
break;
}
}
if ( ( rightVal == null && leftVal == null) || ( rightVal <= arr[ i ] && leftVal <= arr[ i ] ) ) {
return -1;
}
if ( rightVal != null && leftVal != null ) {
return rightVal > leftVal ? indexR : indexL;
}
return rightVal == null ? indexL: indexR;
}
private static void Process( int[] arr ) {
for ( int i = 0; i < arr.Length; i++ ) {
int val = FindBigger( arr, i );
string str = val == -1 ? -val + " (doesn't exist)" : val.ToString();
Console.WriteLine($"For index {i} nearest bigger value is at index {str}");
}
Console.ReadLine();
}
static void Main( string[] args ) {
int[] arr = new int[] { 77, 2, 15, 16, 5, 3, 19, 2, 0, -2, 77, 7, 77 };
Process(arr);
}
}
}
#include <iostream>
#include <vector>
using namespace std;
void printNearestLargerIndex(const vector<int>& a)
{
for (int i = 1; i < a.size(); ++i)
{
int bestJ = 1;
int distance = 0;
for (int j = 0; j < a.size(); ++j)
{
if (j != i)
{
if (a[j] > a[i])
{
int currentDistance = abs(i-j);
if (distance == 0)
{
bestJ = j;
distance = currentDistance;
}
else
{
if (currentDistance < distance)
{
distance = currentDistance;
bestJ = j;
}
}
}
}
cout << bestJ << endl;
}
}
}
int main()
{
vector<int> a;
a.push_back(1);
a.push_back(77);
a.push_back(-4);
a.push_back(140);
printNearestLargerIndex(a);
return 0;
}
For each element find closest index to left and right and then take closest of two.
- sameer November 17, 2015