## Amazon Interview Question for SDE-2s

• 4

Country: United States

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

No need of segment tree it will use 2*n space at max. It could be done by as follows:
take stacks and for every element find position of next and previous max that will we the range. Run time complexity will be O(n).

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

j

hh

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

Can be solved using segment tree in nLog(n).. Not sure if better could be done..

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

``````public static void amzQ(int[] nums){
if(nums == null) return;
for( int i =0; i < nums.length; i++){
int j  = i-1, k = i+1;
while( !(j < 0  || nums[j] > nums[i])){
j--;
}
while( !(k > nums.length-1  || nums[k] > nums[i])){
k++;
}
System.out.println(""+nums[i] +" [ "+ (j+2)+"  "+ k+" ]");
}
}``````

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

``````//O(2*N)
public class HelloWorld{
public static void main(String []args){
int[] arr = { 1,5,4,3,6,10,1,3,2,11};
amzQ(arr);
}
public static void amzQ(int[] nums){
if(nums == null) return;
int len = nums.length;
int[] leftIdx = new int[len];
leftIdx[0]=1;
int[] rightIdx =new int[len];
rightIdx[len-1]=len;
amzQ(nums,leftIdx, rightIdx );
}
public static void amzQ(int[] nums,int[] leftIdx,int[] rightIdx ){
int max = nums[0], maxIdx = leftIdx[0];
for( int i =1; i < nums.length; i++){
if( max < nums[i]){
max = nums[i];
leftIdx[i] = leftIdx[0];
}
if(nums[i-1] > nums[i]){
leftIdx[i] = i+1;
}else{
if(nums[i] != max){
leftIdx[i] = leftIdx[i-1];
}
}
}
max = nums[nums.length-1];
maxIdx = rightIdx[nums.length-1];
for( int i = nums.length-2; i >= 0; i--){
if( max < nums[i]){
max = nums[i];
rightIdx[i] = maxIdx;
}
if(nums[i+1] > nums[i]){
rightIdx[i] = i+1;
}else{
if(nums[i] != max){
rightIdx[i] = rightIdx[i+1];
}
}
}
for(int i =0; i < nums.length; i++){
System.out.println(""+nums[i]+" ["+leftIdx[i] +
" "+rightIdx[i]+" ]");
}
}
}``````

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

doesn't work for int[] arr = { 1, 6, 4, 3, 5};

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

doesn't work for

``int[] arr = { 1, 6, 4, 3, 5};``

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

numbers = int(input('numbers :'))
while numbers<=3:
# print('*' * i)
print(range(numbers))
numbers=numbers+1

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

numbers = int(input('numbers :'))
while numbers<=3:
# print('*' * i)
print(range(numbers))
numbers=numbers+1

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

[1,5,4,3,6]
[[1,1], [1,4], [3,4],[4,4],[1,6]]

i = 0, j =

``stack<pair<int,int>> prevmax, nextmax;``

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

For finding the low (left-hand) MAX of a[i]:
1. If a[i-1] > a[i], return i
2. If we don't know yet the MAX range of a[i-1], find it (recursively)
3. Use the low MAX of a[i-1] to skip elements which are surely smaller than a[i]
4. Repeat steps 2-4 as long as we don't see an element higher than us

``````import random

class Cell():
def __init__(self, pos, val):
self.pos, self.val = pos, val
self.low, self.high, self.queued = -1, -1, False

def get_border(self, side):
return self.low if side < 0 else self.high

def __str__(self):
return ' '.join(["[", str(self.pos), "]", str(self.val),
"(", str(self.low), "->", str(self.high), ")"])

