Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
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.
/**
* 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;
}
}
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 [0] (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.
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.
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.
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);
}
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);
}
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?
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);
}
The idea is to use stock span problem.
- Ayush July 26, 2014Apply 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.