Uber | OA Coding Questions and Solutions | Set - 27 | 2022

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

 

 

Answer 1

1. given an array

Find number of elements equal to mean of neighbor elements.

2 4 6 6 3

Ans: 3
2,4,3 satisfy that condition
2=4+0/2, 4=2+6/2

 

2. delete min of peak elements one by one in an array
Peak element defined as it should be greater than it’s neighbors.

2,7,8,5,1,6,3,9,4
8,6,9 are peak elements. You should remove 6 first.
Ans: 6,8,7,5,9,2,4,3,1

 

3.Spiral matrix but you should sort elements in border
You should do for all elements

 

4.given an array and operations
There are 3 operations
a) 2 then you should return min element in array
b) (0,x) add x to elements of an array
c? (1,x) add x to end of an array

Ans should be array with all values of operation 2 that is min at that time

Answer 2

Question 1 : Find number of elements equal to mean of neighbor elements.


public int getMean(int[] arr) {
		Map<Integer,List<Integer>> map = new HashMap<>();
		for(int i=0; i < arr.length; i++) {
			map.putIfAbsent(arr[i], new ArrayList<>());
			map.get(arr[i]).add(i);
		}
		int count = 0;
		if(map.containsKey(arr[0]*2))
			count++;
		if(map.containsKey(arr[arr.length-1]*2))
			count++;
		for(int i=1; i < arr.length-1; i++) {
			for(int j = 0; j<i; j++) {
				if(map.containsKey(arr[i] * 2 - arr[j])) {
					boolean result = false;
                                        // can be optimized by using binary search
					for(int index : map.get(arr[i] * 2 - arr[j])) {
						if(index > i) {
							result = true;
							break;
						}
					}
					if(result) {
						count++;
						break;
					}
				}
			}
		}
		return count;
	}



Question 2:
Approach: Populate minHeap with peak elements in the first pass. Push peak elements on the heap as you pop elements from the heap.
O(N logN)


   class Num{
        int num; 
        int idx;
        int left;
        int right;
        public Num(int num, int idx, int left, int right){
            this.num = num;
            this.idx = idx;
            this.left = left;
            this.right = right;
        }
    }
    public ArrayList<Integer> getMinPeakElements(int[] arr){
        HashMap<Integer, Num> map = new HashMap<>();
        PriorityQueue<Num> minHeap = this.populateHeap(arr, map);
        ArrayList<Integer> res = new ArrayList<>();
        while(!minHeap.isEmpty()){
            Num n = minHeap.poll();
            res.add(n.num);
            Num left = map.get(n.left);
            Num right = map.get(n.right);
            if(left!=null) left.right = n.right;
            if(right!= null) right.left = n.left;
            this.addIfPeak(left, arr, minHeap);
            this.addIfPeak(right, arr, minHeap);
        }
        return res;
    }
    private void addIfPeak(Num n, int[] arr, PriorityQueue<Num> minHeap){
        if(n==null) return;
        int leftVal = (n.left>=0)? arr[n.left]:Integer.MIN_VALUE;
        int rightVal = (n.right<arr.length)?arr[n.right]:Integer.MIN_VALUE;
        if(leftVal<n.num && rightVal<n.num) minHeap.add(n);    
    }
    private PriorityQueue<Num> populateHeap(int[] arr, HashMap<Integer, Num> map){
        PriorityQueue<Num> minHeap = new PriorityQueue<>(new Comparator<Num>(){
            public int compare(Num a, Num b){ return a.num - b.num; }
        });
        for(int i=0; i<arr.length; i++){
            Num n = new Num(arr[i], i, i-1, i+1);
            map.put(i, n);
            this.addIfPeak(n, arr, minHeap);
        }
        return minHeap;
    }





Q2) Just similar approach :


#include<bits/stdc++.h>
using namespace std;
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int> vec(n+2);
    vec[0]  = INT_MIN;
    vec[n+1] = INT_MIN;
    for(int i=1;i<=n;i++)cin>>vec[i];
    vector<int> nextleft(n+2);
    vector<int> nextright(n+2);
    for(int i=0;i<=n+1;i++)nextleft[i] = i-1, nextright[i]=i+1;
    vector<int> ans;
    set<pair<int,int>>s;
    for(int i=1;i<=n;i++){
        if(vec[i]>vec[i-1] && vec[i]>vec[i+1])s.insert({vec[i],i});
    }
    while(!s.empty()){
        // for(auto a:s){
        //     cout<<a.first<<" ";
        // }
        // cout<<endl;
        auto val = *s.begin();
        int minval = val.first;
        int minindex = val.second;
        ans.push_back(minval);
        s.erase(s.begin());
        nextleft[nextright[minindex]] = nextleft[minindex];
        nextright[nextleft[minindex]] = nextright[minindex];
        if(nextleft[minindex]>=0){
            int newindex = nextleft[minindex];
            if(vec[newindex]> vec[nextleft[newindex]] && 
                vec[newindex] > vec[nextright[newindex]]){
                    s.insert({vec[newindex], newindex});
                }
        }
        if(nextright[minindex]<=n+1){
            int newindex = nextright[minindex];
            if(vec[newindex]> vec[nextleft[newindex]] && 
                vec[newindex] > vec[nextright[newindex]]){
                    s.insert({vec[newindex], newindex});
                }
        }
    }

    for(auto a:ans){
        cout<<a<<" ";
    }
    cout<<endl;
}

/*
9
2 7 8 5 1 6 3 9 4
*/





question 3:


public List<Integer> print2DSpiral(int[][] arrs){
    List<Integer> res = new ArrayList<>();

    Set<int[]> visited = new HashSet<>();
    int[][] directions = new int[][]{{0, 1}, {1 , 0}, {0 , -1} , {-1, 0}};
    int n = arrs.length * arrs[0].length;
    int i = 0;
    int x = 0;
    int y = 0;
    int d = 0;

    while(i < n){
        while(x >= 0 && x < arrs.length && y >=0 && y < arrs[0].length && !visited.contains(new int[]{x, y})){
            res.add(arrs[x][y]);
            visited.add(new int[]{x, y});
            i++;

            x += directions[d][0];
            y += directions[d][1];
        }

        x -= directions[d][0];
        y -= directions[d][1];

        d = ( d + 1 ) % 4;

        x += directions[d][0];
        y += directions[d][1];
    }

    return res;
}