0 like 0 dislike
968 views

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

https://oa.desiqna.in

https://interview.desiqna.in

| 968 views

0 like 0 dislike
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&rsquo;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
by Expert (46,090 points)
0 like 0 dislike
```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<>());
}
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();
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;
}
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;
}
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);
}
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})){
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;
}```

```
by Expert (46,090 points)