3 ms·
I actually don't have an explicit set of core questions, but I'm sure there are clear themes that run through the problems. Probably my only real tip I can thi
by kenjackson 15y ago
I actually don't have an explicit set of core questions, but I'm sure there are clear themes that run through the problems.
Probably my only real tip I can think of is not to have them code something related to stuff you're currently working on. You'll be far more likely to underestimate how hard the problem is.
But the problems aren't that hard to think of. They're not like ACM programming contests. They're more like:
You have two lists. One is a list of IP addresses. The other list contains IP addresses or IP addresses with wildcards. E.g., 192.168.$.1 or $.255.255.255. Return the set of IP addresses from list 1 that are matched in list 2. Additionally return the index from list 2 that matched -- I want the index that is most specific (as defined by having the fewest wildcards, or wildcard furthest to the right when there is a tie).
- AdamTReineke 15y agoWould the optimal solution be O(n*log(m)), where n is the number of IP addresses in list one and m is the number of IP addresses in list 2?
- deleted 15y ago[deleted]
- kenjackson 15y agoI think O(n * 2^p) is also a possibility, where p is the number of slots in the address. For standard IP addresses p is 4. So for large m, this might be preferable. I'm basically just hashing values to get this. How do you get the log(m) factor?
- gordonguthrie 15y agoIf it is a long list then the O of the algorithm matters a lot. If its a short list, who cares? If you care about it all the time then you a premature optimiser - basically a hand-grenade with the pin out. (by you I mean 'one' here - not you AdamT)
- eru 15y agoIf you are implementing, than you are right. If you are interested in studying algorithms and how they work, asymptotic considerations can tell you a lot about the algorithm. You have to decide what you want to ask for in your interview.