Microsoft Amazon Interview Question Software Engineer / Developers Software Engineer in Tests
As others pointed out I changed the post.
If n*logn >>> max(array)-min(array)
or if max(array)-min(array) is approximately close to n then the following algorithm gives better complexity
Space complexity: O(max(array)-min(array))
Time complexity: O(max(array)-min(array))
-> Find 'max' and 'min' of the array = O(n)
-> Create a bitset 'B' of size 'max'-'min' initialized to 0's = O(1)
-> For every element 'i' in the array = O(n)
set B[array[i]-min] = 1
-> Find the closest distance between 1's in the bitset 'B'. = O(max(array)-min(array))
that is the minimum difference
This works only for +ve numbers.
In order to make this work for -ve numbers also, you need to either create a bitset for negative numbers or shift all numbers by Abs(min) (I mean add Abs(min) for every number in the array) if min < 0 and then shift back the answer.
Is the complexity O(n)? Your input could be {0,10000000000}. You'll be iterating through a set with 10000000000 entries but the input size was only 2...
put these number in binary tree , track the difference between parent and current number being inserted . always update this number whenever difference between parent and inserted is hcanges
@S the algorithm does consider the minimum which could be negative. I think it should work
@Anonymous. Yep my bad. The complexity is indeed O(max(array)-min(array))
@Rakesh. Not sure what you are talking about. There's no tree
Find the min and find the max then min-max is -ve and it would be the minimum difference. Does the question say "minimum positive difference" or phrase it another way, "the distance between two numbers should be minimum when plotted on number line"??
If it is minimum positive difference then I don't think it can be done in O(n). Please correct me if I am wrong.
A divide-and-conquer based approach seems workable which keeps track of min,max and min_difference of subproblems. When two subproblems, say A and B are merged,
min_difference_AB = Min ( min_difference_A, min_difference_B, max_A - min_B ) if max_A < min_B
min_difference_AB = Min ( min_difference_A, min_difference_B, max_B - min_A ) if max_B < min_A
It's O(n) time and space complexity.
I found a small flaw here:
when two subproblems are merged, we need to compare 4 cases all together, and take the minimum of all.
If space is not a constraint, we can store the number as the key for another array and 1 as the value for those keys. When we parse this new array, minimum distance between 1s will give the answer.
eg: 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
a[1] =0
a[2] =0
a[3] =0
a[4] =0
a[5] =1
a[6] =0
a[7] =0
so on
1. Arrays.sort(arr);
2. min = Integer.MAX_VALUE;
3. for i = 0 .. n-2
if(arr[i+1] - arr[i] < min)
min = arr[i+1] - arr[i];
4. return min;
How about using Heap; First create Heap cost O(n). Then every node in the heap only need to compare with the lower level. In this way, there are at most 2n comparison. In this way, the time complexity is O(n).
why just lower level?
Consider following heap:
5
9 10
20 14 16 27
The answer should be 1, (9, 10)
Can't this question boils down to problem of minding first two maximum number and first two minimum numbers. Then find the minimum of |(max1-max2)| and |(min1-min2)|.
If it can, then solution is O(n) - time complexity and O(1) space complexity.
Please comment ..
Dirichlet_drawer_principle or Pigeonhole principle
See: http: / / en.wikipedia. org /wiki/Dirichlet_drawer_principle
Suppose there are n numbers
1.find max and min - O(n)
2.calculate diff = (max - min) / (n-1) - O(1)
3.take diff as a drawer, put n numbers into each drawer - O(n)
4.for each drawer, there are at most two numbers, then find the minimal diff easily - O(n)
find the maximum and minimum elements in the set in O(n) time. The minimum difference is minimum-maximum. For minimum non-negative difference, check this link
stackoverflow.com/questions/1669922/is-it-possible-to-find-two-numbers-whose-difference-is-minimum-in-on-time
I think Difference in this problem is defined as abs(A[i] - A[j]).
Hence your algorithm will not work in the case.
I will use divide and conquer approach. I am considering it as an array.
Lets have two vars, int lower and int min.
int arr[]= {2,4,5,7,10,1,20,14,2}
start with middle element..say at index 4 i.e. arr[4] = 10
now lower would be index of previous element..3
i will go backwards by decreasing value of lower till it becomes 0 and i will subtract each element from arr[4] and will store result in 'min'.
so min = 10-6 = 4,
lower--;
if(10-7)<min then min = 10-7 = 3 and so on.
when lower reaches 0 will increment array index..ie. I will take the current element as arr[5] and repeat the same procedure again..finally i will get min value as minimum difference.
I am not sure about the complexity..can anyone tell me??
I assume that you want to find two numbers such that index of the second number is greater than the first and their difference is minimum..(in the case given i suppose its 5 - 20 = -15.
We could use the dynamic programming approach since space is not an issue. You create another array - partner[i] denoting the index of the other element such that the difference is minimal(min a[i] - a[j] && partner[i] = j)
this takes O(n).
public class MinimumDiffAmongNum {
public static void main(String[] args) {
int [] arr = {5,7,75,2,62,10,1};
int min1 = arr[0];
int min2 = arr[0];
for(int i=1;i<arr.length;i++){
if(min1 > arr[i]){
min2 = min1;
min1=arr[i];
}
}
System.out.println("Minimum Difference :" +(min2 - min1));
}
}
scan from begin to end, find the 2 largest numbers, the difference is got to be minimum among them.
Time Complexity: O(N)
Space Complexity: O(N+2)
I think that the blueskin solution would work for a majority of numbers..but what happens when the numbers are
7,20,1,4
Here we have two numbers producing the same minimum difference i.e.(7,4) and (4,1).
I have a solution in my mind..please comment on this and its time complexity..is it taking O(n) or more
Consider the first two numbers - (7,20). Finds its difference which is 13
Now take the next number - 1. Calculate 7-1 = 6 and 20-1 = 19. As the difference 6 <13. Now consider (7,1) as u r next set.
Now again 7-1 = 6.
The next number is 4. And 7-4 = 3 and 4-1 = 3. As both of the sets produce the same difference. The answer shd be either (7,4) or (4,1).
I think this solution works with every list. Please comment on this.
If the numbers are within ranges like 10^9 (around 3MB) We can have a bitmap to perform sorting in O(n).
then Once the sorted order is obtained , we can get the difference in the numbers in O(n) ; store them in an array for reference. we can sort the difference using another bitmap. Now we have the best difference. we can go through the array with the corresponding difference to get the position of the combination|s in O(n).
this takes < O(n) space.
The approach makes sense but sorting the difference is not required. You just need to keep a variable for min and continuously update it whenever any difference is lesser.
I've just been struck with this idea, and it seems all right to me...
It can be done in 3 steps each with order n.
1. Find out the difference of all the numbers from the first number (NOT the absolute difference).
e.g. Numbers are: 30, 19, 43, 14, 11, 40, 52, 18
Differences come out to be: 0, 11, -13, 16, 19, -10, -22, 12
2. Find 5 numbers(all can b found in order n): the smallest, the second smallest, the largest, the second largest, and the smallest with the absolute value, except for the first zero, from the sequence of differences. (say a, b, z, y, m)
e.g.
a=-22
b=-13
m=-10 (coz |-10|=10, the smallest)
y=16
z=19
3. Compare the values abs(a-b), abs(y-z), abs(m).
If it turns out abs(a-b) or abs(y-z) is the smallest value, the values with min difference will be the ones that gave the differences a and b, or x and y.
e.g. abs(a-b)=9
abs(y-z)=3
abs(m)=10
therefore, the numbers with min diff are the ones that gave y=16 and z=19 as differences, viz, 14 and 11 respectively.
Had abs(m) been the difference, we would have taken the number that gave m as the difference (10 in above example)
Not sure this can be solved in O(n). One thing that's not entirely clear to me is whether negative numbers are allowed or not. I'm assuming that only Natural numbers are allowed. If Integers are allowed, I find it even unlikely that it can be solved in O(n). In any case, I came up with the following algorithm.
It works by keeping a hash table of size 3n, maximum space constraint allowed, where the values of the array are kept for fast search. Then it starts with a guess, by picking two random numbers, from different indices of the array, and computing the difference between then. This is the initial guess. From then on, it's basically about improving that initial guess. This works by checking the hashtable for an element "n" such that a_i - n < guess. This can be done in O(1) by searching the hashtable for the key (a_i - guess). The guess is improved by trying to find a difference of 0 first, then up until the current guess - 1. The algorithm will run quicker and quicker as it executes, as the guess will keep on getting smaller and smaller. I'm guessing that this improvement bit will run in O(cn), where "c" is related to how quick the guess goes from the initial down to the minimal. On a quick thought, I find it very unlikely that to ever get to O(n^2). So, total running time would be O((c+1)n). That'd be my guess. Comments are mostly welcome.
Space complexity is clearly O(3n).
- emerson.loureiro February 06, 2011H = hash(A) // O(n) n1 = random(A) n2 = random(A) // Two random values picked such that the index of n1 isn't the same as the index of n2 g = | n1 - n2 | // Guess is the absolute value of the difference between random numbers while not stop a_i = A[i] // Tries to improve the guess, for each a_i in A in the worst case for j = 0 up to (g - 1) // Improvements on the guess n = H.find(a_i - j) // Tries to find an entry "n" in the hash such that a_i - n = j if n and n != i g = j // Found a better difference n1 = a_i n2 = a_i - j end if if g = 0 stop // No difference can be less than 0, so stop the algorithm end if end for if i = A.length stop // Tried to improve until the end of the array, worst case i = 1 + 1 end while return [n1, n2]