Adobe Interview Question Software Engineer / Developers


Country: India
Interview Type: In-Person


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

traverse the circular list with 2 points "first and second"
increment first by 2 times and second once till you read the head pointer again.
after the first travelsal, first will be pointing to head of list and second will be at the mid point.
we will be left with setting the next pointers to null and returning 2 pointer (first and second)

//first points to start if the list
void circular_to_list(struct node *first, struct node *second)
{
    struct node *head, struct node *temp;
    head = first;
    second = head;
    first = head;
    do
    {
        first = first->next;
        if(first == temp)
            break;
        first = first->temp;
        second = second->next;
    }while(first != temp);

    //first is pointing to head of list
    //second is point to mid of the list
    temp = first;
    first = first->next;
    temp->next = NULL;
    temp = second;
    second = second->next;
    second->next = NULL;
}

- mtsingh on April 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

temp and head is not initialized in before first loop

Is temp = head = first ?

- Anon on April 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if list size is odd, then First will skip the head.

- gautamvermaroshan on April 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can start with head and assign first node to list1 and next node to list2 and so on... till all the node && node->next are not equal.
But,what if no. of nodes in list has odd value?

- ptripa on April 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the idea is to not use any additional data structures and do a split in place

- rdo on April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take two pointer of any node, let X. Increment one pointer by one and other by two. when 2nd pointer will again reach to the X then first one will be in the middle of list.Then we will have two list of equal length. First ones starting address will be X and other ones will be 1st pointer.And along with this we need to make lastNode->next=null for both the list.

- Gaurav on April 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess this doesn't work for linked lists with odd-number of elements, does it?.

- abc on May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is same as finding middle element in a link-list by single traversal . Take t1o pointer one runs single increment one 2*single increment. When reached to the middle point split them. Stop condition will not be NULL here but the head pointer.

- Anonymous on April 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use fast & slow pointer concept ....easy one from Adobe...

- joker on April 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use fast & slow pointer concept ....easy one from Adobe...

- joker on April 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution given will work for a circular single linked list that has even number of nodes, what if there are odd number of nodes as ptripa pointed out ?

- Anonymous on April 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A simple condition does the trick.

Solution in coming post.

- Anonymous on April 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.career.ds.linkedlist;

public class SplitCircularList {

    public static void main(String args[]) {
        CreateCircularList ll = new CreateCircularList();
        Node head = ll.createList(7, 1);
        ll.displayCircularList(head);
        Node secondHead =  ll.splitList(head);
        ll.displayCircularList(head);
        ll.displayCircularList(secondHead);
    }
}

class CreateCircularList {

    public Node createList(int length, int data) {
        Node head = new Node((data++));
        Node pointer = head;
        for (int i = 1; i < length; i++) {
            Node temp = new Node((data++));
            pointer.setNext(temp);
            pointer = temp;
        }
        pointer.setNext(head);
        return head;
    }

    public void displayCircularList(Node head) {
        Node temp = head;
        while (temp.getNext() != head) {
            System.out.print(temp.getData() + "->");
            temp = temp.getNext();
        }
        System.out.println(temp.getData() + "->");
    }
    
    public Node splitList(Node head) {
        Node tortoisePointer = head;
        Node harePointer = head.getNext();
        
        while(harePointer != head && harePointer.getNext() != head) {
            harePointer = harePointer.getNext().getNext();
            tortoisePointer = tortoisePointer.getNext();
        }
        Node secondHead = tortoisePointer.getNext();
        tortoisePointer.setNext(head);
        Node temp = secondHead;
        while(temp.getNext() != head) {
            temp = temp.getNext();
        }
        temp.setNext(secondHead);
        return secondHead;
    }
}

Odd
===

1->2->3->4->5->6->7->
1->2->3->4->
5->6->7->

Even
====

1->2->3->4->5->6->7->8->
1->2->3->4->
5->6->7->8->

- Anonymous on April 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

when will below condition be satisfied ???

while(harePointer != head && harePointer.getNext() != head) {

- suvro on May 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private void splitNode(LLNode head){
		
		
		LLNode temp = head;
		int count = 0;
		
		//count total nodes
		while(temp.next!=head){
			
			count++;
			temp = temp.next;
		}
		
		temp = head;
		
		int i=0;
		while(i!=count/2){
			
			temp=temp.next;
			i++;
			
		}
		//go to middle and ground the node also mark the next node as 
		//head of second LL
		LLNode newHead = temp.next;
		
		temp.next = null;
		
		temp = newHead;
		while(temp.next!=head){
			temp=temp.next;
		}
		//ground the last node of second list
		temp.next=null;
		
		
		
		
	}

- suvrokroy on May 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take 3 pointer from start ..
Increase 1st by 4 times,
Increase 2nd by 2 times,
Increase 3rd by 1 times,

When 1st and 2nd will be meeting for first time, 3rd pointer will on mid

- nagen547 on May 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take 3 pointer from start ..
Increase 1st by 4 times,
Increase 2nd by 2 times,
Increase 3rd by 1 times,

When 1st and 2nd will be meeting for first time, 3rd pointer will on mid

- nagen547 on May 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given a circular linked list with head pointer head.

Here is another approach....

1. Turn circular list into singly linked list by inserting a null pointer.

temp = head->next;
head->next = null;
head = temp;

Now we have a singly linked list with new head pointer.

2. Now use two pointers, first moves one step at a time while second moves two step at a time. When second reaches the end, first is at middle. Now we can break the list at the middle.

first = head;
second = head;
while(second!= NULL && second->next != NULL)
{
first = first->next;
second = second->next->next;
}

- JustMe on June 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BreakCircular( Linked *head)
{
Linked * ptr1 , *ptr2, head1;
ptr1 = ptr2 = Head;
int move =0;

while( Ptr2->next != Head)
{
ptr1 = ptr1->next;
i++;
if( i%2 == 0)
{
ptr1 = ptr1->next;
}
}
head1 = ptr1->next;
ptr1->next = NULL;
ptr2->next = NULL;
}
}

- himanshu kumar chauhan on September 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you assuming that this is Double linked list?

- mtsingh on April 25, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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