class Array():
def __init__(self, arr):
self.arr = [ Cell(pos, val) for pos, val in enumerate(arr) ]
self.queue = []
self.enqueue( self.arr[ len(self.arr) // 2 ] )

def enqueue(self, cell):
if cell.queued or cell.low > 0:
return
cell.queued = True
self.queue.append(cell)

def dequeue(self):
cell = self.queue.pop()
cell.queued = False
return cell

def process(self):
while len(self.queue):
cell = self.dequeue()
if cell.low < 0:
self.find_range(cell)

def find_range(self, cell):
cell.low = self.find_border(cell, -1)
cell.high = self.find_border(cell, 1)

def find_border(self, cell, delta):
cand = cell.pos + delta
last_cell = cell
while True:
# check array borders
if cand < 0:
return 0
if cand >= len(self.arr):
return len(self.arr) - 1
cand_cell = self.arr[cand]
# check if we reached a cell higher than us
if cand_cell.val > cell.val:
self.enqueue(cand_cell)
# return the position of the last cell which was
# smaller/equal to us
return last_cell.pos
if cand_cell.low < 0:
self.find_range(cand_cell)
# use cand's own low/high max to skip over values
# which are surely smaller than us
next_cand = cand_cell.get_border(delta)
if next_cand == cand:
# nothing to skip here, so keep crawling in the same direction
next_cand = cand_cell.pos + delta
cand = next_cand
last_cell = cand_cell

def __str__(self):
out = ""
for c in self.arr:
out += str(c) + "\n"
return out

a = [ random.randint(1,100) for i in range(100) ]
arr = Array(a)
arr.process()
print(arr)``````

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

``````import random

class Cell():
def __init__(self, pos, val):
self.pos, self.val = pos, val
self.low, self.high, self.queued = -1, -1, False

def get_border(self, side):
return self.low if side < 0 else self.high

def __str__(self):
return ' '.join(["[", str(self.pos), "]", str(self.val),
"(", str(self.low), "->", str(self.high), ")"])

class Array():
def __init__(self, arr):
self.arr = [ Cell(pos, val) for pos, val in enumerate(arr) ]
self.queue = []
self.enqueue( self.arr[ len(self.arr) // 2 ] )

def enqueue(self, cell):
if cell.queued or cell.low > 0:
return
cell.queued = True
self.queue.append(cell)

def dequeue(self):
cell = self.queue.pop()
cell.queued = False
return cell

def process(self):
while len(self.queue):
cell = self.dequeue()
if cell.low < 0:
self.find_range(cell)

def find_range(self, cell):
cell.low = self.find_border(cell, -1)
cell.high = self.find_border(cell, 1)

def find_border(self, cell, delta):
cand = cell.pos + delta
last_cell = cell
while True:
# check array borders
if cand < 0:
return 0
if cand >= len(self.arr):
return len(self.arr) - 1
cand_cell = self.arr[cand]
# check if we reached a cell higher than us
if cand_cell.val > cell.val:
self.enqueue(cand_cell)
# return the position of the last cell which was
# smaller/equal to us
return last_cell.pos
if cand_cell.low < 0:
self.find_range(cand_cell)
# use cand's own low/high max to skip over values
# which are surely smaller than us
next_cand = cand_cell.get_border(delta)
if next_cand == cand:
# nothing to skip here, so keep crawling in the same direction
next_cand = cand_cell.pos + delta
cand = next_cand
last_cell = cand_cell

def __str__(self):
out = ""
for c in self.arr:
out += str(c) + "\n"
return out

a = [ random.randint(1,100) for i in range(100) ]
arr = Array(a)
arr.process()
print(arr)``````

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

``````public class Amazon {
public static void main(String[] args) {
int[] arr = { 1,5,4,3,6 };
int l,r;
for (int i=0; i<arr.length; i++) {
for (l = i; (l >= 0) && (arr[l] <= arr[i]); l--) {
}
l+=2;
for (r = i; (r<arr.length) && (arr[r] <= arr[i]); r++) {
}
System.out.println(String.format("%d [%d,%d]", arr[i], l, r ));
}
}
}``````

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

``````public class Amazon {
public static void main(String[] args) {
int[] arr = { 1,5,4,3,6 };
int l,r;
for (int i=0; i<arr.length; i++) {
for (l = i; (l >= 0) && (arr[l] <= arr[i]); l--) {
}
l+=2;
for (r = i; (r<arr.length) && (arr[r] <= arr[i]); r++) {
}
System.out.println(String.format("%d [%d,%d]", arr[i], l, r ));
}
}
}``````

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.