public int checkForZeros(int[] arr) {
int total = 0;
for (int i : arr) {
if (i == 0) {
total = total + 1;
}
}
return total;
}
public int[] productArray(int[] arr) {
if (arr.length == 1) return new int[0];
int total = 1;
int zeroCount = checkForZeros(arr);
if (zeroCount > 1) {
for (int i = 0; i < arr.length; i++) {
arr[i] = 0;
}
} else if (zeroCount == 1) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
total = total * arr[i]; //2
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
arr[i] = total; //8
} else {
arr[i] = 0;
}
}
} else {
for (int i = 0; i < arr.length; i++)
total = total * arr[i]; // 24
for (int i = 0; i < arr.length; i++)
arr[i] = total / arr[i];
}
return arr;
}
I explained to him the time and space complexity of the algorithm and also ran through all corner test cases.
Follow-up:
He said my implementation was correct but asked me if this can be done in any other approach as division operation is very expensive.
I hardly had 4-5 mins to come up with new approach and wasn’t able to provide an alternate. He wrapped up the call with last 3 mins open for any questions. I asked him if he had 2 problems statements in mind for me before the interview started and he said No. He said it depended on the approach i followed. The follow up question was his second problem statement. We wrapped up the call.
I get an email today from the recruiter saying they are not moving forward with my profile. Upon enquiring the reason, He said the comments from the interviewer were “Speed, issues coming up with the correct solution and not being able to do the second question as you mentioned”
Thanks for sharing, it sucks I know. I’ve faced this too [ in facebook itself. Though in my case, he pushed a new ‘Hard’ level question to solve in the last 10 min. Provided that he came late (5 min) then took(2 min for the intro) and initial 5-8 min to explain the first question itself. I solved it around 15-20 min and for the second question, he again took around 3-5 min to explain the question in 45 min interview Onsite. After clearing all the round very well {all the remaining round was awesome, did not even stuck in a single point. All the interviewer were impressed but not this guy } ]
I believe there are few things possible
Did you explain your approach to him/her before coding it up?
if you explained, did you asked him/her to look for a more better solution?
In case of the answer is true for both of the above then the ‘interviewer was poor’.
Otherwise, you need to learn this technique.
I follow this technique always regardless, until n unless the interviewer intentionally says that code it up as soon as possible without worrying about the complexity.
Interviewer joined a few mins late and there were some technical difficulties before getting started but afterwards I was asked a question to return the longest substring with at most k distinct characters (very similar to question linked below, but we needed to return the actual substring).
Asked clarifying question about the following input / edge cases:
Empty/Null input, k <= 0, are the characters UTF-8 or other, will there be any non alphabetic characters in input, what about capital versions, should we count uppercase same as lowercase or not
Then discussed Space/Time of O(n) / O(k) where n = len(s)
Question: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
Solution:
Very similar to provided solution from LeetCode with one difference being instead of using max() to update the longest substring, placing it in an if() and maintaining a pointer to the longest substr start index alongside longestSubstr length.
def kDistinctCharacters(s: str, k: int) -> str:
longest_substr = 0
char_freq = {}
start = 0
substr_start = 0
for i in range(len(s)):
char = s[i]
if char not in char_freq:
char_freq[char] = 0
char_freq[char] += 1
while len(freq) > k:
char_freq[s[start]] -= 1
if char_freq[s[start]] == 0:
del char_freq[s[start]]
start += 1
if longest_substr <= i - start + 1:
longest_substr = i - start + 1
substr_start = start
return s[substr_start:substr_start + longest_substr]