## NetApp Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

Better time complexity -

```
public static int[] findLargestCommonSub(int[] arr1, int[] arr2){
if(arr1 == null || arr1.length <= 0 ||
arr2 == null || arr2.length <= 0) return null;
Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
int result[] = new int[ arr1.length > arr2.length ? arr2.length : arr1.length ];
int k = 0;
for(int i = 0; i < arr1.length; i++){
map.put(arr1[i], (map.get(arr1[i]) == null ? 1 : map.get(arr1[i])+1));
}
for(int j = 0; j < arr2.length; j++){
if(map.containsKey(arr2[j])){
result[k++] = arr2[j];
if(map.get(arr2[j]) > 1){
map.put(arr2[j], map.get(arr2[j])-1);
}else{
map.remove(arr2[j]);
}
}
}
return result;
}
```

DP solution O(n^2) time and space:

Let:

`OPT[x][y] be the length of the longest common sub-array between two prefixes A[1..x] and B[1..y].`

Then, the recursive formula is:

```
OPT[x][y] = max(OPT[x][y-1], OPT[x-1][y], OPT[x-1][y-1] + 1), if A[x] = B[y];
= max(OPT[x][y-1], OPT[x-1][y]), if A[x] != B[y];
```

Initial values:

```
OPT[i][j] = 0 for all i, j;
Note: we consider indices start from 1;
```

The length of the longest common sub array is:

`OptLen = OPT[n][m];// n = size of A, m = size of B`

To find such a longest common sub array itself, we can trace back by using OPT table and the recursive formula.

This can be implemented in O(n^2) time and space.

Using a map like what Sathish does is probably best O(n + m) and O(n) memory (cleaned up a bit so it's easier to read):

```
public static int[] getCommonArray(int[] arr1, int[] arr2){
HashMap<Integer, Integer> instanceCountMap = new HashMap<Integer, Integer>();
for(int i : arr1){
Integer count = instanceCountMap.get(i);
if(count == null){
instanceCountMap.put(i, 1);
}
else{
instanceCountMap.put(i, count + 1);
}
}
ArrayList<Integer>results = new ArrayList<Integer>();
for(int i : arr2){
Integer count = instanceCountMap.get(i);
if(count != null){
results.add(i);
if(count > 1){
instanceCountMap.put(i, count -1);
}
else{
instanceCountMap.remove(i);
}
}
}
int[] resultArr = new int[results.size()];
for(int i = 0; i < resultArr.length; i++){
resultArr[i] = results.get(i);
}
return resultArr;
}
```

kind of merge sort.

```
void solve()
{
using namespace std;
vector<int> set1 = { 1, 2, 3, 2, 3, 2 };
vector<int> set2 = { 2, 2, 3, 3, 4, 5 };
vector<int> resultSet;
sort(set1.begin(), set1.end());
sort(set2.begin(), set2.end());
auto it = set2.begin();
for (auto value : set1)
{
if (value == *it) {
resultSet.push_back(value);
++it;
continue;
}
while ((value > *it) && (it != set2.end()))
++it;
if (it == set2.end())
break;
}
}
```

{

public static void main(String[] args)

{

int [] arr1 = {1,2,3,2,3,2};

int [] arr2 = {2,2,3,3,4,5};

int [] same= new int[arr1.length];

int size=0;

int [] skip= new int[arr2.length];

for(int i=0; i<skip.length; i++)

{

skip[i]=0;

}

for(int i=0; i<arr1.length; i++)

{

for(int x=0; x<arr2.length; x++)

{

if(skip[x]==0)

{

if(arr1[i]==arr2[x])

{

same[size]=arr1[i];

size++;

skip[x]=1;

}

}

}

}

for(int i=0; i<size; i++)

{

System.out.print(same[i]);

}

}

}

- Abhi October 29, 2014