## Goldman Sachs Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Written Test

```
Firstly map each value of array B with index, say in "map datastructure"
3->1
4->2
...
7->5
After that update the value of array A which are in B as the key value from "map"
A = [1,3,4,2,5,6] after updating we get C as
C = [ 1,2, 4,3]
from C find the longest increasing subsequence and subtract the length of it from length of B.
ans = ( len(B)-len(C))
```

// As I know, we dont remove 3

// A = [1,3,4,2,5,6], B = [3,4,6,5,7]

// We need find C = maximum run way from A to B = max |S = [a_i]: a_i belongs B and respect order in A and B| = [3,4,5]

// answer = |B| - |C|

int max_run_way(std::vector<int> a, std::vector<int> b) {

size_t ia = 0, ib = 0;

while (ia < a.size() && ib < b.size()) {

if (a[ia++] == b[ib]) {

++ib;

}

}

return b.size() - ib;

}

```
public class MinimumArrayInsertions {
public static void main(String[] args) {
MinimumArrayInsertions app = new MinimumArrayInsertions();
System.out.println(app.minimumInsertions(new int[]{1, 3, 4, 2, 5, 6}, new int[]{3, 4, 6, 5, 7}));
}
public int minimumInsertions(int[] arrA, int[] arrB) {
int i = 0;//min insertions
int al = arrA.length;//element counter in A
for (int n = 0; n < arrB.length;) {
if (n <= al - 1) {
//good to compare and shift until there is equivalence at this position and increment n++
if (arrB[n] == arrA[n]) {
//nice
n += 1;
} else {
//delete in A and shift and loop
for (int p = n; p < al - 1; p++) {
arrA[p] = arrA[p + 1];
}
//reduce arrA length
al -= 1;
//maintin value n and recheck again
}
} else {
//concat all arrB[n] to arrB[arrB.length-1] and count insertions
i = i + (arrB.length - n);
//set value of n to size of B
n = arrB.length;
}
}
return i;
}
}
```

```
def makeEqualArrays(A, B):
lenA = len(A)
lenB = len(B)
A.sort()
B.sort()
for indexA, elementA in enumerate(A):
if (elementA < B[0]):
A[indexA] = None
continue
for indexA, elementA in enumerate(A): #O(N^2)
for indexB, elementB in enumerate(B):
if (elementA not in B):
A[indexA]= None
if elementB not in A:
A.append(elementB)
A = [i for i in A if i]
return (A,B)
A = [1,3,4,2,5,6]
B = [3,4,6,5,7]
print(makeEqualArrays(A,B))
```

why we have to remove 3 from A since it is available in the B, in the above test case.

- MO August 24, 2020