Amazon Interview Question for SDE-2s

• 0

Country: United States
Interview Type: In-Person

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

``````int[] replaceNextHigher(int[] arr) {
int temp;
for(int i=0; i< arr.length; i++) {
temp = arr[i];
for(int j=i+1;j<arr.length;j++) {
if(arr[j] > temp) {
arr[i] = arr[j];
break;
}
}
}
return arr;
}``````

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

share my O(n) solution:

``````public static int[] replaceNextHigher(int[] nums){
if(nums == null || nums.length<=1){
return nums;
}

Deque<Integer> deque = new ArrayDeque<>();
int[] array = new int[nums.length];
for(int i = nums.length-1;i>=0;i--){
if(i==nums.length-1){
array[i]=nums[i];
deque.offer(nums[i]);
}else{

while(!deque.isEmpty()&&nums[i]>=deque.peekFirst()){
deque.pollFirst();
}
if(deque.isEmpty()){
array[i] = nums[i];
}else{
array[i]=deque.peekFirst();
}
deque.offerFirst(nums[i]);
}
}

return array;
}``````

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

``````public static void main(String args[]) throws Exception {
int arr[] = { 1, 2, 3, 4, 9, 5, 6 };
nextHigherElem(arr);
System.out.println(Arrays.toString(arr));
}

public static int[] nextHigherElem(int arr[]) {
int op[] = new int[arr.length];
Stack<Integer> stack = new Stack<Integer>();
for (int i = arr.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
stack.pop();
}
if (!stack.isEmpty()) {
op[i] = arr[stack.peek()];
} else {
op[i] = -1;
}
stack.push(i);
}
System.arraycopy(op, 0, arr, 0, arr.length);
return arr;
}``````

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

I m not sure why to use any exotic structures for this problem, I can think of the solution below:
a) Copy the whole array into a temporary array and sort it.
b) Iterate through each element in original array and do binary search in the sorted array to give last occurrence - not the element - but the occurrence i.e. index of the element in the sorted array. Then you get next bigger by sorted[ lastOccurrence + 1 ] if lastOccurrence < originalarray.length - 1.
Replace the original 's element with this one.

Complexity :
Space = O(n)
Time = O(nlogn) for sort
O(nlogn) for replace. - because for each i in n there is a binary search with log n time.

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

``````import java.util.Stack;
import java.util.Arrays;

public class NextHigher
{
public static void main(String[] args)
{
int[] a = {10, 5, 2, 1, 4, 6, 7};
//int[] a = {1, 2, 3};
//int[] a = {5, 4, 3, 2, 1};
//int[] a = {1, 1, 1};
NextHigher n = new NextHigher();
System.out.println(Arrays.toString(n.populateNextHigher(a)));
}

public int[] populateNextHigher(int[] a)
{
Stack<Integer> stack = new Stack<>();
int[] res = new int[a.length];
for(int i = a.length-1;i>=0;i--)
{
if(stack.isEmpty())
{
stack.push(a[i]);
res[i] = a[i];
}
else
{
while(!stack.isEmpty() && stack.peek()<a[i])
stack.pop();
if(!stack.isEmpty())
res[i] = stack.peek();
else
res[i] = a[i];
stack.push(a[i]);
}
}
return res;
}
}``````

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

@koustav.adorable. Looks like it doesn't work for 3, 7, 5.

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

We can build a Binary Search Tree, keeping mapping of idx_in_orig_array => node_in_bst.
Then, we iterate through the array. We remove the BST node of the i-th element in the array. We do a search in the BST to find the value which is next higher of the value of the i-th element. We replace the i-th element with the next higher value, if any. Then, we do the same for the next element.
Worst case time is O(N^2), because the BST can degrade into a list, and searching for the next higher value would be O(N). But expected time would be something like O(N log N).

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.