Pergunta de entrevista da empresa Justworks
Algorithm Question: Is the number range "saturated". I put the word saturated in quotes, because their definition is somewhat ambiguous, after prodding the interviewers, the number range can be fully saturated, over-saturated in certain ranges or under-saturated. Input is a list of arraylist of 2 integers (each pair represents a range) Input 1: [2,5 | 0,2 | 10,15 | 6,9] Output: Saturated (logically this is over saturated because number 2 occurs twice but not according to the interviewers, creating additional edge cases for your algorithm) Output for the above is, yes the range is "perfectly" saturated because it accounts for all numbers from 0-15. Trick: interviewers consider even though the number 2, which occurs twice to be ok and not over saturated. Input 2: [3,10 | 0,5 | 50,100] Output: "not saturated" ("over saturated", the overlap is more than one number) Note for above range, it is both over saturated and under saturated, but interviewers don't mention/care about this Input 3: [5,9 | 0,3] Output: not saturated
Respostas da entrevista
Sigiloso
- Iterate through the list of integer pairs, and for each range populate an arraylist position with "filled". - if the position is already filled, then the range is oversaturated so return (unless if it is first or last position of any input pair), refer to my 1st input example. After iteration check to see if any arraylist or vector position are not filled, if so then return not saturated. I proposed additional concepts to improve efficiency but one of the interviewers couldn't understand how you can do it in one pass or seemed to think you need to go through the newly created arraylist or vector after filling it. As you iterate, keep track of the smallest & largest number, this will allow you to keep track of the full range. int smallestSoFar; int biggestSoFar; Everytime you fill the arraylist or vector, keep a count, so you know exactly how many positions you "filled" so far. Note there are some edge cases you need consider when keeping this count, refer to input example 1. After iteration, do biggestSoFar-smallestSoFar and compare to your fillCount, if they are as expected then it is perfectly saturated, if not then undersaturated, and there is NO need to go through your arraylist to see if there are any unfilled positions. Funny how one of the interviewers didn't grasp the concept of fillCount, to be fair 2nd interviewer did grasp it and went on to explain to the 1st how I was right. Also, the range can be negative or positive integers, so you will have to implement an "offset"