CareerCup

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

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)

This is an ideal case for an AVL tree implementation. Print the boundary values before rotation. Worst case complexity for insertion is O(logn).

(Surprised they asked this in an interview)

when to put inside bag condition???

This question is from a Hackerearth coding context and not from Amazon interview

Construct a sorted DLL for every insertion and return the prev and next pointer everytime.
return -1 if any neighbor is NULL

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);
        }
    
    }