twitter phone interview questions

readme.md

Questions

1. Swap pairs of a linked list ( 1 -> 2 -> 3 -> 4 -> 5 to 2 -> 1 -> 4 -> 3 -> 5) Took me way too long, I think I got a correct solution in the end but my interviewer was NOT impressed

2. Given a 2D array, a start point, and end point, devise an algorithm to traverse from the start to end given that there are obstacles in the way. Assume you can only traverse up, down, left and right.

Totally screwed up on this. Approached it using a depth first search instead of a breadth first, didn't realize that either one was that (despite hearing about both before). Also, pseudo code is crap.

gistfile1.py

2 D grid. city blocks

. S .
x x .
. E .

start, end == (x ,y), (x, y)
int shortestPath(map, start, end) {
    Queue q = new Queue();
    Branch[] branches = getAllPossible(start);
    for(Branch b: branches) {
        q.push(b);
    }
    distances = []
    while (!q.isEmpty()) {
        Branch b = q.pop();
        if(end.in(getAllPossible(b.position)) {
            distances.append(b.distance)
        }
        for(Branch b: getAllPossible(b.position)) {
            q.push(b);
        }
        
    }
    return min(distances)
}

getAllPossible(start) {
    startx = start.x
    starty = start.y
    branches = []
    for(int i = -1; i<= 1; i++) {
        for(int j = -1; j <= 1; j++) {
               if(noObstacle(startx+i, starty+j) {
                  branches.append(branch(startx+i,starty+j);  
               }
        }
    }
    return branches;
}

Singly linked list.

1 -> 2 -> 3 -> 4 -> 5
 swap all the pairs in the list
 
 
2 -> 1 -> 4 -> 3 -> 5

class Node {
    public Node next;
    // No Data 
}

Node pairSwap(Node head) {
    Node temp = head; // 1
    Node prev = null;
    while(temp != null) {
        Node oldNext = temp.next; // 3
        temp.next = temp.next.next; // 1 -> 3 -> 5 
        oldNext.next = temp; // 2 -> 1 -> 3 -> 4 -> 5
        if (prev != null) {
            prev.next = oldNext;
        }
        prev = temp;
        temp = temp.next; //              4

    }
}

2-> 1 -> 3 -> 5
       4-^