Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
@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.
@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..
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;
}
}
}
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.
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.
Can someone give me the working code ? java is preferred, even pseudo would do.
I just need some help in implementation logic.
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;
}
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;
}
Merge sort :-
- krb December 08, 2012Merge is constant space
as well as finding mid is constant space...