Microsoft Amazon Interview Question for Software Engineer / Developers Software Engineer in Tests






Comment hidden because of low score. Click to expand.
14
of 14 vote

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).

H = 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]

- emerson.loureiro February 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

if we follow sorting approach.... then i guess we can go for radix sort.

- kim October 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose A={10, 7, 5, 2, 9, 15}, then B={3, 2, 3, -7, -6} and the largest contiguous sum should be 8. What should I do from that point on then?

- Sunny December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- blueskin.neo February 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- S February 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- Anonymous February 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rakesh February 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry this will not work

- Rakesh February 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Blueskin February 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isn't this solution looks analogous to bucket sort, where instead of buckets you are using bitsets.

- sigkill July 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Tulley February 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

look at the example case! 20-19=1

- Anonymous March 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

bt count sort can be done only if we have a specified range..here no range is given

- kap October 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

If the original array is a[0...n-1],build a new array b[0...n-2],b[i]=b[i]-b[i+1]
so the problem now is find the largest continuous sum of b, that's pretty easy now

- zhao April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

even two smallest numbers can have a minimum difference

- Anonymous February 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@KK & @ Anonymous: here's an example where both of your algos fail
1, 5, 6, 8, 13, 20

- non anonymous February 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- anonymous February 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anonymous February 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

....

- absolutely WRONG ! February 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Divya February 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So what is the input is 5, 13, 7, 0, 10, 20, 1000. Are you going to hav an array of 1000 numbers and make them all 0. Space is not a constraint but the max allowed is 3 times the number of inputs.

- J February 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- SGK February 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

do they allow sorting?

- Anonymous March 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't we just do a radix sort to get O(N) time complexity. The given additional space allows that.

- Guess Who?? February 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't we just do a radix sort to get O(N) time complexity. The given additional space allows that.

- Guess Who?? February 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- yangjian0219 March 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why just lower level?

Consider following heap:

5
          9               10
     20    14    16       27

The answer should be 1, (9, 10)

- Anonymous March 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The heap will not be formed like this.
It will be formed some thing like :
5
9
10
14 20
16 27

if we consider the example given in the question :
5, 13, 7, 0, 10, 20, 1, 15, 4, 19
The heap formed will be
5
0 13
1 7 20
4 10 15
19

- Jumbo November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ..

- Abhishek July 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't work 1 3 20 21 98 100

- Anonymous August 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- pennymax September 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- xzy0410 October 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think Difference in this problem is defined as abs(A[i] - A[j]).
Hence your algorithm will not work in the case.

- Swap October 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

xyz's approach makes sense if we don't consider non-negative values.Unless the interviewer has asked for abs difference why would you not want to pitch min - max as the min difference?

- pseudo_coder. October 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

let
min1=a[0]<a[1]?a[0]:a[1];
min2=a[0]+a[1]-min1;

for(int i=2;i<n;i++)
{
if(a[i]< min1)
{
min2=min1;
min1=a[i];
}
else if(a[i]< min2)
{
min2=a[i];
}
}

return abs(min1-min2);

complexity: O(n)

- mrn October 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

The difference between the smallest element and the largest element will be minimum.

- tp November 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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??

- krish April 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- gocool January 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

}

- Ritesh Gupta September 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- KK February 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about {1, 2, 5, 8}

- Anonymous February 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Anonymous February 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how will your algo work for this input 5,2,4,6,1,3,2,6

- CCJ February 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

i think sorting should be done. so if space doent matters we can do it with the helpof counting sort
1.first sort the numbers using counting sort.
2. traverse the array and compare neighbous only and maintain the min value always.
complexity O(n)
any other approach??

- geeks October 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- coolsubbu October 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- pseudo_coder. October 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How does bitmap sorting handle duplicate numbers ??

- Thinker October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- prkhr October 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about 19 and 18?

- Yuting October 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

How about we find the n-1 and nth largest element in the set (using k'th largest algorithm) and take the difference?
Just a thought.

- Anonymous October 13, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More