Amazon Interview Question for SDE-2s


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).

- Anonymous August 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

j









hh

- Anonymous July 12, 2020 | Flag Reply
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..

- kautscoding July 13, 2020 | Flag Reply
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+" ]");
         }
     }

- Ashish Kumar Chanda July 14, 2020 | Flag Reply
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]+" ]"); 
         }
     }
}

- Ashish Kumar Chanda July 14, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anony May 20, 2021 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't work for

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

- Anony May 20, 2021 | Flag
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

- Anonymous July 15, 2020 | Flag Reply
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

- manohar July 15, 2020 | Flag Reply
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;

- kevin August 26, 2020 | Flag Reply
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
            # was this cell calculated already
            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)

- Anonymous September 20, 2020 | Flag Reply
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
            # was this cell calculated already
            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)

- shauli September 20, 2020 | Flag Reply
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 ));
        }
    }
}

- Jon W September 13, 2021 | Flag Reply
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 ));
        }
    }
}

- jon.wetherbee September 13, 2021 | 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