Apple Interview Question
Backend DevelopersCountry: United States
Interview Type: Phone Interview
It is better to avoid writing a single line of code, when you can write it in 2 lines.
[ stackoverflow.com/questions/618378/select-unique-or-distinct-values-from-a-list-in-unix-shell-script ]
./yourscript_to_isolate_ip.sh | sort | uniq -u
and this, will run no matter how less memory you have.
Aws guys actually run it, so does azure folks. I am pretty sure Apple will do the same.
Looking for interview experience sharing and mentor?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Code),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution
For the first problem a hash set of {IPs} may simply solve it.
However in the follow-ups as the amount of data cumulates, if the IPs are stored as strings, 4GB is becomes absolutely insufficient, since there are over 4 billion IPs out there and each ip as a string takes at least 9 bytes.
Even if convert ip to integer(8B), it wouldn't be enough.
An approach is to go with bit set. Then each ip takes only 1 bit. Have a bit set to store whether an ip occurs and another set to store whether an ip repeats.
This takes 2 * 2^32 bit = ~1GB -> fits in RAM.
- aonecoding July 23, 2017