There are two questions to demonstrate my confusion:
- LRU Cache
Design a data structure that when its instantiated it's given a capacity. Implement put and get methods with a key and value (similar to a dictionary) both in O(1). If it reaches capacity it removes the least used key. I thought to myself subclassing from an OrderedDict would be a good solution but I figured that would be "cheating". I toyed around with ways to maintain how my internal data structure would know which is the least used. Eventually I looked at the answer and sure enough it does exactly what I thought of and subclasses from an OrderedDict.
- Reverse Words in a String
Basically maintain the order of the words themselves but have the words reversed:
e.g "the sky is blue " -> "blue is the sky"
All the white space has to be removed save for a single space between words.
The answer using Python builtins I came up with is simple as:
split_s = s.split()
return " ".join(split_s[::-1])So where is the line for using built in data structures or functions/methods? I can understand that I could do more and reverse it myself in the second example but is split() too much? Should I loop through the characters and filter them then create the list myself? Again, where is the line?
What is an interviewer most likely wanting to see?