Goldman Sachs Interview Question
Software Engineer / DevelopersCountry: 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))
def makeEqualArrays(L1,L2):
#check lengh of two list
if len(L1)>0 and len(L2)>0:
# loop through second list and add missing item of L2 in L1
for j in range(len(L2)):
if L2[j] not in L1:
L1.append(L2[j])
print("J",j,"value:",L2[j])
# loop through first list and set item to None that doesnt exist in L2
for j in range(len(L1)):
if L1[j] not in L2:
L1[j]= None
print("J",j,"value:",L1[j])
# build new list which contain only value != NONE
# ==> avoid != False because its wont return value zero
L1=[i for i in L1 if i!=None ]
return L1
results=makeEqualArrays([1,2,3,4,5,6],[1,6,8,9])
#output : results = [1,6,8,9]
print(results)
results=makeEqualArrays([0,2,3],[0,6,8,9])
#output : results = [0, 6, 8, 9]
print(results)
def makeEqualArrays(L1,L2):
#check lengh of two list
if len(L1)>0 and len(L2)>0:
# loop through second list and add missing item of L2 in L1
for j in range(len(L2)):
if L2[j] not in L1:
L1.append(L2[j])
print("J",j,"value:",L2[j])
# loop through first list and set item to None that doesnt exist in L2
for j in range(len(L1)):
if L1[j] not in L2:
L1[j]= None
print("J",j,"value:",L1[j])
# build new list which contain only value != NONE
# ==> avoid != False because its wont return value zero
L1=[i for i in L1 if i!=None ]
return L1
results=makeEqualArrays([1,2,3,4,5,6],[1,6,8,9])
#output : results = [1,6,8,9]
print(results)
results=makeEqualArrays([0,2,3],[0,6,8,9])
#output : results = [0, 6, 8, 9]
print(results)
#My solution for the problem
A = [1, 3, 4, 2, 5, 6]
B = [3, 4, 6, 5, 7]
A.sort()
B.sort()
count = 0
newArray = []
for i in A:
for x in B:
if i-x == 0:
newArray.append(i)
num_difference_CountA = len(A)-len(newArray)
num_difference_CountB = len(B)-len(newArray)
print(num_difference_CountB+num_difference_CountA)
why we have to remove 3 from A since it is available in the B, in the above test case.
- MO August 24, 2020