Pregunta de entrevista de Meta
Design an enumerator (e.g. named FBSuperEnumerator) that has two API's:
- (id) nextObject;
- (NSArray *) allObjects; // all objects remaining
which, when given an input array that has content that can be either NSNumbers or NSArray, will expand all arrays embedded inside it.
That is, given an input of something like @[@1, @[@2, @[@3, @4]], @[ ], @5], each call to nextObject will display items in the expected order.
Respuestas de entrevistas
The implementation I’m copying down below isn’t perfect — and is the reason Facebook decided to not move forward with me. :-( I’ll explain why after the code.
This version keeps track of the current object as a property value:
@interface FBSuperEnumerator
@property int currentIndex = 0
@property id currentObj;
@property NSArray *list;
@property FBSuperEnumerator *fbse;
@end
@implementation
-(id) nextObject
{
id nextObject = [list objectAtIndex: currentIndex];
if [nextObject isKindOf: [NSArray class]]
{
top:
if self.fbse
{
id objectToReturn = fbse.nextObject;
if objectToReturn != nil
{
return objectToReturn;
} else {
self.fbse = [FBSE newWithArray: nextObject];
objectToReturn = self.fbse.nextObject;
if objectToReturn == nil
{
if curIndex+1 >= list.count
return nil;
else {
curIndex++;
goto top;
}
}
}
} else {
if curIndex+1 >= list.count
return nil;
else
return nextObject;
}
}
if [nextObject isKindOf: [NSNumber class]]
{
return nextObject;
}
}
@end
This is the one interview question/session the recruiter told me I goofed up. Primarily because I used the awkward (and apparently forbidden) C keywords word “goto:” (and I had offered to quickly scribble a refactor on the whiteboard to the interviewer, but we were running short of time).
I also suspect another reason was because I could have used NSEnumerator instead of maintaining my own current index & current object states.
Fairly straightforward solution in Swift using recursion. Basically keep a 'stack' (in the form of an array) of 'sub' enumerators mapped to how many levels deep the array is and utilize that to pop off the integers.
class FBEnumerator: NSEnumerator {
private var _subenumerators: [NSEnumerator]
init(objects: NSArray) {
_subenumerators = [objects.objectEnumerator()]
}
override func nextObject() -> Any? {
guard let currentEnumerator = _subenumerators.last else { return nil }
guard let currentObject = currentEnumerator.nextObject() else {
_subenumerators.removeLast()
return nextObject()
}
if let array = currentObject as? NSArray {
_subenumerators.append(array.objectEnumerator())
return nextObject()
}
return currentObject as? Int
}
override var allObjects: [Any] {
var temp: [Any] = []
while let obj = nextObject() {
temp.append(obj)
}
return temp
}
}
@interface FBEnumerator : NSObject
@property (nonatomic) NSArray *internalArray;
@property (nonatomic) NSMutableArray *enumerators;
- (id)nextObject;
- (NSArray *)allObjects;
@end
@implementation FBEnumerator
//@[@1, @[@2, @[@3, @4]], @[ ], @5]
- (instancetype)initWithArray:(NSArray *)array
{
if (self = [super init])
{
self.internalArray = array;
self.enumerators = [NSMutableArray array];
[self.enumerators addObject:[array objectEnumerator]];
}
return self;
}
- (id)nextObject
{
NSEnumerator *lastEnumerator = [self.enumerators lastObject];
id object = [lastEnumerator nextObject];
if (!object)
{
[self.enumerators removeObject:lastEnumerator];
return [self nextObject];
}
else
{
if ([object isKindOfClass:[NSNumber class]])
{
return object;
}
else if ([object isKindOfClass:[NSArray class]])
{
[self.enumerators addObject:[object objectEnumerator]];
return [self nextObject];
}
}
return nil;
}
- (NSArray *)allObjects
{
NSMutableArray *allObjects = [NSMutableArray array];
while (self.enumerators.count > 0)
{
NSEnumerator *lastEnum = [self.enumerators lastObject];
NSMutableArray *objects = nil;
[self getAllObjectsInEnumerator:lastEnum intoArray:&objects];
[allObjects addObjectsFromArray:objects];
[self.enumerators removeObject:lastEnum];
}
return allObjects;
}
- (void)getAllObjectsInEnumerator:(NSEnumerator *)enumerator intoArray:(NSMutableArray **)array
{
if (*array == nil)
{
*array = [NSMutableArray array];
}
NSArray *objects = [enumerator allObjects];
for (id object in objects)
{
if ([object isKindOfClass:[NSNumber class]])
{
[*array addObject:object];
}
else if ([object isKindOfClass:[NSArray class]])
{
[self getAllObjectsInEnumerator:[object objectEnumerator] intoArray:array];
}
}
}
@end