Goldman Sachs Interview Question
Software Engineer / DevelopersCountry: Singapore
Interview Type: In-Person
public static void main(String[] args){
Node N5 = new Node(5, null);
Node N3 = new Node(3, N5);
Node N1 = new Node(1, N3);
Node N7 = new Node(7, null);
Node N6 = new Node(6, N7);
Node N4 = new Node(4, N6);
Node N2 = new Node(2, N4);
merge(N1, N2);
}
//1,3,5 2,4
public static void merge(Node list1, Node list2){
Node head = new Node(list1.val);
Node node = head;
list1 = list1.next;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
node.next = list1;
list1 = list1.next;
}else if(list2.val < list1.val){
node.next = list2;
list2 = list2.next;
}
node = node.next;
}
if(list1 != null){
node.next = list1;
}
if(list2 != null){
node.next = list2;
}
while(head != null){
System.out.print(head.val + " ");
head = head.next;
}
}
static class Node{
int val;
Node next;
public Node(int val){
this.val = val;
}
public Node(int val, Node node){
this.val = val;
this.next = node;
}
}
My JavaScript in-place linear time solution. It uses the same idea that the combine step of MergeSort. A bit messy because of the pointers to nodes handling.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
function merge(A, B) {
let itrA = A;
let itrB = B;
let mergedHead = null;
let mergedRear = null;
while (itrA || itrB) {
if (itrA && itrB) {
if (itrA.value < itrB.value) {
// pick next from A
if (!mergedHead) {
mergedHead = itrA;
mergedRear = mergedHead;
} else {
mergedRear.next = itrA;
mergedRear = mergedRear.next;
}
itrA = itrA.next;
} else {
// pick next from B
if (!mergedHead) {
mergedHead = itrB;
mergedRear = mergedHead;
} else {
mergedRear.next = itrB;
mergedRear = mergedRear.next;
}
itrB = itrB.next;
}
} else if (itrA) {
// pick next from A
if (!mergedHead) {
mergedHead = itrA;
mergedRear = mergedHead;
} else {
mergedRear.next = itrA;
mergedRear = mergedRear.next;
}
itrA = itrA.next;
} else {
// pick next from B
if (!mergedHead) {
mergedHead = itrB;
mergedRear = mergedHead;
} else {
mergedRear.next = itrB;
mergedRear = mergedRear.next;
}
itrB = itrB.next;
}
}
return mergedHead;
}
const A = new Node(1);
A.next = new Node(3);
A.next.next = new Node(7);
A.next.next.next = new Node(9);
const B = new Node(2);
B.next = new Node(3);
B.next.next = new Node(5);
B.next.next.next = new Node(8);
B.next.next.next.next = new Node(10);
console.log(merge(A, B));
public class MergeList {
static Node mergeList(Node head1, Node head2) {
return mergeInternal(head1, head2);
}
static Node mergeInternal(Node n1, Node n2) {
if(n1.value > n2.value) {
Node next2 = n2.next;
n2.next = n1;
n1 = n2;
n2 = next2;
} else {
while(n1.next != null && n1.next.value < n2.value) n1 = n1.next;
Node next1 = n1.next;
n1.next = n2;
n2 = n2.next;
n1.next.next = next1;
}
if(n2 == null) return n1;
return mergeInternal(n1,n2);
}
public static void main(String[] args) {
int[] list1 = {2, 4, 7, 10, 13, 16, 17, 18, 19, 20, 21, 30, 35};
int[] list2 = {1, 2, 3, 4, 5, 5, 7, 8, 9, 20, 23, 25, 40};
// [ 1 1 2 2 3 4 4 5 5 7 7 8 9 10 13 16 17 18 19 20 20 21 23 25 30 35 40 ]
Node head1 = makeList(list1);
Node head2 = makeList(list2);
Node merged = mergeList(head1,head2);
printList(head1.value > head2.value ? head2:head1);
}
public static Node makeList(int[] values) {
Node prev=null;
Node ret=null;
for(int i=0; i<values.length;i++) {
Node curr = new Node();
curr.value = values[i];
if(prev == null) {
ret = curr;
} else {
prev.next = curr;
}
prev = curr;
}
return ret;
}
public static void printList(Node head) {
System.out.print("[ ");
while (head != null) {
System.out.print(head.value+ " ");
head = head.next;
}
System.out.println("]");
}
static class Node {
Node next;
int value;
}
}
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
}
int val_;
};
list<Node *> Merge(list<Node *> &l1, list<Node *> &l2)
{
list<Node *> out;
while (!l1.empty() ||
!l2.empty())
{
if (!l1.empty() &&
(l2.empty() || l1.front()->val_ <= l2.front()->val_))
{
out.push_back(l1.front());
l1.pop_front();
} else {
out.push_back(l2.front());
l2.pop_front();
}
}
return out;
}
int main()
{
Node n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7);
list<Node *> l1 = {&n1, &n3, &n5, &n6};
list<Node *> l2 = {&n2, &n4, &n7};
auto l = Merge(l1, l2);
for (Node *n : l) {
cout << n->val_ << "->";
}
cout << "\n";
}
Node* merge( Node* l1, Node* l2 )
{
if( NULL == l1 )
return;
else if( NULL == l1 )
return;
int len1 = get_len ( l1 );
int len2 = get_len ( l2 );
if( len2 > len1 )
{
Node* t1 = l1;
l1 = l2;
l2 = t1;
}
Node* curr_l1;
Node* curr_l2 = l2;
Node* prev_l1 = NULL;
int check = 1;
while( curr_l2 != NULL )
{
cout << endl << check++ << endl;
Node *curr_l2_next = curr_l2->next;
curr_l1 = l1;
while( curr_l1 != NULL && curr_l1->data <= curr_l2->data )
{
prev_l1 = curr_l1;
curr_l1 = curr_l1->next;
}
if( NULL == prev_l1 )
{
curr_l2->next = l1;
l1 = curr_l2; //head changes
}
else
{
prev_l1->next = curr_l2;
prev_l1->next->next = curr_l1;
}
curr_l2 = curr_l2_next;
}
cout << endl;
while( l1 != NULL )
{
cout << l1->data << " ";
l1 = l1->next;
}
return l1;
}
package InterviewPrep;
import java.util.Scanner;
class LinkedListNode{
int data;
LinkedListNode next;
public LinkedListNode(int number) {
this.data=number;
this.next=null;
}
}
public class MergeTwoSortedLinkedList {
static LinkedListNode start1=null;
static LinkedListNode curr1=null;
private static LinkedListNode mergeFunction(LinkedListNode head1, LinkedListNode head2) {
LinkedListNode temp1=head1;
LinkedListNode temp2=head2;
LinkedListNode head=null;
LinkedListNode tail=null;
while(temp1!=null && temp2!=null){
if(temp1.data<temp2.data){
if(head==null){
head=temp1;
tail=temp1;
temp1=temp1.next;
}
else{
tail.next=temp1;
tail=temp1;
temp1=temp1.next;
}
}
else{
if(head==null){
head=temp2;
tail=temp2;
temp2=temp2.next;
}
else{
tail.next=temp2;
tail=temp2;
temp2=temp2.next;
}
}
}
if(temp1!=null){
tail.next=temp1;
}
else if(temp2!=null){
tail.next=temp2;
}
return head;
}
public static void printLinkedList(LinkedListNode start){
LinkedListNode temp = start;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
System.out.println();
}
public static LinkedListNode createLinkedList(int number){
LinkedListNode node = new LinkedListNode(number);
if(start1==null){
start1=node;
curr1=node;
}
else{
curr1.next=node;
curr1=node;
}
return start1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
LinkedListNode head1=null;
LinkedListNode head2=null;
int number = sc.nextInt();
for(int i=0;i<number;i++){
int n=sc.nextInt();
head1 = createLinkedList(n);
}
start1=null;
curr1=null;
int number2 = sc.nextInt();
for(int i=0;i<number2;i++){
int n=sc.nextInt();
head2 = createLinkedList(n);
}
printLinkedList(head1);
printLinkedList(head2);
LinkedListNode newhead = mergeFunction(head1,head2);
System.out.println(newhead.data);
printLinkedList(newhead);
}
}
package InterviewPrep;
import java.util.Scanner;
class LinkedListNode{
int data;
LinkedListNode next;
public LinkedListNode(int number) {
this.data=number;
this.next=null;
}
}
public class MergeTwoSortedLinkedList {
static LinkedListNode start1=null;
static LinkedListNode curr1=null;
private static LinkedListNode mergeFunction(LinkedListNode head1, LinkedListNode head2) {
LinkedListNode temp1=head1;
LinkedListNode temp2=head2;
LinkedListNode head=null;
LinkedListNode tail=null;
while(temp1!=null && temp2!=null){
if(temp1.data<temp2.data){
if(head==null){
head=temp1;
tail=temp1;
temp1=temp1.next;
}
else{
tail.next=temp1;
tail=temp1;
temp1=temp1.next;
}
}
else{
if(head==null){
head=temp2;
tail=temp2;
temp2=temp2.next;
}
else{
tail.next=temp2;
tail=temp2;
temp2=temp2.next;
}
}
}
if(temp1!=null){
tail.next=temp1;
}
else if(temp2!=null){
tail.next=temp2;
}
return head;
}
public static void printLinkedList(LinkedListNode start){
LinkedListNode temp = start;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
System.out.println();
}
public static LinkedListNode createLinkedList(int number){
LinkedListNode node = new LinkedListNode(number);
if(start1==null){
start1=node;
curr1=node;
}
else{
curr1.next=node;
curr1=node;
}
return start1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
LinkedListNode head1=null;
LinkedListNode head2=null;
int number = sc.nextInt();
for(int i=0;i<number;i++){
int n=sc.nextInt();
head1 = createLinkedList(n);
}
start1=null;
curr1=null;
int number2 = sc.nextInt();
for(int i=0;i<number2;i++){
int n=sc.nextInt();
head2 = createLinkedList(n);
}
printLinkedList(head1);
printLinkedList(head2);
LinkedListNode newhead = mergeFunction(head1,head2);
System.out.println(newhead.data);
printLinkedList(newhead);
}
}
import java.util.Arrays;
import java.util.LinkedList;
public class MergeSortedList {
public static void main(String[] args) {
LinkedList<Integer> first = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
LinkedList<Integer> second = new LinkedList<>(Arrays.asList(6, 7, 8, 9, 10));
second.stream().forEach(e -> first.addLast(e));
first.stream().forEach(System.out::println);
}
}
Since we are not allowed to create a dummy node, we need to adjust the newHead first.
- mr.robot.fun.society November 12, 2017