## Amazon Interview Question for SDE-2s

• 0
of 0 votes

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

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