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.

- Ayush July 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- livingstone.s.e August 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- andres.santana August 31, 2014 | Flag
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;
	}
}

- OLS July 31, 2014 | Flag Reply
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 ...

- Rahul Sharma July 26, 2014 | Flag Reply
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 [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.

- Anonymous July 26, 2014 | Flag Reply
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.

- Murali Mohan July 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

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.

- Murali Mohan July 28, 2014 | Flag
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

- gdg July 31, 2014 | Flag
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);
}

- ShaRai August 11, 2014 | Flag Reply
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);
}

- Punit Patel August 14, 2014 | Flag Reply
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?

- daniel.a.p September 24, 2014 | Flag Reply
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.

- maniscareer2014 August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- spneuman August 11, 2014 | Flag
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);
}

- Anonymous August 11, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More