CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person



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

ListNode *curr,*second = NULL;

curr = head;

while(curr!=NULL && curr->next!=NULL)
{
	temp = curr->next;

	curr->next = temp->next;

	temp->next = second;

	second = temp;

	prev = curr;

	curr = curr->next;
}

prev->next = second;

Didnt include corner cases where the list is empty or has only one element....

- Jayanth February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I wanted to know since we are changing the value of current. Will the value of head also change?

- Chaitanya October 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Possible solution: Parse the list and push alternate nodes on the stack. Then pop and add at the end.

- Victor February 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Victor: Code in c to support your statement

#include <stdio.h>

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

typedef struct node_ node;
node *head = NULL;

int add(node **head,int no)
{
        node *temp,*head_ref;
        head_ref = *head;
        temp = malloc(sizeof(struct node_));
        temp->data = no;
        temp->next = NULL;
        if(*head == NULL){
                *head = temp;
        } else {
                while(head_ref->next != NULL)
                {
                        head_ref = head_ref->next;
                }
                head_ref->next = temp;
        }
        return 0;
}

void print(node *head)
{
        while(head != NULL)
        {
                printf("node no %d \n",head->data);
                head = head->next;
        }
}
void add_alt_nodes(node *temp, node **list)
{
        if(temp == NULL)
                return;
        add(list, temp->data);
}

void add_alt_data(int data, node **list)
{
        add(list, data);
}

void push(node **list, int data)
{
        node *temp = *list;
        node *t = malloc(sizeof(*t));
        t->data = data;
        t->next = NULL;
        if(temp == NULL) {
                *list = t;
        } else {
                /* find the top most element */
                t->next = *list;
                *list = t;
        }
}

int pop(node **list)
{
        int data;
        if(!*list)
                return -1;
        data = (*list)->data;
        (*list) = (*list)->next;
        return data;
}
int main()
{
        int i = 0;int found;int data=0;
        node *temp;
        node *s_list=NULL;
        node *s_list_1=NULL;
        for(i=0;i<20;i++)
                add(&head, i);
        for(temp=head;temp && temp->next;temp=temp->next->next) {
                add_alt_nodes(temp, &s_list);
        }
        add_alt_nodes(temp, &s_list);
        for(temp=head->next;temp && temp->next;temp=temp->next->next) {
                push(&s_list_1, temp->data);
        }
        if(temp)
                push(&s_list_1, temp->data);
        while(1) {
                data = pop(&s_list_1);
                if(data == -1)
                        break;
                add_alt_data(data, &s_list);
        }
        print(s_list);
        return 0;
}

- aka February 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks for the question. This was surprisingly tricky to get right...I made mistakes. I think part of the reason was that I underestimated the question :-(
The foll code works for 1, 1-901, 1-901-2, 1-901-2-902.

if (head->next) {
		second_head = head->next;
	} else {
		printf("Only one element in list.\n");
		return 1;
	}

	if (second_head->next == NULL) {
		printf("Only two elements in the list.\n");
		return 2;
	}

	tail = head;
	second_tail = second_head;
	while(tail->next && second_tail && second_tail->next) {
		tail->next  = tail->next->next;
		second_tail->next = second_tail->next->next;

		tail = tail->next;
		second_tail = second_tail->next;
	}
	
	// attach the first and second lists togther.
	tail->next = second_head;

	print_list(head);

- smallchallenges February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This might do it:

ListNode* reverseList(ListNode* head)
{
    if(head == NULL || head->next == NULL) return head;

    ListNode *pre = NULL, *nex;
    for(; head != NULL; pre = head, head = nex){
        nex = head->next;
        head->next = pre;
    }

    return pre;
}
ListNode* reverseAlternateAppendToTail(ListNode* head)
{
    if(head == NULL || head->next) return head;

    //break into two lists
    ListNode *list1 = head, *list2 = head->next, *p1 = list1, *p2 = list2, *p = list2->next;
    bool first = true;
    for(; p != NULL; p = p->next, first = !first){
        if(first){
            p1->next = p;
            p1 = p1->next;
        }
        else{
            p2->next = p;
            p2 = p2->next;
        }
    }
    
    //reverse list2 and append it to list1's tail
    p2->next = NULL;
    p1->next = reverseList(list2);
    
    return list1;
}

- uuuouou February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void ReverseAltNodes(struct Node *&node)
{
if(!node || !node->next)
return;
struct Node *last=node;
while(last->next)
last=last->next;
struct Node *t=node;
while(t && t!=last && t->next!=last)
{
struct Node *next=t->next;
if(!next){
break;
}
t->next=next->next;
struct Node *s=last->next;
last->next=next;
next->next=s;
t=t->next;
}
}

- Anonymous February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void getList(LinkedList head){
		if(head == null)
			return;
		int i=1;
		Stack S = new Stack();
		while(head != null){
			int d = head.getData();
			if(i%2==0)
				S.push(d);
			else
				System.out.print(" "+d);
			head = head.getNext();
			i++;
		}
		while(!S.isEmpty()){
			System.out.print(" "+S.pop());
		}
	}

- niraj.nijju February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void getList(LinkedList head){
		if(head == null)
			return;
		int i=1;
		Stack S = new Stack();
		while(head != null){
			int d = head.getData();
			if(i%2==0)
				S.push(d);
			else
				System.out.print(" "+d);
			head = head.getNext();
			i++;
		}
		while(!S.isEmpty()){
			System.out.print(" "+S.pop());
		}
	}

- niraj.nijju February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A recursive solution.

Node reverse(Node head, Node tail) {
    if(head == null)
      return tail;
    if(head.next == null) {
      head.next = tail;
    } else {
      Node next = head.next;
      Node nextNext = head.next.next;
      head.next = nextNext;
      next.next = tail;
      head.next = reverse(nextNext, next);
    }
    return head;
  }

- Sunny February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Node {
   Node(char d) : data(d), next(0) {}
   char  data;
   Node* next;
};

inline void ADD(Node*& t, Node* n)
{
    n->next = 0; t->next = n; t = n;
}

int main(int argc, char** argv)
{
    Node* head = new Node('a');
    Node* tail = head;

    ADD(tail, new Node('x'));
    ADD(tail, new Node('b'));
    ADD(tail, new Node('y'));
    ADD(tail, new Node('c'));
    ADD(tail, new Node('z'));

    for (Node* p = head; p->next != tail; p = p->next) {
        Node* t = p->next;
        p->next = t->next;
        t->next = tail->next;
        tail->next = t;
    }

    for (Node* n = head; n; n = n->next) cout << n->data; cout << endl;
    cout << endl;
}

- Westlake February 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static Node reverseAlternateElement(Node start) {
		if(start==null || start.next==null)
			return start;
		Node startCopy=start;
		Node second= start.next;
		Node secondCopy=second;
		while(second!=null && second.next!=null){
			start.next=second.next;
			start=start.next;
			second.next=start.next;
			second=second.next;
		}
		start.next=secondCopy;
		return startCopy;
		
	}

- Manu February 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node f(node x)
{
	a_head = x
	b_head = x.next
	a=a_head, b = b_head;
	
	while((a!=null) && (b != null))
	{
		a.next = b.next
		a = a.next
		b.next = a.next
		b = b.next
	}
	a.next = b_head
	return a_head;
}

- anon123 February 11, 2014 | 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