Article Amazon Interview Questions

Amazon was founded in 1994, spurred by what Bezos called "regret minimization framework", his effort to fend off regret for not staking a claim in the Internet gold rush.While company lore says Bezos wrote the business plan while he and his wife drove from New York to Seattle,that account appears to be apocryphal. The company began as an online bookstore; while the largest brick-and-mortar bookstores and mail-order catalogs for books might offer 200,000 titles, an on-line bookstore could offer more. Bezos named the company "Amazon" after the world's biggest river. Since 2000, Amazon's logotype is an arrow leading from A to Z, representing customer satisfaction (as it forms a smile) and the goal to have every product in the alphabet.

1. Given 2 linked lists(which need not have unique elements) find intersection point in the form of Y.(it can be anywhere--middle or tail)
Solution:

• Calculate the length of the 2 linked-lists - L1 & L2
• int diff = abs(L1-L2);
• Move the head pointer of the larger length list by diff positions.
• Keep moving each of the head pointer by 1 step, the point at which they meet is the point at which the linked-lists intersect.

node *h1,*h2; /* Calculates the length of the linked-list given the head pointer */ int l1 = length ( h1 ),l2 = height ( h2 ); int diff = abs( l1 - l2 ); if ( l1 > l2 ) { while( diff ) {h1 = h1->next;diff--;} } else { while( diff ) {h2 = h2->next;diff--;} } while( h1->next != h2->next ) {h1 = h1->next; h2 = h2->next; }
2. Given an array, find out if there exists a pair of nos. that adds up to a sum 'x'
Solution:

• Sort the array; Complexity = O(nlgn)
• Have 2 pointers, p1 & p2; p1 - points to the 1st element in the array and p2 points to the last element in the array.
• Sum up a[p1] and a[pn]; s = a[p1] + a[pn] if( s > x ) { pn--; } else if ( s < x ) {p1++;}
• Repeat the above till you encounter the sum = x, else there are no pairs in the array that sum to 'x'

Since the array is sorted, the above technique works int p1 = 0, p2 = n-1; int sum = a[p1] + a[p2]; while ( sum !=x && (p1 < p2) ){ if( sum > x ) p2--; else p1++; }