Amazon Interview Question
SDE-2sCountry: United States
//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]+" ]");
}
}
}
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)
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)
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 ));
}
}
}
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 ));
}
}
}
#include <iostream>
#include <vector>
#include <stack>
#include <utility>
// Utility function to find the next greater element positions for each element
void findNextGreaterElements(const std::vector<int>& nums, std::vector<int>& left, std::vector<int>& right) {
int n = nums.size();
std::stack<int> s; // Stack to store indices
// Find next greater element positions on the right
for (int i = 0; i < n; ++i) {
while (!s.empty() && nums[s.top()] < nums[i]) {
right[s.top()] = i;
s.pop();
}
s.push(i);
}
// Clear the stack to reuse it
while (!s.empty()) s.pop();
// Find next greater element positions on the left
for (int i = n - 1; i >= 0; --i) {
while (!s.empty() && nums[s.top()] < nums[i]) {
left[s.top()] = i;
s.pop();
}
s.push(i);
}
}
// Function to find and print ranges where each element is the maximum
void printMaxElementRanges(const std::vector<int>& nums) {
int n = nums.size();
std::vector<int> left(n, -1); // Position of next greater element on the left
std::vector<int> right(n, n); // Position of next greater element on the right
findNextGreaterElements(nums, left, right);
for (int i = 0; i < n; ++i) {
// Adjust the range according to the problem statement
std::cout << nums[i] << " [" << (left[i] + 2) << ", " << (right[i]) << "]" << std::endl;
}
}
int main() {
std::vector<int> nums = {1, 5, 4, 3, 6};
printMaxElementRanges(nums);
return 0;
}
No need of segment tree it will use 2*n space at max. It could be done by as follows:
- Anonymous August 17, 2020take stacks and for every element find position of next and previous max that will we the range. Run time complexity will be O(n).