K nearest points to the origin on a 2D plane; one-pass reverse linked list with constant space.

Question

Michael Kristian Peterson · Accepted Answer

"one-pass   reverse linked list with constant space"

@interface Link : NSObject
@property(nonatomic) int value;
@property(nonatomic) Link *next;
- (Link*)reversedList;
@end


@implementation Link

- (Link*)reversedList {
    
    Link* head;
    
    Link *link = self;
    while (link) {
        
        // save reference to next link
        Link *next = link.next;

        // "insert" link at the head of the list
        link.next = head;
        head = link;

        // continue processing the rest of the list
        link = next;
    }
    
    return head;
}

@end

helloslz · Answer

The first one can be done using a java PriorityQueue, define a Point class that implements Comparable.
Put all the points to the PriorityQueue and poll the top k.

Kenneth · Answer

The first one can be done by sorting points by x^2 + y^2, the second one is the most common data structure question. Thanks for your sharing :)

Michael Peterson · Answer

"K nearest points to the origin on a 2D plane"
- I took this to mean "write an algorithm that figure out K closest coordinates to the origin (0, 0) of a 2D matrix.
- Assume origin is at top left.
- We want to fan out from the origin. Choosing coordinates in the order along X and Y in an order closest to origin.
- For example, for Row 2, Col 2 = (2,0), (0,2), (2,1), (1,2), (2,2)
- Example class in Objective-C:

@interface CloseToMatrixOrigin : NSObject
+ (void)printK:(int)k closestCoordinateToOriginOfMatrix:(NSArray*)matrix;
@end

@implementation CloseToMatrixOrigin

+ (void)printK:(int)k closestCoordinateToOriginOfMatrix:(NSArray*)matrix {

    int count = 0;
    
    for (int i = 0; i < [matrix count]; i++) {
        
        for (int j = 0; j <= i; j++) {
            
            int row;
            int col;
            
            if (j != i) {
                
                for (int toggle = 1; toggle <= 2; toggle++) {
                    
                    row = (toggle == 1) ? i : j;
                    col = (toggle == 1) ? j : i;
                    if (![CloseToMatrixOrigin printRow:row andCol:col forCount:++count andK:k]) {
                        return;
                    }
                }
                
            } else {
                
                row = col = i;
                if (![CloseToMatrixOrigin printRow:row andCol:col forCount:++count andK:k]) {
                    return;
                }
            }
        }
    }
}

+ (BOOL)printRow:(int)row andCol:(int)col forCount:(int)count andK:(int)k {
    
    NSLog(@"[%d, %d]", row, col);
    
    if (count == k) {
        return NO;
    }
    
    return YES;
}

@end

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas