## 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* tail = nullptr;

// Initialize newHead and tail first.
if( first->val < second->val )
{
first = first->next;
}
else
{
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;
}``````

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

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

}
}

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

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 mergedRear = null;

while (itrA || itrB) {
if (itrA && itrB) {
if (itrA.value < itrB.value) {
// pick next from A
} else {
mergedRear.next = itrA;
mergedRear = mergedRear.next;
}
itrA = itrA.next;
} else {
// pick next from B
} else {
mergedRear.next = itrB;
mergedRear = mergedRear.next;
}
itrB = itrB.next;
}
} else if (itrA) {
// pick next from A
} else {
mergedRear.next = itrA;
mergedRear = mergedRear.next;
}
itrA = itrA.next;
} else {
// pick next from B
} else {
mergedRear.next = itrB;
mergedRear = mergedRear.next;
}
itrB = itrB.next;
}
}
}

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

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

``````public class MergeList {

}

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 ]

}

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("[ ");
}

System.out.println("]");

}

static class Node {
Node next;
int value;

}

}``````

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

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

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

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

``````package InterviewPrep;
import java.util.Scanner;
int data;
this.data=number;
this.next=null;
}
}
while(temp1!=null && temp2!=null){
if(temp1.data<temp2.data){
tail=temp1;
temp1=temp1.next;
}
else{
tail.next=temp1;
tail=temp1;
temp1=temp1.next;
}
}
else{
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;
}

}
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
System.out.println();
}

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);
int number = sc.nextInt();
for(int i=0;i<number;i++){
int n=sc.nextInt();
}
start1=null;
curr1=null;
int number2 = sc.nextInt();
for(int i=0;i<number2;i++){
int n=sc.nextInt();
}

}

}``````

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

``````package InterviewPrep;
import java.util.Scanner;
int data;
this.data=number;
this.next=null;
}
}
while(temp1!=null && temp2!=null){
if(temp1.data<temp2.data){
tail=temp1;
temp1=temp1.next;
}
else{
tail.next=temp1;
tail=temp1;
temp1=temp1.next;
}
}
else{
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;
}

}
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
System.out.println();
}

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);
int number = sc.nextInt();
for(int i=0;i<number;i++){
int n=sc.nextInt();
}
start1=null;
curr1=null;
int number2 = sc.nextInt();
for(int i=0;i<number2;i++){
int n=sc.nextInt();
}

}

}``````

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

``````import java.util.Arrays;

public class MergeSortedList {
public static void main(String[] args) {

first.stream().forEach(System.out::println);
}
}``````

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.

### 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.

### 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.