Job Interview, Did I Mess Up?
in [C++]
|
From: Daniel T. on 1 Mar 2010 12:23 I had a job interview recently and I was asked to write three functions on a sheet of paper. I was given 45 minutes for this task. Function 1. Given a string of characters consisting only of upper and lower case letters, sort the characters in alphabetical order, lower case first (i.e., aAbBcC...) Function 2. Given a string of words (e.g., "Apple Ball", or "Apple Ball Cow") write a function that generates all permutations. For example: "Apple Ball" should produce: Apple Ball Ball Apple "Apple Ball Cow" should produce: Apple Ball Cow Apple Cow Ball Ball Apple Cow Ball Cow Apple Cow Apple Ball Cow Ball Apple Function3. Using the function declaration "char *copy(char *str, int n)", write a function that will change the size of 'str' so that it equals 'n', padding with spaces if the string needs to be grown. These aren't the exact wording of the questions of course, but the gist is there. My question is, do you think it was cheating for me to use std::sort and std::next_permutation for the first two functions? The test was for a C++ programmer, not a C programmer (strangely, I was told I could answer the questions using any programming language I wanted.) The day after the interview, it occurred to me that they might have wanted me to actually code up a quicksort and permutation algorithm on the spot. Does that sound likely? The only questions the interviewer had regarding my answers were some minor issues regarding function three (he though that std::min didn't exist and wanted to see me implement it, and he was curious why I was unwilling to assume that the input string actually had enough space to hold the result.) Just in case someone is curious what answers I gave them... // Answer 1 bool fn(char a, char b) { bool result = false; if (tolower(a) == tolower(b)) result = a > b; else result = tolower(a) < tolower(b); return result; } void specialSort(char* in) { sort(in, in + strlen(in), &fn); } // Answer 2 // I told the interviewer that I wasn't sure what he meant by "generate" // so I just sent the result to standard output. void permutations(const char* in) { vector<string> strs; stringstream ss(in); string next; while (ss >> next) { strs.push_back(next); } copy(strs.begin(), strs.end(), ostream_iterator<string>(cout, " ")); cout << '\n'; while (next_permutation(strs.begin(), strs.end())) { copy(strs.begin(), strs.end(), ostream_iterator<string>(cout, " ")); cout << '\n'; } } // Answer 3 // The interviewer told me that 'min' wasn't standard (which I know is // wrong) and asked what I would use in place of it. I told him I would // use the ternary operator "?:". // He also asked why I new'ed the output instead of changing 'str', // I showed him that some of the examples provided with the question // showed input strings that were too small to hold the result. The // question didn't explicitly say that I should modify 'str', but he // thought I should have inferred that from the lack of const in the // signature. char* copy(char* str, int n) { char* result = new char[n + 1]; memset(result, ' ', n); result[n] = 0; strncpy(result, str, min(strlen(str), static_cast<size_t>(n))); return result; } (Lastly, if anybody knows of a C++ position in or near Tampa FL, my email address is legitimate. :-) -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: CornedBee on 2 Mar 2010 02:27 On Mar 2, 6:23 am, "Daniel T." <danie...(a)earthlink.net> wrote: > I had a job interview recently and I was asked to write three functions > on a sheet of paper. I was given 45 minutes for this task. > <snip> > These aren't the exact wording of the questions of course, but the gist > is there. My question is, do you think it was cheating for me to use > std::sort and std::next_permutation for the first two functions? The > test was for a C++ programmer, not a C programmer (strangely, I was told > I could answer the questions using any programming language I wanted.) Well, neither I nor anyone else in this group can read your interviewer's mind, but the fact that you could use any language you want strongly suggests that the point of the exercise was to test your ability to find solutions to problems. The way I see it, you answered the first two questions perfectly. (The third could be improved a bit, I think, by only filling the overflow with spaces, not everything.) Asking you to reimplement quicksort doesn't test your problem solving ability, but your ability to memorize and reproduce an existing algorithm. Which is not a particularly useful skill. Sebastian -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Juan Pedro Bolivar Puente on 2 Mar 2010 09:00 I agree with other replies: the answers where probably the best ones one could come up with in such situation. And the questions themselves reveal that the employee is a bit confused... > >> Just in case someone is curious what answers I gave them... >> >> // Answer 1 >> bool fn(char a, char b) >> { >> bool result = false; >> if (tolower(a) == tolower(b)) >> result = a > b; >> else >> result = tolower(a) < tolower(b); >> return result; >> } > > I'd definitely not like that one, and prefer > const int lo_a = tolower(a); > const int lo_b = tolower(b); > if(lo_a == lo_b) > return a > b; > else > return lo_a < lo_b; > > what's the point of juggling with state and in the meantime break DRY SPOT > too? > What do you mean by "dry spot principle"? I Googled it to find it mentioned in only one book which I am not willing to pay for :D Anyway, the only advantage of your solution is that it might be a bit more efficient if the compiler is not able to discover that tolower() has no side-effects when inlining it... On the other hand, his solution has the advantage that fits the "only one return point" principle that many people are dogmatic about --and maybe his interviewer is one of them (I know, your solution could be adapted to match that property). In any case, if you really care that much about about performance, here is a just for fun new implementation for very picky boys ;) bool f (char a, char b) { const char d = a - b; if (a >= 'a') { if (b < 'a') return d <= 'a' - 'A'; return d < 0; } if (b >= 'a') return d < 'A' - 'a'; return d < 0; } Or if you prefer in a more obfuscated fashion: bool fn (char a, char b) { const char d = a - b; return a>='a' ? b<'a' ? d<='a'-'A' : d<0 : b>='a' ? d<'A'-'a' : d<0; } JP -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Walter Bright on 2 Mar 2010 09:00 Daniel T. wrote: > // Answer 3 > // The interviewer told me that 'min' wasn't standard (which I know is > // wrong) and asked what I would use in place of it. I told him I would > // use the ternary operator "?:". > // He also asked why I new'ed the output instead of changing 'str', > // I showed him that some of the examples provided with the question > // showed input strings that were too small to hold the result. The > // question didn't explicitly say that I should modify 'str', but he > // thought I should have inferred that from the lack of const in the > // signature. > char* copy(char* str, int n) > { > char* result = new char[n + 1]; > memset(result, ' ', n); > result[n] = 0; > strncpy(result, str, min(strlen(str), static_cast<size_t>(n))); > return result; > } A minor nit, the code computes the length of str twice (once with strlen, once with strncpy). I generally calc the length of all the strings at the beginning, and use memcpy(). I eschew strncpy because I can never remember if the terminating 0 is included in the 'n' or not. ---------------- Walter Bright Digital Mars http://www.digitalmars.com free C, C++, D programming language compilers -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Daniel T. on 2 Mar 2010 16:02
Juan Pedro Bolivar Puente <magnicida(a)gmail.com> wrote: > I agree with other replies: the answers where probably the best ones one > could come up with in such situation. And the questions themselves > reveal that the employee is a bit confused... Thanks. I don't think the interviewer was confused, but I do think that he is a C expert and only marginally experienced in the standard C++ library. However, there were many grammatical mistakes in the test questions. I don't think English is his native language and that probably confused things a bit. > >> Just in case someone is curious what answers I gave them... > >> > >> // Answer 1 > >> bool fn(char a, char b) > >> { > >> bool result = false; > >> if (tolower(a) == tolower(b)) > >> result = a > b; > >> else > >> result = tolower(a) < tolower(b); > >> return result; > >> } > > > > I'd definitely not like that one, and prefer > > const int lo_a = tolower(a); > > const int lo_b = tolower(b); > > if(lo_a == lo_b) > > return a > b; > > else > > return lo_a < lo_b; > > > > what's the point of juggling with state and in the meantime break DRY SPOT > > too? > > What do you mean by "dry spot principle"? I Googled it to find it > mentioned in only one book which I am not willing to pay for :D I assume he is talking about: http://en.wikipedia.org/wiki/Don't_repeat_yourself Balog Pal and I have a different idea of what constitutes DRY in this case. I think that having the extra variables creates two representations for the piece of knowledge in question (tolower(a) and lo_a both represent the exact same thing.) IMHO, his solution breaks DRY. That said, he was dead on about the while loop in solution 2. I should have avoided that by putting the duplicated code in a separate function or used a do...while loop. (For some reason, I don't care for do...while loops.) > Anyway, the only advantage of your solution is that it might be a bit > more efficient if the compiler is not able to discover that tolower() > has no side-effects when inlining it... On the other hand, his solution > has the advantage that fits the "only one return point" principle that > many people are dogmatic about --and maybe his interviewer is one of > them (I know, your solution could be adapted to match that property). I am pretty dogmatic about the single exit principle. I've had too many times when I was trying to find some hard to track bug in someone else's code only to learn that it had to do with some early return or continue that bypassed a critical piece of code. > In any case, if you really care that much about about performance, here > is a just for fun new implementation for very picky boys ;) > > bool f (char a, char b) > { > const char d = a - b; > if (a >= 'a') { > if (b < 'a') > return d <= 'a' - 'A'; > return d < 0; > } > if (b >= 'a') > return d < 'A' - 'a'; > return d < 0; > } I'm not so worried about performance except in the later stages of a project. I'm more worried about reducing cyclomatic complexity. My function only has two possible paths, where the above has four. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |