Status : New grad, Masters in Computer Science from Top 20 CS universities
Position : Graduate Software Engineer @Bloomberg
Location : United Kingdom
Date : October 2019
I only reached phone interview stage. It was 45 minutes long and consisted of:
- [5-10 minutes] Questions on CV: tell me more about yourself, why Computer Science?, tell me about your recent projects, which languages do you prefer and why, what is your strongest programming language
- [15-25 minutes] Only one coding question - solve in any language you prefer. Followed by a follow-up to that question without actually having to implement it. Discuss time and space complexity of the solution. See details below.
- [5-10 minutes] Ask the interviewer any questions about them or the company
Overall impressions: Interviewer was a Senior Software Engineer. He tried to be helpful but never pointed out any mistakes I might have made (since I implemented a valid solution, but did not progress to the next stage of the recruiting process - clearly there must have been something wrong I did which he did not mention about in order to give me a chance to re-think and eventually reach the correct answer.) I believe it was not hard at all but I could have done better if I had practiced more beforehand. Three days after the interview I received a rejection email. (no feedback provided - normal for this stage of the recruiting process).
Coding question:
Consider a “binary string” such as: 0110 - it consists of either 0 or 1 but also can be longer or less than 4 characters
Now imagine we swap a character in the string for “wildcard” (represented by ? ) - i.e. 01?0
A wildcard evaluates to 0 or 1 .
Task: Print out all possible permutations of that string with the wildcard.
Sample Input and Outputs:
-
input:
01?0=> output:["0110", "0100"] -
input:
0??0=> output:["0100", "0110", "0010", "0000"]
Explain time and space complexity of your solution. Can that be improved?
Follow-up: How would you change your code if a wildcard can evaluate to numbers of 0 to 9 ? How would that affect time and space complexity of your code? (P.S. Interviewer did not actually want me to implement the solution, but rather explain it to him with words).
[My Solution] I am providing the solution I implemented in the 20 minutes I had. I would appreciate if you could rate it and discuss its time and space complexity (which I am unsure about). I would also love to hear any suggestions on how to improve my code or read about a completely different and better approach to the problem.
Implemented in JavaScript:
let output = [];
let input = "0??0";
let charArray = input.split('');
function compose(str, num, charArray) {
if(num == 0 || num == 1) {
str += num;
}
for(let i = 0; i < charArray.length; i++) {
if(charArray[i] == "?") {
charArray = charArray.slice(i+1, charArray.length);
compose(str, 1, charArray);
compose(str, 0, charArray);
} else {
str += charArray[i];
}
}
if(str.length == input.length) {
output.push(str);
}
}
compose("", null, charArray);
// Print answer
console.log(`${input} => ${output}`);