## Amazon Interview Question

Java Developers**Country:**United States

**Interview Type:**Phone Interview

```
public static List<List<Integer>> insertInBag(List<Integer> nums) {
TreeSet<Integer> bag = new TreeSet<>();
List<List<Integer>> result = new ArrayList<>();
for (Integer i : nums) {
Integer smaller = bag.floor(i); // O(logn)
Integer higher = bag.ceiling(i);// O(logn)
ArrayList<Integer> subresult = new ArrayList<>();
if (smaller != null) {
subresult.add(smaller);
} else {
subresult.add(-1);
}
if (higher != null) {
subresult.add(higher);
} else {
subresult.add(-1);
}
result.add(subresult);
bag.add(i);
}
return result;
}
```

Can also be implemented by a creating sorted single-linked-list.

Take two variable prev and next, just before inserting an element in the bag loop through the linked list and search for an element that is bigger than the element to be inserted and this way as soon as you find a node with value more than the value to be inserted in the bag print the two values and insert the value between the two nodes.

Worst Case Complexity - O(n)

```
static void solve(int[] arr, int N){
// Please write your code here
List<Integer> temp = new ArrayList<Integer>();
int min =-1; int max = -1;
int minIndex=0; int maxIndex=0;
for (int i = 0; i <N; i++) {
temp.add(arr[i]);
if(temp.size()>1) {
Collections.sort(temp);
minIndex = temp.indexOf(arr[i])!=-1?temp.indexOf(arr[i])-1:-1;
maxIndex = temp.indexOf(arr[i])!=-1?temp.indexOf(arr[i])+1:-1;
min = (minIndex!=-1 && minIndex>-1)?temp.get(minIndex):-1;
max = (maxIndex!=-1 && maxIndex<temp.size())?temp.get(maxIndex):-1;
}
System.out.println(min + " " + max);
}
```

}

```
static void solve(int[] arr, int N){
// Please write your code here
List<Integer> temp = new ArrayList<Integer>();
int min =-1; int max = -1;
int minIndex=0; int maxIndex=0;
for (int i = 0; i <N; i++) {
temp.add(arr[i]);
if(temp.size()>1) {
Collections.sort(temp);
minIndex = temp.indexOf(arr[i])!=-1?temp.indexOf(arr[i])-1:-1;
maxIndex = temp.indexOf(arr[i])!=-1?temp.indexOf(arr[i])+1:-1;
min = (minIndex!=-1 && minIndex>-1)?temp.get(minIndex):-1;
max = (maxIndex!=-1 && maxIndex<temp.size())?temp.get(maxIndex):-1;
}
System.out.println(min + " " + max);
}
}
```

```
static void solve(int[] arr, int N){
// Please write your code here
List<Integer> temp = new ArrayList<Integer>();
int min =-1; int max = -1;
int minIndex=0; int maxIndex=0;
for (int i = 0; i <N; i++) {
temp.add(arr[i]);
if(temp.size()>1) {
Collections.sort(temp);
minIndex = temp.indexOf(arr[i])!=-1?temp.indexOf(arr[i])-1:-1;
maxIndex = temp.indexOf(arr[i])!=-1?temp.indexOf(arr[i])+1:-1;
min = (minIndex!=-1 && minIndex>-1)?temp.get(minIndex):-1;
max = (maxIndex!=-1 && maxIndex<temp.size())?temp.get(maxIndex):-1;
}
System.out.println(min + " " + max);
}
}
```

Construct a binary search tree and inset each item, return left and right nodes values as output of insertion

- Anonymous June 22, 2019