Arista Networks Interview Question
Software EngineersCountry: India
Interview Type: Written Test
Here is my solution
class ListNode<T extends Comparable<T>> {
private T val;
private ListNode<T> next;
ListNode (T v) {
val = v;
}
}
ListNode<Integer> merge (ListNode<Integer> n1, ListNode<Integer> n2) {
if (n1 == null)
return n2;
if (n2 == null)
return n1;
if (n1.val.compareTo(n2.val)<0) {
n1.next = merge (n1.next, n2);
return n1;
}
else {
n2.next = merge (n1, n2.next);
return n2;
}
}
}
In C:
Assume LL1 and LL2 are the pointers to the two sorted linked list(typedef struct node).
Then the code snippet would look like this:
struct node* build_l1, build_l2, build_l3, ll3; //initialize to null
while(!LL1 && !LL2)
{
build_l1 = LL1;
build_l2 = LL2;
if(LL1->data < LL2_data)
{
if(!build_l3)
{
LL3 = build_l3 = build_l1;
}
else
{
build_l3->next = build_l1;
}
build_l1->next = build_l2;
LL1 = LL1->next;
LL2 = LL2->next;
build_l3 = build_l3->next;
}
else if(LL1->data >= LL2_data)
{
if(!build_l3)
{
LL3 = build_l3 = build_l2;
}
else
{
build_l3->next = build_l2;
}
build_l2->next = build_l1;
LL1 = LL1->next;
LL2 = LL2->next;
build_l3 = build_l3->next;
}
}
if(!LL1)
{
build_l3->next = LL2;
}
else if(!LL2)
{
build_l3->next = LL1;
}
return LL3;
In C:
Assume LL1 and LL2 are the pointers to the two sorted linked list(typedef struct node).
Then the code snippet would look like this:
struct node* build_l1, build_l2, build_l3, ll3; //initialize to null
while(!LL1 && !LL2)
{
build_l1 = LL1;
build_l2 = LL2;
if(LL1->data < LL2_data)
{
if(!build_l3)
{
LL3 = build_l3 = build_l1;
}
else
{
build_l3->next = build_l1;
}
build_l1->next = build_l2;
LL1 = LL1->next;
LL2 = LL2->next;
build_l3 = build_l3->next;
}
else if(LL1->data >= LL2_data)
{
if(!build_l3)
{
LL3 = build_l3 = build_l2;
}
else
{
build_l3->next = build_l2;
}
build_l2->next = build_l1;
LL1 = LL1->next;
LL2 = LL2->next;
build_l3 = build_l3->next;
}
}
if(!LL1)
{
build_l3->next = LL2;
}
else if(!LL2)
{
build_l3->next = LL1;
}
return LL3;
Here is code:-
public Node<V> merge(Node<V> list1, Node<V> list2) {
Node<V> temp = list1;
int index = 0;
while (list1 != null && list2 != null) {
if (compare(list1, list2) >= 0) {
Node<V> node = new Node<>();
node.setValue(list2.value);
if (index == 0) {
node.next = list1;
list1= node;
temp = list1;
list1 = list1.next;
} else {
temp.next = node;
node.next = list1;
list1 = node;
index = 0;
}
list2 = list2.next;
} else{
list1 = list1.next;
}
if (index > 0) {
temp = temp.next;
}
index++;
}
if(list2 != null){
temp.next = list2;
}
return list1;
}
@SuppressWarnings({ "rawtypes", "unchecked" })
private int compare(Node<V> node1, Node<V> node2) {
Comparable<V> comparable = (Comparable) node1.value;
return comparable.compareTo(node2.value);
}
private static class Node<V> {
private V value;
private Node<V> next;
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
public static Node MergeSortedLists(Node first, Node second)
{
if (first == null && second == null)
{
return null;
}
if (first == null && second != null)
{
return second;
}
if (first != null && second == null)
{
return first;
}
Node head;
//if value of first node of left side linked list is greater than first node of second side linked list then swap them
//as we need node with smallest value as first node of left linked list
if (first.nodeContent < second.nodeContent)
{
head = first;
}
else
{
var n = second.next;
second.next = first;
head = second;
second = n;
}
while (first.next != null && second != null)
{
if (first.next.nodeContent < second.nodeContent)
{
first = first.next;
}
else
{
var t = first.next;
var n = second.next;
first.next = second;
second.next = t;
first = first.next;
second = n;
}
}
//check if second list still has elements
if (second != null)
{
first.next = second;
}
return head;
}
public static Node MergeSortedLists(Node first, Node second)
{
if (first == null && second == null)
{
return null;
}
if (first == null && second != null)
{
return second;
}
if (first != null && second == null)
{
return first;
}
Node head;
//if value of first node of left side linked list is greater than first node of second side linked list then swap them
//as we need node with smallest value as first node of left linked list
if (first.nodeContent < second.nodeContent)
{
head = first;
}
else
{
var n = second.next;
second.next = first;
head = second;
second = n;
}
while (first.next != null && second != null)
{
if (first.next.nodeContent < second.nodeContent)
{
first = first.next;
}
else
{
var t = first.next;
var n = second.next;
first.next = second;
second.next = t;
first = first.next;
second = n;
}
}
//check if second list still has elements
if (second != null)
{
first.next = second;
}
return head;
}
public static Node MergeSortedLists(Node first, Node second)
{
if (first == null && second == null)
{
return null;
}
if (first == null && second != null)
{
return second;
}
if (first != null && second == null)
{
return first;
}
Node head;
//if value of first node of left side linked list is greater than first node of second side linked list then swap them
//as we need node with smallest value as first node of left linked list
if (first.nodeContent < second.nodeContent)
{
head = first;
}
else
{
var n = second.next;
second.next = first;
head = second;
second = n;
}
while (first.next != null && second != null)
{
if (first.next.nodeContent < second.nodeContent)
{
first = first.next;
}
else
{
var t = first.next;
var n = second.next;
first.next = second;
second.next = t;
first = first.next;
second = n;
}
}
//check if second list still has elements
if (second != null)
{
first.next = second;
}
return head;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* head;
struct ListNode* cur;
if (!l1) {
return l2;
} else if(!l2) {
return l1;
}
if (l1->val < l2->val) {
head = l1;
l1 = l1->next;
} else {
head = l2;
l2 = l2->next;
}
cur = head;
while(true) {
if (l1 && l2) {
if (l1->val <l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
} else if (!l1 && !l2) {
break;
} else if (l1 && !l2) {
cur->next = l1;
break;
} else if (!l1 && l2) {
cur->next = l2;
break;
}
}
return head;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* head;
struct ListNode* cur;
if (!l1) {
return l2;
} else if(!l2) {
return l1;
}
if (l1->val < l2->val) {
head = l1;
l1 = l1->next;
} else {
head = l2;
l2 = l2->next;
}
cur = head;
while(true) {
if (l1 && l2) {
if (l1->val <l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
} else if (!l1 && !l2) {
break;
} else if (l1 && !l2) {
cur->next = l1;
break;
} else if (!l1 && l2) {
cur->next = l2;
break;
}
}
return head;
}
private static <T extends Comparable> void mergeTwoSortedLinkedList(LinkedList<T> list1, LinkedList<T> list2) {
T firstOfList1 = list1.peek();
T firstOfList2 = list2.peek();
ListIterator<T> iter1 = list1.listIterator();
while (iter1.hasNext()) {
T next = iter1.next();
if (next.compareTo(list2.peek()) <= 0) {
iter1.remove();
list2.addLast(next);
} else {
T first = null;
do {
first = list2.pollFirst();
list2.addLast(first);
first = list2.peek();
} while (first.compareTo(next) <= 0 && !first.equals(firstOfList1) && !first.equals(firstOfList2));
list2.addLast(next);
}
}
while (list2.peekFirst().compareTo(list2.peekLast()) >= 0) {
list2.addLast(list2.pollFirst());
}
}
C/C++ Solution
Node* Merge(Node *head1, Node *head2) {
Node *ptr1 = head1;
Node *ptr2 = head2;
Node *head, *ptr;
if (!head1) {
return head2;
}
if (!head2) {
return head1;
}
if (head1->data < head2->data) {
head = head1;
ptr1 = ptr1->next;
} else {
head = head2;
ptr2 = ptr2->next;
}
ptr = head;
while (ptr1 && ptr2) {
if (ptr1->data < ptr2->data) {
ptr->next = ptr1;
ptr1 = ptr1->next;
} else {
ptr->next = ptr2;
ptr2 = ptr2->next;
}
ptr = ptr->next;
}
if (ptr1) {
ptr->next = ptr1;
}
if (ptr2) {
ptr->next = ptr2;
}
return head;
}
Node* Merge(Node *head1, Node *head2) {
Node *ptr1 = head1;
Node *ptr2 = head2;
Node *head, *ptr;
if (!head1) {
return head2;
}
if (!head2) {
return head1;
}
if (head1->data < head2->data) {
head = head1;
ptr1 = ptr1->next;
} else {
head = head2;
ptr2 = ptr2->next;
}
ptr = head;
while (ptr1 && ptr2) {
if (ptr1->data < ptr2->data) {
ptr->next = ptr1;
ptr1 = ptr1->next;
} else {
ptr->next = ptr2;
ptr2 = ptr2->next;
}
ptr = ptr->next;
}
if (ptr1) {
ptr->next = ptr1;
}
if (ptr2) {
ptr->next = ptr2;
}
return head;
}
node *merge(node *temp1,node *temp2){
int k=0;
node *t,*head,*temp;
while(temp1!=NULL&&temp2!=NULL){
if(temp1->data<temp2->data){
temp=temp1;
}
else{
temp=temp2;
}
if(k==0){
t=temp;
head=temp;
k++;
if(temp==temp1)
temp1=temp1->next;
else
temp2=temp2->next;
}
else{
t->next=temp;
t=t->next;
if(temp==temp1)
temp1=temp1->next;
else
temp2=temp2->next;
}
}
if(temp1==NULL){
t->next=temp2;
}
else{
t->next=temp1;
}
return head;
}
c#, straightforward.
- zr.roman January 16, 2016