Goldman Sachs Interview Question for Software Engineer / Developers


Country: Singapore
Interview Type: In-Person




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


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