Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
void LongestSubSequence(int arr[], int arr2[],int n1,int n2)
{
map<int, int> mapMerged = { make_pair(0,0) };
map<int, int>::iterator mapIt;
int largest = (n1 > n2) ? n1 : n2;
for (int i = 0; i < largest; i++)
{
if (i < n1)
{
mapMerged[arr[i]]++;
}
if (i < n2)
{
mapMerged[arr2[i]]++;
}
}
//Print sequence now.
for (mapIt = mapMerged.begin(); mapIt != mapMerged.end(); mapIt++)
{
if(mapIt->second > 1)
printf("%d ",mapIt->first);
}
}
int main()
{
int arr1[] = {1,5,2,6,3,7,9,10,55,34};
int arr2[] = { 5,6,7,1,2,3,10 };
int n1 = sizeof(arr1) / sizeof(int);
int n2 = sizeof(arr2) / sizeof(int);
LongestSubSequence(arr1,arr2,n1,n2);
}
C#
Cost: O(m + n)
private static List<int> lcs(int[] array1, int[] array2)
{
List<int> r1 = lcsInternal(array1, array2);
List<int> r2 = lcsInternal(array2, array1);
List<int> result;
// Get the longest
if (r1.Count >= r2.Count) { result = r1; }
else { result = r2; }
return result;
}
private static List<int> lcsInternal(int[] array1, int[] array2)
{
int l1 = array1.Length;
int l2 = array2.Length;
List<int> resultList = new List<int>();
// Initially start with 0
int startj = 0;
bool done = false;
for (int i = 0; i < l1 && !done; i++)
{
int v1 = array1[i];
for (int j = startj; j < l2; j++)
{
int v2 = array2[j];
// Not the same value, go to the next j
if (v1 != v2) { continue; }
// v1 == v2
// Store the result
resultList.Add(v1);
// Store the current j + 1 because it'll start there on
// the next iteration
startj = j + 1;
if (startj >= l2)
{
done = true;
}
// Stop the current j, and continue with i
break;
}
}
return resultList;
}
Looking for interview experience sharing and mentors?
- acoding167 May 12, 2019Visit A++ Coding Bootcamp at aonecode.com.
Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.
Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.
Welcome to email us with any questions. Thanks for reading.