How to solve this problem asked in Uber OA :-
You can assume N walls with distinct heights.
You are given an array A. A[i] denotes how many walls can be viewed if you stand after the i'th wall
Example array of walls :- [5 4 2 3 1]
A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 3 (You can view 5 , 4 , 3 -> if you stand after 3 and observe.) A[5] = 4
Given an array A ; find the count of permutations possible of size "N" ("N" walls with distinct heights from 1 to N)
Input :- A : [1 2 3 1 2]
Output :- 4
[4 3 2 5 1]
[4 3 1 5 2]
[4 2 1 5 3]
[3 2 1 5 4]
Tried many ways couldn't find any that works.
Auto comment: topic has been updated by LovesProgramming (previous revision, new revision, compare).
This problem is kind of similar to 1946E - Girl Permutation Let’s choose the biggest index i such that a[i] = 1,then p[i] = N.We divide the array into two parts: [1,i-1] and [i+1,N].There are $$$C_{N-1}^{i-1}$$$ ways to do that. Now let’s solve the left part(right part is similar). Assume the segment is [L,R], again we choose the biggest index i such that a[i] = 1 && L <= i <= R.then p[i] is the largest number in the segment,again we divide the segment into two parts:[L,i-1] and [i+1,R]. There are $$$C_{R-L}^{L}$$$ ways to do that. If the size of segment is 1 then just return 1.
In your initial statement you said (i-1)C(n-1) ways; but there is only 1 way to divide:-
(1,i-1) and (i+1,n)
What am I getting wrong
Thankyou
Let’s see your example A : [1 2 3 1 2]. First we choose a[4] = 1, we have $$$C_4^3$$$ = 4 ways to divide the array.for subarray [1,2,3] we choose a[1] = 1 and we have $$$C_2^0$$$ = 1 ways to divide.left part is empty.the contribution is 1.for the right part [2,3] we should choose the biggest index i such that a[i] = 2(since we know there is a element in the left of the segment that is larger than all the element in this part.In this case it is p[1]).then we choose a[2] and divide the segment again.the left part is empty and the right part contains only a[3].both contributions are 1.And the last segment is a[5] and the contribution is 1 too.So we have the answer = 4.
The ways to divide the array means you choose some elements for the left part and leave other elements for the right part.there is $$$C_{N-1}^{i-1}$$$ ways to choose the numbers.which number you choose doesn’t matter.
expected rating of the problem ??
Was this actually asked for an Uber interview or is it from some site that tries to get clicks by claiming it was from Uber?