Common elements between array of strings
Given two 1-dimensional arrays containing strings of lowercase alphabets, print the elements that are common in both the arrays i.e. the strings that are present in both the arrays.

Note:

An element of one array can be mapped only to one element of the array. For example : Array 1 = {“ab”, “dc”, “ab”, “ab”} Array 2 = {“dc”, “ab”, “ab”} The common elements for the above example will be “dc”, “ab”, and “ab”.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow. The first line of each test case includes two integers, 'N' and 'M', representing the sizes of both the arrays. The second line of each test case contains 'N' single-spaced strings representing the elements of the first array. The third line of each test case contains 'M' single-spaced strings representing the elements of the second array.

Output Format:

For each test case, the common elements of both arrays are printed in the order in which they appear in the second array. The elements are printed in a single space-separated manner. The output for each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the common elements in the specified order.

Constraints:

1

Question

Common elements between array of strings

Given two 1-dimensional arrays containing strings of lowercase alphabets, print the elements that are common in both the arrays i.e. the strings that are present in both the arrays.

Note:

An element of one array can be mapped only to one element of the array. For example :

Array 1 = {“ab”, “dc”, “ab”, “ab”}
Array 2 = {“dc”, “ab”, “ab”} 

The common elements for the above example will be “dc”, “ab”, and “ab”.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case includes two integers, 'N' and 'M', representing the sizes of both the arrays.

The second line of each test case contains 'N' single-spaced strings representing the elements of the first array.

The third line of each test case contains 'M' single-spaced strings representing the elements of the second array.

Output Format:

For each test case, the common elements of both arrays are printed in the order in which they appear in the second array. The elements are printed in a single space-separated manner. 

The output for each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the common elements in the specified order.

Constraints:

1 <= T <= 10
1 <= N, M <= 10000    
1 <= S <= 10

Where 'T' is the number of test cases. 'N' and 'M' are the sizes of both the arrays and 'S' is the length of the strings of the arrays. Also, the strings contain only lowercase alphabets.

Time limit: 1 sec.

Accepted Answer

Step 1 : Traverse through the first array and store its contents in a hashmap. If key (string) appears for the first time set corresponding value (count) as 1, else increment count.
Step 2 : Traverse through the second array. If an element from this array (key/string) is present in the hashmap print it and decrement its value (count) by 1.
Step 3 : If value (count) becomes 0 after decrementing for any key (string) remove it from the hashmap.

Note : Be careful while taking string inputs after integer input because the nextInt() method doesn't read the newline character of your input, so when you issue the command nextLine(), the Scanner finds the newline character and gives you that as a line.

Accepted Answer

Bruteforce approach

The main idea behind this approach is to solve the problem intuitively, and for each string in the second array, check if it exists in the first array (we are checking for each string in the second array because we need the output in the order in which they appear in the second array).

Algorithm :

Start traversing the second array and for each string in the second array, do the following :
- Loop through the first array and see if the string is present in the first array. If it is present in the first array, add the string to the answer as it is present in both the arrays. Also, in the first array, replace the string with an empty string so that the same string is not considered again in the subsequent iterations.
The answer will contain the strings in the order in which they appear in the second array. Simply return the answer.

Space Complexity: OtherExplanation:

O(K), where ‘K’ = min('N', ‘M’) i.e. ‘K’ is the minimum of the sizes of both the arrays.

Additional space is used to store the answer i.e. the common strings of both the arrays. The number of common strings of both the arrays would be K = min(N, M) and thus, the final space complexity is O(K).

Time Complexity: OtherExplanation:

O(N * M), where ‘N’ and 'M' are the sizes of both the arrays.

For each string in the second array, we are traversing the first array. Thus, the final time complexity will be O(N * M).

Accepted Answer

Using Hashmap

The main idea behind this approach is to use a hashmap to store the count of the strings.

Algorithm :

Traverse the first array and for every string in the first array do the following :
- If the string is not already present in the hashmap, insert it in the hashmap with a count of 1.
- Else increment the count of the string in the hashmap by 1.
Now, traverse the second array and for every string do the following :
- If the string is present in the hashmap, this string is a common element of both the arrays. Add this string to the answer and decrement its count in the hashmap.
  Now, if the count becomes 0, this means that all the instances of the current string in the first array have been considered. So, delete this string from the hash map.
- If the string is not present in the hashmap, then this string is not present in the first array and will not be a part of the answer.
After both the traversals, the answer will have the common strings in the order in which they appear in the second array. Thus, we need to simply return the answer.

Space Complexity: O(n)Explanation:

O(N), where 'N' is the size of the first array.

We are storing all the strings of the first array in the hashmap. Thus, the final space complexity is O(N).

Time Complexity: OtherExplanation:

O(K * S), where ‘K’ = max('N', ‘M’) i.e. ‘K’ is the maximum of the sizes of both the arrays and 'S' is the average size of the strings.

The traversal of an array takes linear time. Also, inserting a string in the hashmap will take O(S) time on average where S is the size of the string.

Thus, the final time complexity will be O(K * S) where K = max(N, M).

Accepted Answer

Using Trie

The main idea behind this approach is to use a trie to store the frequencies of the strings in the first array. We can add an additional field “COUNT” in the implementation of the node of the trie. This field will be equal to the number / occurrences of the current string in the first array. For the nodes that do not represent the end of a string, the value of count will be zero.

Firstly, we traverse the first array and insert the strings in a trie. While inserting a string in the trie, we increment the variable “COUNT” of the last node i.e. the node representing the last character of the string.

After the creation of the trie, we traverse the second array and for each string in the second array, we check if it is present in the trie. If the string exists in the trie, we add it to the answer and decrement the variable “COUNT” for the last node i.e. the node representing the last character of the string.

After the traversal of the second array, the answer will contain the common strings.

Space Complexity: OtherExplanation:

O(26 * N * S), where ‘N’ is the size of the first array and ‘S’ is the average length of the strings.

For every string in the first array of length S, we will create S nodes and every node will have an array of size 26 (to store the children of the node). Since there are N strings in the first array, the final space complexity will be O(26 * N * S).

Time Complexity: OtherExplanation:

O(K * S), where ‘K’ = max('N', ‘M’) and ‘S’ is the average length of strings.

Both, inserting and searching a string in the trie, take O(S) time, where S is the length of the string. Thus, inserting N strings of the first array will take O(N * S) time, and searching for M strings of the second array will take O(M * S) time. Thus, the final time complexity will be O(N * S + M * S) = O((N + M) * S) = O(K * S) where K = max(N, M).

Given two 1-dimensional arrays containing strings of lowercase alphabets, print the elements that are common in both the arrays i.e. the strings that are present in both the arrays.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Societe Generale Global Solution Centre Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Societe Generale Global Solution Centre Software Engineer