Saturday, July 2, 2016

Google interview questions: print matching chars in order of first string

// http://www.impactinterview.com/2009/10/140-google-interview-questions/#software_engineer
// Write a function f(a, b) which takes two character string arguments and returns a string containing
// only the characters found in both strings in the order of a. Write a version which is order N-squared
// and one which is order N.

#include <iostream>
#include <string>
#include <functional>
#include <vector>
#include <cstring>

std::string match_the_stupid_way(std::string a, std::string b)
{
// the silly way is just for each char in string a O(n)
// look through string b O(n) double loop hence O(n^2)

std::string res;

for (std::string::iterator ait = a.begin();
ait != a.end();
++ait)
{
// ok match the first each char
std::string::iterator bit = b.begin();
while (bit != b.end() and
*bit != *ait)
{
++bit;
}

if (bit != b.end())
res += *ait;
}
return res;
}

std::string match_the_fast_way(std::string a, std::string b)
{
// O(N) .. this imples reading over a string (which takes O(N)) and
// digesting into an O(1) data struture and then check over the other...

// well an O(1) data structure is a hash or table..
std::vector<bool> found_char(256,false);

for (std::string::iterator bit = b.begin();
bit != b.end();
++bit)
{
found_char[*bit] = true;
}

// and the second O(N) check is
std::string res;
for (std::string::iterator ait = a.begin();
ait != a.end();
++ait)
{
if (found_char[*ait])
res += *ait;
}

return res;
}

void test(std::function<std::string (std::string,std::string)> func,
std::string a,
std::string b,
std::string exp)
{
std::string out = func(a,b);

std::cout << (out == exp ? "passed" : "FAILED")
<< " a:\""     << a
<< "\" b:\""   << b
<< "\" out:\"" << out
<< "\" exp:\"" << exp
<< "\"\n";
}

void test_set(std::function<std::string (std::string,std::string)> func)
{
test(func, "a", "cba", "a");
test(func, "aaa", "cba", "aaa");  // hmm question isnt clear on repeats.. assume it does repeats
test(func, "abcdefg", "gfedcba", "abcdefg");
test(func, "the quick brown fox", "peter piper picked a pepper", "te ick r ");
std::cout << "*** SET DONE ***\n";
}

int main()
{
test_set(match_the_stupid_way);
test_set(match_the_fast_way);
}


Output is

passed a:"a" b:"cba" out:"a" exp:"a"
passed a:"aaa" b:"cba" out:"aaa" exp:"aaa"
passed a:"abcdefg" b:"gfedcba" out:"abcdefg" exp:"abcdefg"
passed a:"the quick brown fox" b:"peter piper picked a pepper" out:"te ick r " exp:"te ick r "
*** SET DONE ***
passed a:"a" b:"cba" out:"a" exp:"a"
passed a:"aaa" b:"cba" out:"aaa" exp:"aaa"
passed a:"abcdefg" b:"gfedcba" out:"abcdefg" exp:"abcdefg"
passed a:"the quick brown fox" b:"peter piper picked a pepper" out:"te ick r " exp:"te ick r "
*** SET DONE ***