Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Subbu - I don't get how the element distinctness problem helps solve this question , can you elaborate? Thanks.
@Jason: there is no O(n) solution for this as subbu mentioned by referring you to 'element distinctness problem'.This problem is just to prove the point that there can't be O(n) solution possible for this problem.
O(nlgn) solution:
public static List<Pair> getMinDiff(int[] A)
{
ArrayList<Pair> pairs;
int minDiff = Integer.MAX;
A=quicksort(A);
for(int i=0;i<A.length-1;i++)
{
if (abs(A[i+1]-A[i]) < minDiff)
{
pairs = new ArrayList<Pair>();
pairs.add(new Pair(A[i], A[i+1]));
minDiff = abs(A[i+1]-A[i]) ;
}
else if (abs(A[i+1]-A[i]) == minDiff)
{
pairs.add(new Pair(A[i], A[i+1]));
}
}
return pairs;
}
O(nlgn) with O(1) space solution
1. Sort the array.
2. Scan the sorted array from left to right. keep minDiff to contain the min difference between two elements during the scan.
3. If diff between two consecutive is less than minDiff so far then create a list and add the pair.
4. if diff between two consecutive is equal to minDiff that means there is already a list. Add the pair to the list.
public static List<Pair> getMinDiff(int[] A)
{
ArrayList<Pair> pairs;
int minDiff = Integer.MAX;
A=quicksort(A);
for(int i=0;i<A.length-1;i++)
{
if (abs(A[i+1]-A[i]) < minDiff)
{
pairs = new ArrayList<Pair>();
pairs.add(new Pair(A[i], A[i+1]));
minDiff = abs(A[i+1]-A[i]) ;
}
else if (abs(A[i+1]-A[i]) == minDiff)
{
pairs.add(new Pair(A[i], A[i+1]));
}
}
return pairs;
}
Using this method we can find the absolute minimum difference:
Assume numbers are array a[ ].
for(int i=1;i<(sizeof(a)/sizeof(int));i++)
{
min=a[1]-a[0];
max=a[0];
if((a[i]-min)<min)
{
min=a[i]-max;
start=a[i];
end=max;
}
if(a[i]>max)
max=a[i];
}
after finding absolute min we can get the elements using start and end.
but since we need to find all. After getting the absolute minimum we will traverse the liist and find out two numbers having difference equal to absolute min.
1> Convert all numbers as positive integers.
2> Sort them. complexity O(n log n) Average/best time
3> Traverse once to find the closest two adjacent numbers. O(n)
Overall complexity O(n log n)
Solution written in C++. Time complexity O(nlogn).
Output:
-470 - -520 = 50
30 - -20 = 50
Code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
std::vector<std::pair<int, int>> find_min_abs_diff(std::vector<int>& arr) {
// Sort the vector O(nlogn)
std::sort(arr.begin(), arr.end());
// Find the difference between every adjacent elements. O(n)
// Keep track of minimum
int min_so_far = std::numeric_limits<int>::max();
std::vector<std::pair<int, int>> pairs;
for (size_t i = 1; i < arr.size(); i++) {
int diff = std::abs(arr[i] - arr[i-1]);
if (diff <= min_so_far) {
min_so_far = diff;
pairs.emplace_back(arr[i], arr[i-1]);
}
}
// Remove elements that are greater than the minimum found.
pairs.erase(std::remove_if(pairs.begin(), pairs.end(),
[&](const std::pair<int, int>& p) {
return p.first - p.second > min_so_far;
}), pairs.end());
return pairs;
}
int main() {
std::vector<int> arr{-20, -3916237, -357920, -3620601, 7374819, -7330761,
30, 6246457, -6461594, 266854, -520, -470};
std::vector<std::pair<int, int>> min_pairs = find_min_abs_diff(arr);
for (const auto& p: min_pairs) {
std::cout << p.first << " - " << p.second << " = ";
std::cout << p.first - p.second << std::endl;
}
}
In c#, maybe not the most elegant, but this should work:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace InterviewQuestions
{
struct pair
{
public int first;
public int second;
}
class Program
{
static void Main(string[] args)
{
int[] arr = { -20, -3916237, -357920, -3620601, 7374819, -7330761, 30, 6246457, -6461594, 266854, -520, -470 };
int nSmallest = Int32.MaxValue;
List<pair> results = new List<pair>();
for (int i = 0; i < arr.Length; i++)
{
for (int j = i+1; j < arr.Length; j++)
{
if (Math.Abs(arr[i] - arr[j]) < nSmallest)
{
results.Clear();
pair p;
p.first = arr[i];
p.second = arr[j];
results.Add(p);
nSmallest = Math.Abs(arr[i] - arr[j]);
}
else if (Math.Abs(arr[i] - arr[j]) == nSmallest)
{
results.Add(new pair { first = arr[i], second = arr[j] });
}
}
}
foreach (pair r in results)
Console.WriteLine("({0},{1})",r.first,r.second);
Console.ReadLine();
}
}
}
here my solution in O(n log n) time.
@Diego: i think this might be faster than your algo...since i dont call vector.erase...which allocates the vector new?
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct mypair {
int x;
int y;
mypair(int x_, int y_): x(x_), y(y_) {}
}mypair;
vector<mypair> get_numbers_min_diff(vector<int> &vec) {
map<int,vector<mypair>> m;
// O(n log n)
sort(vec.begin(), vec.end());
// O(n log n)
for(int i = 0; i < vec.size() - 1; i++) {
int diff = vec[i+1] - vec[i];
auto it = m.find(diff);
if(it == m.end()) {
vector<mypair> v;
v.push_back(mypair(vec[i], vec[i+1]));
m.insert(make_pair(diff, v));
}
else {
it->second.push_back(mypair(vec[i], vec[i+1]));
}
}
auto it = m.begin()->second;
return it;
}
int main() {
vector<int> vec = {-20, -3916237, -357920, -3620601, 7374819, -7330761, 30, 6246457, -6461594, 266854, -520, -470};
vector<mypair> sp = get_numbers_min_diff(vec);
for_each(sp.begin(), sp.end(), [](mypair p) { cout << p.x << ", " << p.y << endl; });
return 0;
}
#include<stdio.h>
#include<math.h>
#define MAX 100
int main()
{
int arr[12]={-20,-3916237,-357920,-3620601,7374819,-7330761,30,6246457,-6461594,266854,-520,-470};
int i,j,temp,c[11],min;
/* Sort the array*/
for (i= 0;i<11;i++)
{
for (j=0;j<(12-i-1);j++)
{
if (arr[j]>arr[j+1])
{
temp =arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}}}
for(i=0;i<11;i++)
{
c[i]=abs(arr[i]-arr[i+1]);
}
min=c[i];
for(i=0;i<11;i++)
{
if(min>c[i])
min=c[i];
}
for(i=0;i<11;i++)
{
if(min==c[i])
printf("%d %d",arr[i],arr[i+1]);
}
return 0;
}
1.) Sort the list;
2.) Traverse the list twice: first to find the min difference and second to find all pairs with the min difference found
public String displaySmallestDifference(List<Integer> numbers) {
String smallestDifferences = "";
Collections.sort(numbers);
Integer smallestDifference = null;
Integer currentDifference = null;
for(int i = 0; i < numbers.size(); i++) {
if(i + 1 < numbers.size()) {
currentDifference = Math.abs(numbers.get(i+1) - numbers.get(i));
if(smallestDifference == null || currentDifference <= smallestDifference) {
smallestDifference = currentDifference;
}
}
}
for(int i = 0; i < numbers.size(); i++) {
if(i + 1 < numbers.size() &&
Math.abs(numbers.get(i + 1) - numbers.get(i)) == smallestDifference) {
smallestDifferences += " "+numbers.get(i)+" "+numbers.get(i + 1);
}
}
return smallestDifferences;
}
1)first sorting the list
- Jason November 30, 20132)traversing the list and return the min absolute pair.
the time complexity is O(nlogn).
I do not know if there is any solution in O(n) steps.