Amazon Interview Question for Software Engineer / Developers






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

1. Without extra space time: O(N^2)
2. With O(N) space time: O(N)

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

This information doesn't give any insight of your solution. If you don't have time to give a "hint" to the job seeker, why the hell you need to give some ad-hoc solution at first place.

If you dare to challenge, post your complete code. Others will catch bug in that.

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

int min=MAX_INT;
hash_map<int,int> hm;
while(a&&b)
{
if(abs(a->data-b->data)<min)
{
min=abs(a->data-b->data);
hm.clear();
}
if(abs(a->data-b->data)<=min)
{
hm.Insert(pair<int,int>(a->data,b->data));
}
if(a->data>b->data) b=b->next;
else a=a->next;
}

- anonymous2 April 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First sort the array.
Then store the difference between the first two as min.
then go on by comparing the difference between the next two element if it is less than min consider that as the min.

Now problem comes when the array has both the Negative and positive numbers.we can follow the above method if the array contains only positive or only negative.

suppose if one element is positive in one array and the corresponding element in other array is negative then get the difference Binary search for that difference+positive num. modify the binary search such that it return the next small no index if a current is not found. From that position you have track. and see whether you are getting the minimum element.

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

This problem doesn't have any negative value..

- krithick.krishnagiri April 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

First sort both the linked lists
Set pointer x1 to 1st sorted linked list and x2 to 2nd sorted linked list.
1) Initialize min to distance between the values pointed by x1 and x2.
2) if value pointed by x1 is less than the value pointed by x2 then move x1 to next element otherwise move x2 to next element.
3) Then take distance between the elements pointed by x1 and x2 and update min if necessary.
4) repeat steps 2 and 3.

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

Good Solution Kiran .. It works .. It has O(nlogn) time complexity .. the time taken to sort the biggest of two arrays..

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

If input arrays are not sorted by default sort them using some in-place algo.

a) have two integer(index1, index2) pointing to position on two array and currentBestIndex1, currentBestIndex2
b) i)assume array2 will lead the way, loop through array until MIN(sizeof(array1), sizeof(array2))
ii) increase index1, index2 according to local best difference and update currentBestIndex1, currentBestIndex2 if index1, index2 values are smaller
iii) once we reach the end of one of the array we are done

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

Time/Space
Assume Array1 is N, Array2 is M and also array1 is smaller than array2
Time=O(N) if already sorted
=O(nlogn + mlogm)
Space O(1)

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

Looks like your solution is O(NM). Can you explain more on the time complexities part.

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

int main()
{
	int array2[] = {8, 14, 27, 29};
	int array1[] = {2, 3, 5, 10, 12, 16, 19, 20}
	int array1Size = sizeof(array1)/sizeof(int);
	int array2Size = sizeof(array2)/sizeof(int);
	int index1,index2 = 0;
	int lowestIndex1, lowestIndex2 = 0;//local minimum found so far
	for(int i = 1; i < array1Size && i < array2Size; i++)
	{

		if(abs (array1[index1] - array2[index2]) > abs (array1[(index1+1)] - array2[index2]))
		{
			if((index1+1) < array1Size)
				index1++;
		}
		else if(abs (array1[index1] - array2[index2]) > abs (array1[index1] - array2[(index2+1)]))
		{
			if((index2+1) < array2Size)
				index2++;
		}
		else if(abs (array1[index1] - array2[index2]) > abs(array1[index1+1] - array2[index2+1]))
		{
			if((index1+1) < array1Size)
				index1++;
			if((index2+1) < array2Size)
				index2++;
		}

		//overwrite current lowest if index1,2 is lower
		if(abs(array1[lowestIndex1] - array2[lowestIndex2]) > abs(array1[index1] - array2[index2]))
		{
			lowestIndex1 = index1;
			lowestIndex2 = index2;
		}
	}

	printf("index1 = %d, index2 = %d\n", index1, index2);
}

The loop will run until the end of the maximum sized array so O(n)/space(1) if arrays are already sorted

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

small correction to the main loop condition it should be || not &&

- Mat April 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Considerering the size to be M and N.. it can easily be done in O(max(lg(max(M, N)), min(M, N)))

So, if M > N it can be done in
O( max(Lg(M), N) )-time

- Siddharth April 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if we deal with 3 characters as opposed to 2 characters in the original problem? Can somebody tell me what would be the time & space complexity?

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

assuming all positions are positives. I will bucketize the 2 lists by 10, for eg. {1-10},{11-20}... then only compare the elements in the same buckets.

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

sort the lists (if not sorted before)
merge the two lists and keep track of the minimum difference

- camSun April 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes I was thinking exactly the same. Plus from the example it seems they are already sorted..so using the merge operation of merge sort, this can be done in O(N) time

- megatron April 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assume that arrays are sorted. Otherwise sort the arrays first

namespace MinDistanceBetweenWordsIn2Docs
{
    class Program
    {
        //use binary search in second array
        static void Main(string[] args)
        {
            int[] ar1 = { 2, 3, 5, 10, 12, 16, 19, 20 };
            int[] ar2 = { 8, 13, 27, 29 };
            Console.WriteLine(MinimumDistance(ar1,ar2));
            Console.Read();
        }
        public static int MinimumDistance(int[] arr1, int[] arr2)
        {
            int min = int.MaxValue;
            for (int i = 0; i < arr1.Length; ++i)
            {
                int left = 0, right = arr2.Length - 1;
               
                while (left <= right)
                {
                    int mid = (left + right) / 2;
                    if (Math.Abs(arr1[i] - arr2[mid])<min)
                    {
                        min = Math.Abs(arr1[i] - arr2[mid]);
                    }
                    if (mid > left && Math.Abs(arr1[i] - arr2[mid - 1]) < min)
                    {
                        min = Math.Abs(arr1[i] - arr2[mid - 1]);
                        right = mid - 1;
                    }
                    else if (mid < right && Math.Abs(arr1[i] - arr2[mid + 1]) < min)
                    {
                        min = Math.Abs(arr1[i] - arr2[mid + 1]);
                        left = mid + 1;
                    }
                        //mid element distance is the least
                    else break;
                }
            }

            return min;
        }
    }
}

- BVarghese October 20, 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