Follow-up interview question
I got this question in onsite round at a startup. I could solve the initial question but was clueless on the follow-up. Question: Given an input number develop the api checkValid(int num) to check if it is valid or not. A number is valid if none of its digits are four dimensional neighbors on a mobile keypad. Example: 145 is invalid. 159, 286 and 642 are valid. Follow-Up: Now the checkValid(String num) api starts getting millions of queries. How do you handle incoming queries if the api has to run on a single core machine. You can only run the api on a single machine. Interviewer specifically mentioned he is not interested in threading. I have no idea how to tackle follow-up. Can anyone please share me what should be the thought process for such questions. NOTE: follow up question takes input as string TC: 170k
Can you create all the valid combinations and cache the data in a set? At the request time, you just need to find if the given number belongs to the set or not. No need for computations at the runtime, and no need for multi core machine.
Maybe precompute all valid inputs? I think the total number is small and you can compute all valid inputs using backtracking so your memory space and initial time cost isn’t that high. From there, it’d be just checking to see if the input is in the precomputed cache. Perhaps you can go into solutions things like queuing, processing the inputs in batches, etc...
Sorry but what is the solution for the actual problem? Do you simply check if the difference between the digits is equal?
If the input size is 3 and 0 isn't a starting digit then there can only be 900 numbers possible we can precompute them and store it in a set and just look up.
Agree, this problem is too simple if the range is just [0-1000) lmao
Caching and other suggestions make sense, but I think you can probably frame this problem as an XOR masking problem. That framing would make any solution optimal for millions of computations in a single threaded task. But what's the range of the input? 0 - 2^32-1? 0 - 2^64 -1? Just three digits? Idk, these are just my hunches.
I forgot to mention this, but for the follow up checkValid input is of type string. I didnt ask the interviewer how many char long can the input string be, but since its a string it can be arbitrarily long is what I am assumed.
I was thinking masking as well. Each digit gets a %, shift and bitwise comparison against an array lookup, and /. Pretty economical. Probably not a problem for an xGHz processor to do millions per second. Billions per second, you gotta work on architecture.
the number of valid combinations is very limited. And the domain of the problem looks like phone numbers so we can assume 10 digits max and the area codes makes the search space even smaller. I would try to precompute and cache the result.( you can precompute this in parallel in a very short time if the same restriction does not apply) If allowed you can put this service behind a cdn since the results are static.
Don't reveal the right answer, just to show off. Let the 170k guy put some sweat
Rate limiter, cache