Microsoft Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

Fairly straightforward problem. The only clarification we might need is if to include the second LL's element in the last interleaving (i.e whether to include 40) but going by your example, it doesn't seem to be the case. This solution is expressed in Python below.

Solution:

def interleaveLL(head1, head2):
  dummy = curr = Node(None)

  while head1 != None:
    # Append head1 and move its pointer forwards
    curr.next = head1
    curr = curr.next
    head1 = head1.next
    if head1 is None:
      break # If end of head then break

    # Append head2 and move its pointer forwards
    curr.next = head2
    curr = curr.next
    head2 = head2.next

  return dummy.next

Test code:

def printLL(head):
  curr = head
  while curr:
    print(curr.data, end='->')
    curr = curr.next
  print()

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None


head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)

head2 = Node(10)
head2.next = Node(20)
head2.next.next = Node(30)
head2.next.next.next = Node(40)
head2.next.next.next.next = Node(50)
head2.next.next.next.next.next = Node(60)

printLL(interleaveLL(head1, head2))
'''
Output:
1->10->2->20->3->30->4->
'''

- prudent_programmer March 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Prudent_Programmer. Your code won't support scenario when L2 length is less then L1 length.

As part of ''' "while head1 != None: " '''' ou should also include head2 != None and condition to break if
if head2 is None:
break # If end of head then break

- Andy March 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Andy. Excellent catch man! Thank you for pointing that out. :)

- prudent_programmer March 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MergeLists {
	
	Node root;
	Node root2;
	
	class Node{
		int data;
		private Node next;
		
		public Node(int data) {
			this.data=data;
			
		}
	}
	
	public void buildFirstList() {
		
		root=new Node(1);
		
		Node n1=new Node(2);
		root.next=n1;
		Node n2=new Node(3);
		n1.next=n2;
		Node n3=new Node(4);
		n2.next=n3;
		
		
		
		
		
	}
	
	public void buildSecondList() {
		root2=new Node(10);
		Node n1=new Node(20);
		root2.next=n1;
		Node n2=new Node(30);
		n1.next=n2;
		Node n3=new Node(40);
		n2.next=n3;
		
		
	}
	
	public void traverseAlt(Node n,Node n2) {
		n=root;
		n2=root2;
		while(n!=null && n2!=null) {
			System.out.println(n.data);
			System.out.println(n2.data);
			n=n.next;
			n2=n2.next;
		}
		
		if(n==null && n2!=null) {
			
			return;
			
	}
		
		else if(n2==null && n!=null){
			
			return;
			
		}
		

}
	
	public void traverse(Node n) {
		while(n!=null) {
			System.out.println(n.data);
			n=n.next;
		}
	}
	
	public static void main(String args[]) {
		MergeLists ml=new MergeLists();
		ml.buildFirstList();
		ml.buildSecondList();
		
		ml.traverseAlt(ml.root, ml.root2);
		//ml.traverse(ml.root2);
	}

}

- aifra2000 April 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node l1;
Node l2;
Node node = new Node(0);
Node head = node;
while(l1 != null && l2 != null)
{
	node.next = l1;
	l1 = l1.next;
	node = node.next;
	node.next = l2;
	l2 = l2.next;
	node = node.next;
}

if(l1 == null)
{
	node.next = l2;
}
else if(l2 == null)
{
	node.next = l1;
}
return head.next;

- Abhay Nagaraj April 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static ListNode interLeaveLL(ListNode l1, ListNode l2){
        ListNode head = new ListNode(0);
        ListNode tmp = head;
        boolean flag = true;

        while (l1 != null && l2 != null){
            if(flag){
                tmp.next = l1;
                tmp = tmp.next;
                l1 = l1.next;
            } else {
                tmp.next = l2;
                tmp = tmp.next;
                l2 = l2.next;
            }

            flag = !flag;
        }

        while (l1 != null){
            tmp.next = l1;
            tmp = tmp.next;
            l1 = l1.next;
        }
        return head.next;
    }

- Anonymous January 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static ListNode interLeaveLL(ListNode l1, ListNode l2){
        ListNode head = new ListNode(0);
        ListNode tmp = head;
        boolean flag = true;

        while (l1 != null && l2 != null){
            if(flag){
                tmp.next = l1;
                tmp = tmp.next;
                l1 = l1.next;
            } else {
                tmp.next = l2;
                tmp = tmp.next;
                l2 = l2.next;
            }

            flag = !flag;
        }

        while (l1 != null){
            tmp.next = l1;
            tmp = tmp.next;
            l1 = l1.next;
        }
        return head.next;
    }

- dpslackbot January 22, 2019 | 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