## Amazon Interview Question for SDE-2s

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 11 vote

One solution can be we get the span of ith day by checking if any j<i exists such that a[j]<a[i].
If so, in that case span[i]=span[j]+1 else it will be 0.

``````void getspan(int a[],int n)
{
int span[100];
int i=0,j;
span[0]=0;
for(i=1;i<n;i++)
{
j=i-1;
while(j>=0 && a[j]>=a[i])
j--;
if(j==-1)
span[i]=0;
else
span[i]=span[j]+1;
}
for(i=0;i<n;i++)
printf("%d\t",span[i]);
printf("\n");
}``````

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

Good. Best case linear, worst case quadratic. On average it should run good for real stock prices (that go up and down).

Worst case happens if a stock keeps going down without going up.

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

there may be an element which is less then current element but greater then your 'j' element;

eg.

1,40,30,70.

according to yoy, span[1]=0;
span[40]=1;
span[30]=1;
span[70]=2...here it is wrong, as you wont be counting value '40'.

You have to used a balanced BST for this problem.

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

@nitin (right above), how to use BST?

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

This is basically the computation of smaller element count on the right. We can do it more efficiently using balanced BST such as AVL tree. We will consider each number in an array as a BST node and insert them in a AVL tree one by one from right to left. During each insert we will keep updating the size of left subtree at the node being inserted. This will give us our desired smaller element count. We also need to handle balancing the tree while insert.

A balance tree got imbalanced on an insert when the insert on a subtree rooted at a node x makes difference between left subtree and right subtree height more than 1. We will have to consider 4 cases:

1) Insert-in-left-of-left-subtree of x: we can balance by rotating x right
2) Insert-in-right-of-right-subtree of x: we can balance by rotating x left
3) Insert-in-right-of-left-subtree of x: we need two rotations: balance left of x by rotating left. And then a right rotation of x.
4) Insert-in-left-of-right-subtree of x: we need two rotations: balance right of x by rotating right. And then a left rotation of x.

Time complexity will be O(nlgn) and space is O(n).

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

The above solution by zahidbuet106 is simply AWESOME.

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

This is basically the computation of smaller element count on the right. We can do it more efficiently using balanced BST such as AVL tree. We will consider each number in an array as a BST node and insert them in a AVL tree one by one from right to left. During each insert we will keep updating the size of left subtree at the node being inserted. This will give us our desired smaller element count. We also need to handle balancing the tree while insert.

A balance tree got imbalanced on an insert when the insert on a subtree rooted at a node x makes difference between left subtree and right subtree height more than 1. We will have to consider 4 cases:

1) Insert-in-left-of-left-subtree of x: we can balance by rotating x right
2) Insert-in-right-of-right-subtree of x: we can balance by rotating x left
3) Insert-in-right-of-left-subtree of x: we need two rotations: balance left of x by rotating left. And then a right rotation of x.
4) Insert-in-left-of-right-subtree of x: we need two rotations: balance right of x by rotating right. And then a left rotation of x.

Time complexity will be O(nlgn) and space is O(n).

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

This can be solved simply by maintaining a Min and max stock price.

Globals
int Size = 100; //Some large value
int StockStack[size];
int Min = 32767; //Some large sentinel value
int Max = -1;
int spanOfStack( int StockPriceForTheDay)
{
int count = 0;

if(StockPriceForTheDay <= Min)
{
Min = StockPriceForTheDay;
StockStack.push(Min);
return -1;
}
else if(StockPriceOfTheDay >= Max)
{
Max = StockPriceOfTheDay;
StockStack.push(Max);
return StockStack.NumberOfElements();
}
else
{
StockStack.push(StockPriceForTheDay);
for(int i=0;i<StockStack.NumberOfElements();i++)
{
if(StockStack[i]<StockPriceForTheDay)
count++;
}

return count;
}

}

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

insert the values to the Linked List in sorted order.
Increment the span to index while inserting.

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

could sort them by the stock prices preserving the original index, the number of the span will be the new index minus the number of pairs which the previous element's original index is higher than the current one.e.g:
input:{2,4,6,9,5,7,1};
internal sorted result {1,2,4,5,6,7,9} with index{6,0,1,4,2,5,3}
output:{-1,1,2,3,2,3,-1}
expected time complexity o(nlogn) + o(n)
space complexity o(n)

