Microsoft Interview Question for Software Engineers

• 0

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)

# Append head1 and move its pointer forwards
curr = curr.next
break # If end of head then break

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

return dummy.next``````

Test code:

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

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

'''
Output:
1->10->2->20->3->30->4->
'''``````

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
break # If end of head then break

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

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

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);
}

}``````

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

``````Node l1;
Node l2;
Node node = new Node(0);
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;
}

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

``````public static ListNode interLeaveLL(ListNode l1, ListNode l2){
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;
}
}``````

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

``````public static ListNode interLeaveLL(ListNode l1, ListNode l2){
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;
}
}``````

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.

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.