## Amazon Interview Question for SDE-2s

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

The idea is to use stock span problem.
Apply stock span problem on an the array and its reverse.
Store the results of stock-span of array and its reverse in left[] and right[] auxiliary arrays.

return left[i]+right[i].

See the code of stock span on GeeksforGeeks.

Comment hidden because of low score. Click to expand.
0

Consider heights {100, 80, 60, 70, 60, 75, 85} (taken from stockspan in geeksforgeeks). According to stockspan logic for the element 5(75) the poles 2(60), 3(70), 4(60) will be visible on the left. But since element 3(70) is taller than element 2(60) effectively hiding it from element 5(75). Should it be considered or ignored.

Comment hidden because of low score. Click to expand.
0

Ayush, you're right with that use case. It's not clear from the problem statement. Also fro your example, could 5(75) be able to see 1(80) and 0(100)? If you plot it, it looks possible.

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````/**
* Given an array with the heights of the poles and the standing position of the observer,
* determines how many poles are visible to the observer.
* @author tcslesa
*
*/
public class MaxNoOfVisiblePolls {
public static void main(String[] args) {
MaxNoOfVisiblePolls max = new MaxNoOfVisiblePolls();
int maxPoles = max.getVisiblePoles(new int[]{5, 4,6,1,3,7,6,8,1}, 6);
System.out.println(maxPoles);
}

public int getVisiblePoles(int a[], int pos){
/*
* visible poles on the left + visible poles on the right + pole at the position itself
*/
return getMaxLeft(pos, a)+getMaxRight(pos, a)+1;
}

private int getMaxLeft(int position, int a[]){
int count = 1;
int maxHeight = a[position-1];
/*
* Start from the pillar next to the position on the left and reach till the first one
*/
for(int i=position-2; i>=0; i--){
if(a[i] > maxHeight){
maxHeight = a[i];
count ++;
}
}
return count;
}

private int getMaxRight(int position, int a[]){
int count = 0;
int length = a.length;
int maxHeight = 0;
/*
* Start from the pillar next to the position on the right and reach till the last one
*/
for(int i=position+1; i<length; i++){
if(a[i] > maxHeight){
maxHeight = a[i];
count ++;
}
}

return count;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

can we do it in a better way than O(n^2) if we are goint to calculate answer for all ...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Whenever a max height pole comes, It will cover all the left poles. We have to keep the track of the maximum height pole before i.
Just iterate on the array, by setting the max = a  (first element of the array). Whenever you encounter a number during traverse a [index] > max. Reset ​the maximum and save its index. At ith index check for it will give the number of poles visible.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Good question, though the problem statement is a bit vague. I assume that the problem is asking to find out all the elements to the left and right of the current element in the array that are greater than current element.

One approach is to use two cumulative arrays - one that stores the count of elements greater than the current element to it's right and the other to store the count of elements greater than the current element to it's left.

The cumulative arrays are computed by building BSTs so during the insertion of an element, we figure out the number of elements that are greater. We need to build two BSTs - one while traversing the array forward and the other while traversing the array backward.

Comment hidden because of low score. Click to expand.
3

Just realized that simple count won't suffice, need to figure out monotonically increasing subsequences from left to right as well as from right to left of the given element.

Comment hidden because of low score. Click to expand.
1
of 1 vote

if you are standing on the ith pole then you can obviously see the pole (i+1)th pole, even if the (i+1)th pole is smaller than the pole on which you are standing

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void FindNumOfVisiblePoles(int[] poleHeights, int i)
{
int l = poleHeights.Length;
int j = i - 1;
int k = i + 1;
int count = 0;
while (j >= 0)
{
count++;
if (poleHeights[j] >= poleHeights[i])
break;
j--;
}
while (k < l)
{
count++;
if (poleHeights[k] >= poleHeights[i])
break;
k++;
}
Console.WriteLine(count + 1);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int main(){
int x = 0, i, count = 0;
highest = 0;
for(x = i+1; x < right_boundary ; ++x){
if(arr[i] > arr[x] && !highest) ++count
else if(arr[i] <= arr[x] && arr[x] >= highest){++count; highest = arr[x];}
}
highest = 0;
for(x = i-1; x >= 0; --x){
if(arr[x] < arr[i] && !highest) ++count;
else if(arr[x] >= arr[i] && arr[x] >= highest){++count; highest = arr[x];}
}
printf("%d", count);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since this question was put here, I have another one for you guys... I used to ask a small variation of this question when I was interviewing candidates.

Given the array of pole heights, find me the pole that sees more poles. You can easily expand the solutions above to find a O(n^2) solution, but can you give me a O(n) solution?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sort the array and number of poles visible will be i-1.

Comment hidden because of low score. Click to expand.
0

I don't see how sorting will work. Consider pole heights in this order {5,7, 6}. Sorting would indicate that both the 7' and 6' pole woiuld be visible, but the 7' pole actually blocks the visibility of the 6' pole.
Am I missing something here?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void FindNumOfVisiblePoles(int[] poleHeights, int i)
{
int l = poleHeights.Length;
int j = i - 1;
int k = i + 1;
int count = 0;
while (j >= 0)
{
if (poleHeights[j] <= poleHeights[i])
{
count++;
}
j--;
}
while (k < l)
{
if (poleHeights[k] <= poleHeights[i])
{
count++;
}
k++;
}
Console.WriteLine(count + 1);
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.