1. Given an array of size N+1 has integers in range 1 to N. Find one duplicate. Memory allocation should be constant and way less than N, time complexity should be better than N2.\n2. You are given a string with a valid expression containing digits, +- \nWrite int[] eval(string s) so it returns all different combinations of evaluations for example:\n"1+2*3" should return [7,9]\n3. Write a function that inserts a value to BST. Write a function that prints a tree level by level starting from a tree root.\n4. Design an airline tickets search system.

Given an array of size N+1 has integers in range 1 to N. Find one duplicate. Memory allocation should be constant and way less than N, time complexity should be