Read this question: https://leetcode.com/problems/minimum-number-of-frogs-croaking/ The solution I came up with an implemented, is basically a simulation solution. I keep an array of stacks, and as I scan for characters, I try to add the character to one of the existing frogs, or start a new one if needed. It works, it passes. To speed up having to iterate over each stack, there is a hashmap of “I need X character -> stack indices”. It’s O(characters) complexity, and ~O(3*characters) complexity in space (the stack, the hashmap, and the result). Anyway, I came up with the this solution in 5 minutes, and it took me about 20 to implement; the way you actually would in an interview. It turns out, there’s an even more efficient solution. You don’t need to keep stacks at all, you can just keep character counts and then check if any counts are out of order. It’s O(characters) time and O(1) space. I might’ve come up with that solution if I had more time to think about it, maybe 30 minutes to an hour to really understand the problem. But under the constraints of an interview where I’m nervous. And I want to give a solution fast, I never will. So now interviewer will see my first solution, think I’m a noob, smile and nod and let me pass, only to hit me with a fat rejection, because I didn’t implement the most optimal approach. This is what 99% of you are missing when you think you “passed all your technical interviews” and then don’t receive an offer. There’s a very high chance you gave “a solution” but it wasn’t the most optimal, and in this tough job market, you have to give the most optimal and be a near-perfect candidate to receive an offer. The interview process is no longer about “working with a coworker” or “demonstrating your thought process and problem solving skills”, the interview process is purely: can they implement the most efficient solution to this leetcode medium question in 30 minutes or less?
Those are 💩 interviews if they only care about the optimal solution. Plenty of companies like that but if you’re from Google you should know good companies with good interview practices and checks and balances ask progressive questions that have changing requirements. You can pass those without finishing and the process actually is important.
I see you interviewed at roblox 😂
Zoox asks this in their OA as well.
This is from a OpenAI GPT - how accurate is the solution ?? To solve this problem, we can simulate the process of each frog croaking by keeping track of the number of 'c', 'r', 'o', 'a', and 'k' characters we have encountered in the string. We can use a counting method to ensure the sequence of the characters follows the order of "croak". If we encounter a character out of order, it means the string is not a valid combination of "croak", and we should return -1. Here's a step-by-step approach: 1. Initialize counters for each character in "croak" to 0. These counters will keep track of how many of each character we have seen so far. 2. Initialize a variable `frogs` to 0, which will track the maximum number of frogs croaking at the same time (which is the answer we're looking for). 3. Iterate over each character in the input string `croakOfFrogs`. - When we see a 'c', increment the 'c' counter. This could potentially start a new "croak", so we also check if we need to increment `frogs`. - For 'r', 'o', 'a', check if there are enough previous characters ('c' for 'r', 'r' for 'o', 'o' for 'a') to continue a valid "croak". If not, return -1. Otherwise, increment the counter for the current character and decrement the counter for the previous character. - For 'k', check if there are enough 'a' characters. If not, return -1. Otherwise, decrement the 'a' counter. This completes a "croak", so we can potentially decrement `frogs`. 4. After processing the entire string, check if all counters except for 'c' are back to 0, ensuring all "croak" sequences are completed. If not, return -1. 5. Return the value of `frogs`, which represents the minimum number of different frogs needed. Let's implement this logic in code to find the solution. The function produced the following results for the given examples: - For "croakcroak", the output is 1, indicating that only one frog is needed, which matches the expected output. - For "crcoakroak", the output is 1, which does not match the expected output of 2. This suggests there's an issue in the logic that tracks the maximum number of frogs needed. It appears that the decrement of `frogs` when a "croak" is completed is missing, leading to an underestimation of the number of frogs. - For "croakcrook", the output is -1, which is correct as the string is not a valid combination of "croak" from different frogs. To address the issue with the second example, let's refine the logic to correctly track the number of frogs. We need to ensure that `frogs` correctly reflects the maximum number of concurrent "croak" sequences. We'll adjust the logic to only increment `frogs` when a new 'c' character starts a "croak" that cannot be attributed to an existing frog finishing a previous "croak". This adjustment should provide the correct count for the second example. Let's implement this correction and retest the examples. With the corrected logic, the function now produces the expected results for the given examples: - For "croakcroak", the output is 1, indicating that only one frog is needed to finish all the croaks, which is correct. - For "crcoakroak", the output is 2, which matches the expected outcome. This suggests that the minimum number of frogs needed is indeed two, as the croaks overlap in a way that requires two frogs to complete them sequentially. - For "croakcrook", the output remains -1, correctly indicating that the given string is not a valid combination of "croak" from different frogs. This solution efficiently tracks the sequence of croaks and determines the minimum number of frogs needed by ensuring the characters appear in the correct order and accounting for overlapping croaks.
git gud nerd 😺
I never needed to have the most efficient solution to pass anything Just needed to show that I was very thoughtful analytical and considerate People who overindex on solving come off as non-collaborative since they can't explain their thought process or show collaboration skills But you'll probably pass with certain rote "book smart" interviewers I won't name
Literally getting an offer now for solving two problems optimally (because I had seen them before).
I read the question and came up with the solution using queue but realized that just 2 counters are works since it doesn’t matter which frog a croak belong to. It took be more than 15-20 mins to get to the optimal. I guess it is too slow for the current market if you add the coding time to it.
Tech Industry
Yesterday
3003
What happens when most of your team is Indian?
Tech Industry
Yesterday
1693
Women, help me understand why this is inspirational
2024 Presidential Election
Yesterday
346
Trump and his projections
Health & Wellness
Yesterday
626
Lasik cost
India
2h
239
'Hindutva': The Radical Hindu Ideology That Seeks to 'Push Christianity Out of India’
I mean…I don’t ask this kind of trick question. I ask a more implementation question and see how they reason it.