Applied for the position through the company's website and got an invitation from a rep to interview. The interview was a skills test done via email to determine how proficient my coding skills were. You're given two hours to complete two tasks (see below for actual tasks). I submitted my solutions within the time limit and received a confirmation email from the HR rep. After that I never received any follow up correspondence like the mentioned. Figured it was a lost cause.
-------------------------
Please complete the two programming questions below. You can use any IDE you'd like as long as it is written in C or C++ code.
We are looking for correctness and creativity. Impress us with your ability to optimize for memory usage and/or speed. Please comment on your design choices, any tradeoffs you make, as well as memory requirements and run time complexity. You do not need to send us any output from your functions, just the functions themselves.
You will have 2 hours to complete the questions. Also, if you choose, you can also submit any optimizations you make to your code by the end of day. Good luck!
1.
Permutations of a string are defined to be all possible orderings of the characters within the string. For example, the string "cat" has the following permutations:
{ "cat", "cta","atc","act","tca","tac" }
Write an efficient C/C++ function, generate_permutations(), that will generate all the permutations of a given string. This program is expected to be invoked with the input string as the only parameter and expected to output the results to the standard output.
Assumption : If the characters in the string are duplicated, some permutations will be identical, however they are still listed out. For example, "all" will generate the following permutations: { "all","all","lal","lal","lla","lla" }
Function prototype : void generate_permutations(const char* input_string)
Test run : void generate_permutations("eyjafjallajokull").
1a.
Without actually coding the changes, explain how you would modify the above program to print out only the unique strings.
For example, "all" would generate only
{ "all","lal","lla" }
2. Write a function that returns whether one string is an anagram of another. A phrase is an anagram of another phrase if you can rearrange the letters of the first to form the second phrase, using all the original letters once.
Prototype: bool anagram_checker(const char* str1, const char* str2);
Test run: anagram_checker("George Bush", "He bugs Gore"); //this should return true
