Some possible solution for the problem posted above:

balanced binary search tree will provide us with all of these operations in O(log n). If some operations are more frequent, e.g. find max, min, we can use min and max heaps to make these operations in O(1). All elements are stored in linked list and heaps store pointers to nodes, so we can remove min and max in O(1) as well. Unfortunately, delete will take O(n). Please take a look at the following links for more ideas and discussion: http://www.geeksforgeeks.org/a-data-structure-question/

Solution: This is problem can have different solutions depending on requirements. Using hash map (or better just a bit vector) to keep track of the numbers we've seen while scanning the sequence we can solve the problem in O(n) time. However, we need O(n) space. Can we do this in O(1) memory? Brute force solution could be to try all elements first and look for a duplicate in second scan, which is O(n^2) time. Can we do better?... By sorting the array first we can move duplicates together and check in a single scan, which means O(n log n) total time complexity. What if we are not allowed to modify the original list of numbers? In this case we can use binary search. Let's count how many numbers from 1 to N/2 we have in our array. If we have more than half numbers from this range, than there is a duplicate, otherwise the duplicate must be from N/2 to N-1. This solution also has O(n log n) complexity.

Next Problem:
How many tennis balls can you fit into a limousine?

Answer will be posted after 1 hour

Solution: This kind of problems might be quite surprising, but they are not uncommon. These problems test your ability to think analytically in difficult situations. You need to demonstrate that you don't panic and don't get confused. With this particular problem we need to start from the basics: how to count the number of balls? We need to know the volume of a limousine and a ball and then we can divide one by the other. Next, we can estimate the volume of a limousine, e.g. by guessing its length, width and height and making some reasonable assumptions.

Solution: A good first attempt is to realize that whenever we are dealing with sums over segments in array, we can precompute partials sums from 0 to i and then easily compute a sum on any interval as sum[i] - sum[j-1]. Using this approach we can iterate over all possible left ends of the interval and then find the right, which gives the sum closest to the given T. To do this we realize that since we only have positive integers, the sum will only increase as the interval get longer. Thus we can do binary search to find the right end. This gives us O(nlogn) solution. But we can do better. Let's start with some interval and try to grow/shrink it to make its sum closer to T. If the current sum is less than T, we know we need to grow the segment, so we move the right boundary. If the current sum is less than T we increment the left boundary. We can start with a segment that only contains a single left-most element and work our way to the right by constantly shifting either left or right end of the segment.

Solution: If the array only contained positive integers the sorted array of squares would have the same order. When we also have negative numbers their squares would interleave with squares of positive numbers. But nevertheless we have the following property: |a_i| < |a_j| => a_i^2 < a_j^2. Therefore, the smallest square would come from the smallest absolute value. We can find zero (or the place where sign of numbers change) in the original array (using binary search) and then maintain two indexes to the current negative and positive candidates. On each step we check which of these numbers have smaller absolute value and add its square to the result, while advancing the corresponding index (backwards for negatives and forward for positives).

Question: You have two sorted arrays A and B. Array A actually has some empty elements at the end, that would fit B. How to merge A and B together in sorted order?

Solution: typically, when we need to combine multiple sorted sequences into one we use merge sort. However, if we start from the beginning of A and B and store result in A we would have to move elemenets. But we can start merge sort from the end of arrays, thus filling in empty spaces in A.

Solution: Basically, each rectangle is represented by two segments on X and Y axes. Rectangles overlap if both segments overlap. Then we can compute the coordintates of vertices of the intersection by combining coordinate of left and right points of segment intersections. There is a good explanation of this idea here: https://www.interviewcake.com/question/java/rectangular-love

Solution: The first idea is to enumerate all permutations (either in lexicographical order, or sort them afterwards) and return the k-th one. But this is quite inefficient. Do we really need to generate permutations we don't care about? E.g. what if we need to return the last permutation of a string "abcd" do we need to generate permutations that start with "a"? Probably not, but can we compute what element the k-th permutation will start with? How many permutations will start with the smallest element in the array? The answer is (n-1)! Therefore, we can compute the first element of the permutation we need to compute. But wait, can we do the same for the second character? Yes we can! The number of permutations that start with the fixed first two characters are (n-2)!. So all we need to do is starting with the first character, compute what character will be on each position in the k-th permutation.

Problem: given a sorted array of integers (not necessarily positive) return a sorted array of squares of these integers.

Solution: If the array only contained positive integers the sorted array of squares would have the same order. When we also have negative numbers their squares would interleave with squares of positive numbers. But nevertheless we have the following property: |a_i| < |a_j| => a_i^2 < a_j^2. Therefore, the smallest square would come from the smallest absolute value. We can find zero (or the place where sign of numbers change) in the original array (using binary search) and then maintain two indexes to the current negative and positive candidates. On each step we check which of these numbers have smaller absolute value and add its square to the result, while advancing the corresponding index (backwards for negatives and forward for positives).

Solution: A good first attempt is to realize that whenever we are dealing with sums over segments in array, we can precompute partials sums from 0 to i and then easily compute a sum on any interval as sum[i] - sum[j-1]. Using this approach we can iterate over all possible left ends of the interval and then find the right, which gives the sum closest to the given T. To do this we realize that since we only have positive integers, the sum will only increase as the interval get longer. Thus we can do binary search to find the right end. This gives us O(nlogn) solution. But we can do better. Let's start with some interval and try to grow/shrink it to make its sum closer to T. If the current sum is less than T, we know we need to grow the segment, so we move the right boundary. If the current sum is less than T we increment the left boundary. We can start with a segment that only contains a single left-most element and work our way to the right by constantly shifting either left or right end of the segment.