``````#include <algorithm>
#include <utility>
#include <iostream>

vector<int>& calculateSpan(const vector<int>& stock_prices) {
// result of the span calculation
vector<int> *span = new vector<int>(stock_prices.size(), -1);
if (span->size() > 1) {
// sorted the stock prices, preserving the original index
vector<pair<int, int> > sorted_prices;
for (int i = 0; i < stock_prices.size(); ++i) {
sorted_prices.push_back(make_pair(stock_prices[i], i));
}
sort(sorted_prices.begin(), sorted_prices.end());

// whenever we find a value with its index lower than the previous one, we
// increase the count
int higher_index_count = 0;
for (int i = 1; i < sorted_prices.size(); ++i) {
if (sorted_prices[i].second < sorted_prices[i - 1].second) {
++higher_index_count;
}
// the span is calcuated by the index minus the higher index count
const int number_of_span = i - higher_index_count;
(*span)[sorted_prices[i].second] = number_of_span == 0? -1: number_of_span;
}
}
return *span;
}``````

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

please try the input(2, 4, 6, 9, 5, 10)
the output should be (-1, 1, 2, 3, 2, 5)

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

The solution can be found in O(n) using a stack and is present in many algorithm text books.

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

this is not the traditional stock span problem, the definition of span here is different, here span is "the amount of days before the given day where the stock price is less than that of given day", it's not "number of consecutive days just before the given day" as the traditional stock span problem, don't think the stack approach works.

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

``````int[] span(int[] stockValues) {
int[] out = new int[stockValues.length];
SortedMap<Integer, Integer> map = new TreeMap<Integer, Integer>();

for (int i = 0; i<stockValues.length;i++) {
int stockValue = stockValues[i];
int frequency = 0;
if (map.containsKey(stockValue))
frequency = map.get(stockValue);
map.put(stockValue, ++frequency);

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getKey() < stockValue) out[i] = out[i]+entry.getValue();
else break;
}
}

return out;
}``````

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

For each entry have another count variable which keeps track of how many entries are less than that in the list. Have a bst constructed for each entry. That way for finding number of entries less than n we can go to the inorder predecessor of n, get its count and do a +1.

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

this can be done using avl tree,

every time we insert a stock value we check how many values are less than that of the present stock value being inserted.

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

I was trying to find solution faster than O(N*N), but I could not.
Here is a solution in python

``````def find_max_span(data):
output = []
for i in range(0, len(data)):
current = data[i]
count = -1
for j in range(0, i):
if (data[j] < current):
if (count==-1):
count =1
else:
count+=1
output.append(count)
return output``````

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

This can be solved in nlogn time using a same approach as calculating number of inversion pairs. Just change the definition of inversion to be A[i] < A[j].

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

``````import java.io.*;
import java.util.*;

