CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Goldman Sachs Interview Question for Software Engineer / Developers


Country: Singapore
Interview Type: In-Person
More Questions from This Interview



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

Since we are not allowed to create a dummy node, we need to adjust the newHead first.

class node
{
public:
	int val;
	node* next;
	node( int v ):val(v), next(nullptr)
	{}
};

node* mergeTwoSortedList( node* first, node* second )
{
	if( first == nullptr ) return second;
	if( second == nullptr ) return first;
	
	if(  first == second ) return first;
	
	node* newHead = nullptr;
	node* tail = nullptr;
	
	// Initialize newHead and tail first.
	if( first->val < second->val )
	{
		newHead = tail = first;
		first = first->next;
	}
	else
	{
		newHead = tail = second;
		second = second->next;		
	}
	
	// Go over both list at same time and update new list 
	while( first && second )
	{
		if( first->val < second->val )
		{
			tail->next = first;
			first = first->next;
		}
		else
		{
			tail->next = second;
			second = second->next;
		}
		tail = tail->next;
	}
	
	// Append unfinished list to end of new list
	tail->next = first ? first : second;
	return newHead;
}

- mr.robot.fun.society November 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sudip.innovates November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

        }


}

- thatfernando@yahoo.com November 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public ListNode merge(ListNode l1, ListNode l2) {
    if(l1 == null || l2 == null) {
        return l1 == null ? l2 : l1;
    }
    if(l1.val > l2.val) {
        l2.next = merge(l1, l2.next);
        return l2;
    }
    l1.next = merge(l1.next, l2);
    return l1;
}

- samantha November 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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";
}

- Alex December 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vinay February 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

}

- Nikhil Attri September 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

}

- Nikhil Attri September 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- mprabhat September 14, 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