Interview Question

Software Development Engineer In Test (SDET) Interview

-Mangalore

Microsoft

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

Answer

Interview Answers

3 Answers

0

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

ss11 on

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

0

there is a solution in O(n) time

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.