class Inversions
{
public static void main (String args[])  // entry point from OS
{
Scanner s, ls;
int L, listNum = 1;

s = new Scanner(System.in);  // create new input Scanner

ls = new Scanner(s.nextLine());
L = ls.nextInt();

while(L > 0)    /*  While there's more data to process...  */
{
/*  Create an array to hold the integers  */
int nums[] = new int[L];

ls = new Scanner(s.nextLine());
/* Check that we are putting them in reverse order here
So if i/p is (2, 4, 6, 9, 5, 10), nums[] will be 10 5 9 6 4 2
for (int j = L; j < 0; j++)
nums[j] = ls.nextInt();

/*  Compute the number of inversions, and print it out  */
System.out.print( "List " + listNum + " has " );
System.out.println ( countInversions(nums) + " inversions.");

/*  Read in the next value of L  */
listNum++;
ls = new Scanner(s.nextLine());
L = ls.nextInt();
}

}  /*  end of "main" procedure  */

public static int countInversions(int nums[])
/*  This function will count the number of inversions in an
array of numbers.  (Recall that an inversion is a pair
of numbers that appear out of numerical order in the list.

We use a modified version of the MergeSort algorithm to
do this, so it's a recursive function.  We split the
list into two (almost) equal parts, recursively count
the number of inversions in each part, and then count
inversions caused by one element from each part of
the list.

The merging is done is a separate procedure given below,
in order to simplify the presentation of the algorithm
here.

Note:  I am assuming that the integers are distinct, but
they need *not* be integers { 1, 2, ..., n} for some n.

*/
{
int mid = nums.length/2, k;
int countLeft, countRight, countMerge;

/*  If the list is small, there's nothing to do.  */
if (nums.length <= 1)
return 0;

/*  Otherwise, we create new arrays and split the list into
two (almost) equal parts.
*/
int left[] = new int[mid];
int right[] = new int[nums.length - mid];

for (k = 0; k < mid; k++)
left[k] = nums[k];
for (k = 0; k < nums.length - mid; k++)
right[k] = nums[mid+k];

/*  Recursively count the inversions in each part.
*/
countLeft = countInversions (left);
countRight = countInversions (right);

/*  Now merge the two sublists together, and count the
inversions caused by pairs of elements, one from
each half of the original list.
*/
int result[] = new int[nums.length];
countMerge = mergeAndCount (left, right, result);

/*  Finally, put the resulting list back into the original one.
This is necessary for the recursive calls to work correctly.
*/
for (k = 0; k < nums.length; k++)
nums[k] = result[k];

/*  Return the sum of the values computed to
get the total number of inversions for the list.
*/
return (countLeft + countRight + countMerge);

}  /*  end of "countInversions" procedure  */

public static int mergeAndCount (int left[], int right[], int result[])
/*  This procudure will merge the two lists, and count the number of
inversions caused by the elements in the "right" list that are
less than elements in the "left" list.
*/
{
int a = 0, b = 0, count = 0, i, k=0;

while ( ( a < left.length) && (b < right.length) )
{
if ( left[a] <= right[b] )
result [k] = left[a++];
else       /*  You have found (a number of) inversions here.  */
{
result [k] = right[b++];
count += left.length - a;
}
k++;
}

if ( a == left.length )
for ( i = b; i < right.length; i++)
result [k++] = right[i];
else
for ( i = a; i < left.length; i++)
result [k++] = left[i];

return count;
}

}  /*  end of "Inversions" program  */``````

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

not clear question please explain more

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

This was just having fun and answering quickly. Linked list sure is a nice soln though.

``````public class MaxStockPriceSpan {

/**
Max span is number of days before this day that the price was lower than todays.
I/P is an array of prices ordered by days.
*/
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
int[] in = {2, 4 ,6 ,9, 5, 1};
List<Integer> out = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
for (int n : in) {
while (!minHeap.isEmpty() && minHeap.peek() < n) {
int temp = minHeap.poll();
stack.push(temp);
}
minHeap.offer(n);
if (stack.isEmpty()) {
}
else {
while (!stack.isEmpty()) {
int temp = stack.pop();
minHeap.offer(temp);
}
}
}
System.out.println("The min span array for " + Arrays.toString(in) + " is " + Arrays.toString(out.toArray()) + ".");
}
}``````

I also think the balanced search tree idea deserves a look. Seems like it would make sense since what we're looking for is a data struct that's always sorted and which gives you the index of a member on request -- like the linked list solution does "manually."

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

void getspan(int a[],int n)
{
int span[50];
int i,j;
span[0]=0;
for(i=1;i<n;i++)
{

for(j=0;j<i;j++){
if(a[i]>a[j])
span[i]=span[j]+1;
}
}
for(i=0;i<n;i++){
printf("%d\t",span[i]);
printf("\n");
}
}

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

Just came up with a simple idea of maintaining a sorted list.
So my algorithm would look like this.

(1) Initialize Sorted List
(2) Using binary search check the lower bound of the key to be inserted in the sorted list, if it is at x then put x in the span[i], (exception: if x == 0, then span[i] = -1)

So the sorted list would keep on growing, but the advantage is that it is simpler than maintaining a tree or a balanced BST. Moreover, it is always sorted and we can calculate the lower bound of an element to be inserted (also called lower bound insertion point) in logarithmic time.

If we maintain a dynamic array-like structure for the sorted list then insertion would be constant time.

Overall runtime should be under **nlogn** which is fairly satisfactory for this problem.

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

The solution could be achieved in nlogn complexity

Deatils:
construct BST and keep adding +1 when moving to right tree and dont increment anything when moving in left part of the tee.

for root-> -1(output)
for node having 0 as incremnet count(output -1)
and >0 output whatever is the count.

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

Consider the following input: {1,2,3,4,5}. In this case, you will have N^2 time complexity. The same goes if the input is {5,4,3,2,1}.

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

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.