Interview Question
Country: United States
is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
I would use a bit vector to decode all problems for each patient. Each bit on the vector is assigned to one problem and will be '1' if the patient has the problem and '0' otherwise.
(lets call a bit vector of the patient Vpatient)
All bit vectors will be stored on a hash table, hash by a hash function on the patient id
When asked if the patient has any set of problems, we can compute the bit vector of these problems (lets call it Vproblems), then get Vpatient for the patient from the hash table and compute a bitwise AND over both of them:
Vmatch has a '1' bit for each problem from the set that the patient has.
- davidglbr September 27, 2014To answer the question if a patient has 3 of more problems, simply check if there are 3 or more '1' bits on Vmatch.
Why is this an efficient representation:
1. The number of patients (n) if huge. Using hash table is an efficient way to store and retrieve items from large data sets in O(1) complexity.
2. Bit vectors are the most minimal way to store what problems every patient has, and enable bit-wise operations (the most efficient to perform by the CPU). It's also make sense because the number of problems (m) is not comparatively huge.
3. Security bonus - using the right hash func we can decode patient IDs and make it hard to know who is the patient for a given problem vector if the hash-table is hacked