Honeywell Interview Question
Software DevelopersCountry: India
Interview Type: In-Person
The task requires: "Need efficient algorithm to do this".
And this is just a unix command, but what algorithm is behind it?
I suppose it is something like as described above.
Complexity : O(n)
#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>
using namespace std;
int main() {
vector<string> v1 {"Raja Uthaya", "Antony Karthi"
,"Christopher Raja","Manickam Antony" ,"Veeramani", "Chinmay Garg" };
vector<string> v2 {"Antony Karthi"
,"Christopher Raja","Veeramani" };
unordered_set<string> s1 (v1.begin(), v1.end());
unordered_set<string> s2 (v2.begin(), v2.end());
for(auto it : s2) {
if(s1.find(it) != s1.end()) {
s1.erase(it);
}
}
for(auto it : s1) {
cout << it << endl;
}
return 0;
}
Put everything in file2 into a hashtable. Then go through file 1, and check if the name matches to a key for file2 hashtable
Put all the names from 2.txt into hashset (of hashtabe, in general - into structure with O(1) access).
Perform a loop against "1.txt".
In a loop: if hashset.Contains( <current word from 1.txt> ), then continue. Otherwise - display it on screen.
O(n + m), where n - number of names in 1.txt., m - number of names in 2.txt.
But, as the task says m << n, then asymptotic complexity O(n).
- srterpe December 09, 2015