Microsoft Interview Question: given a linked list which has... | Glassdoor.co.in

Interview Question

Software Development Engineer In Test (SDET) Interview(Student Candidate) Mangalore

given a linked list which has two types of pointers, a

  normal next pointer which points to next element in the list and random pointer which points to random element in the list. Question was to clone this linked list
Tags:
technical, algorithm
Answer

Interview Answer

3 Answers

0

there is a solution in O(n) time

Interview Candidate on 26-Sep-2012
0

@ Interview Candidate: can you give some details about the logic ?

ss11 on 05-Oct-2012
0

import java.util.HashMap;

public class MSQuestion2 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        CustomLinkedList lst = new CustomLinkedList();
        lst.head=new Node1(1);
        lst.incrementsize();
        Node1 node2 = new Node1(2);
        lst.head.next=node2;
        Node1 node3 = new Node1(3);
        node2.next=node3;

        lst.printList(lst);
// lst.reverseList(lst);
        lst.printList(lst);
        CustomLinkedList clonelst= lst.clone(lst);
        lst.printList(clonelst);

    }

}

class Node1
{
    int data;
    Node1 next;
    Node1 random;

    public Node1(int data)
    {
        this.data=data;
        this.next=this.random=null;
    }
}

class CustomLinkedList
{
    Node1 head;
    static int size;

    public CustomLinkedList()
    {
        this.head=null;
        this.size=1;
    }

    public CustomLinkedList(Node1 head)
    {
        this.head=head;
        this.size=1;
    }

    public CustomLinkedList clone(CustomLinkedList lst) {
        // TODO Auto-generated method stub
        CustomLinkedList lst2 = new CustomLinkedList();
        HashMap map = new HashMap();
        Node1 n = lst.head;
        Node1 clonednode = null;
        while(n!=null)
        {
            clonednode = new Node1(n.data);
            map.put(n, clonednode);
            n=n.next;
        }
        n = lst.head;
        while(n!=null)
        {
          clonednode=map.get(n);
          clonednode.next=map.get(n.next);
          clonednode.random=map.get(n.random);
          n=n.next;
        }
        lst2.head=map.get(lst.head);

        return lst2;

    }

    public void printList(CustomLinkedList lst)
    {
          Node1 n = lst.head;
          while(n!=null)
          {
              System.out.println(n.data);
            n=n.next;
          }
    }

    public void reverseList(CustomLinkedList lst) {

        Node1 n=lst.head;
        Node1 prev =null;
        Node1 next = null;
        while(n!=null)
        {
          next=n.next;
          n.next=prev;
          prev=n;
          head=n;
          n=next;
        }
    }

    public void add(CustomLinkedList lst,int data)
    {
        Node1 node= new Node1(data);
        node.next=null;
        size++;
    }

    public void incrementsize()
    {
        this.size++;
    }

}

Siva on 26-Jun-2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.