Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
2
of 4 vote

Merge sort :-
Merge is constant space
as well as finding mid is constant space...

- krb December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But merge sort needs extra memory

- Rocky December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

merging 2 sorted linkedlist needs constant extra memory

- krb December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Chris, linked lists are a structure unlike arrays that they do not need any extra space for merging. linked lists can be merged with O(1) space.

- famee December 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@All.. but still it need some node to store the data.. I guess no extra space rules out the possibility of using any extra space .. Specially for Data Storage .. including O(1) space..

- hprem991 December 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oftentimes, no extra space is taken to mean "only O(1) extra space"

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

simple bubble sort.

public void sortLL(LinkedList head){
		LinkedList p = head;
		if(head==null)
			return;
		
	
		else{
			
			while(p.next!=null){
				LinkedList q = head;
				while(q.next!=null){
					
					
					if(p!=q){
						if(p.value<q.value){
							int temp = p.value;
							p.value=q.value;
							q.value=temp;
						}
					}
					q=q.next;
				}
				
				p=p.next;
			}
		}
		
	}

- suvrokroy December 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bubble sort is O(n^2) compared to MergeSort O(nlgn). Both use constant space because of linked list structure.

- famee December 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

We can write insertion sort algorithm very easily for linked lists.
Algorithm:
While(index of unsorted linklist is not at an element pointing null- the last element)
{
1. Search for the biggest element one, after the other element
2. After the biggest element is found, remove it from the list and append it to the beginning of the list.
}
The complexity is O(n) like the implementation with arrays. The deletion of element in the list and insertion takes linear time.

- Lyubomir December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

need to loop for n nodes O(n), and for finding biggest again O(n)
total O(n^2), can't we do better than this?

- Andi December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do it with quicksort. There in the partition subroutine we know which elements in the linked list we have to swap, because we have them when traversing from the beginning to the pivot element and from the end to the pivot element. This will be O(n logn) time without additional memory usage.

- Lyubomir December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can not traverse backwards... because it is single linked list... ok can we make id double linked list with one traversal? - I guess it will not increase the overall complexity?
10x

- Lyubomir December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone give me the working code ? java is preferred, even pseudo would do.
I just need some help in implementation logic.

- Fresh_man December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

link

stackoverflow.com/questions/9368076/quick-sort-on-a-linked-list-with-a-random-pivot-in-c

- WarriorOfLight December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Both MergeSort and QuickSort will use space from the stack with each recursive call. If what the interviewer means with O(1) space is just keeping the original linked list and modifying than it shouldn't be a problem.

- Rayden December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I dont understand the term extra memory - if they mean don't allocate any extra linklist item on the heap - then this is a Simple insertion sort in C++ I just wrote
(just uses few temp pointers)

.Heap sort also won't use extra allocation of the LL object as you can simply heapify using comparator value.

Quicksort will bloat the stack but give good performance

struct ListNode
{
	int data;
    ListNode* next;
};

ListNode* getSortedLinkList(ListNode* head)
{
	ListNode *tempHead = head;
    
    if(!head) return NULL;
    
    head = NULL;
    
    do
    {
        ListNode* largest = tempHead;

        for (ListNode *temp2 = tempHead->next; temp2;
             					temp2 = temp2->next) {
            if(temp2->data > largest->data)
            {
            	//mark as largest
                largest = temp2;
            }
            // this prev helps avoid rescan
        }
        
        // remove largest from list and insert into new list (unless its alread up)
        if(largest != tempHead) 
        {
            // we are guaranteed to have at least 2 members in list here
            ListNode *temp3 = tempHead;
            while (temp3->next != largest) {
                temp3 = temp3->next;
            }
            // temp3 now points to previous of largest
            temp3->next = largest->next; // remove largest
        }
        else
        {
        	tempHead = tempHead->next;
        }
        largest->next = head;
        head = largest;
    
    } while (tempHead);
    
    return  head;
}

ListNode* getPopulatedList()
{
    int indata[8] = {23, 55, 11, 5, 14, 3, 78, 43};
    ListNode *head = new ListNode;
    ListNode *temp = head;
    
    for( int i = 0; i < 8; i++)
    {
        temp->data = indata[i];
    	temp->next =  new ListNode;
        temp = temp->next;
    }
    temp->next = NULL;
    
    return head;
}

int main(int argc, const char * argv[])
{
    ListNode* head = getPopulatedList(); // fill up some data
    for (ListNode *temp3 = head; temp3 != NULL; temp3 = temp3->next) {
        cout << "presort node data - " << temp3->data <<endl;
    }
    head = getSortedLinkList(head);
     for (ListNode *temp3 = head; temp3!= NULL; temp3 = temp3->next) {
         cout << "node data - " << temp3->data <<endl;
     }
    return 0;
}

- Aztec warrior December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

merge sort. with linked list, the merge can be done with const space complexity

List* mergeLists (List* L1, List* L2) {
	if (L1 && L2) {
		List* list = (L1->val < L2->val) ? L1 : L2;
		if (list == L1) L1 = L1->next;
		else L2 = L2->next;
		while (L1 && L2) {
			if (L1->val < L2->val) {
				list->next = L1;
				L1 = L1->next;
			}
			else {
				list->next = L2;
				L2 = L2->next;			
			}
			list = list->next;
		}
		if (L1) list = L1;
		else list = L2;
		return list;
	}
	if (L1) return L1;
	return L2;
}

- Daru December 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Radix Sort

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

I think radix sort will not be possible with a no extra space. We need an auxiliary table for storing nodes after each pass in radix sort.

- Subodh February 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

similar to "sort using two stacks" problem from "cracking..." book. treat the linked list as stack, and add another stack (linked list) to keep sorted results.

- lngbrc May 22, 2015 | 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