Skip to content

Instantly share code, notes, and snippets.

@Zhangerr
Created March 4, 2015 05:45
Show Gist options
  • Save Zhangerr/5abfeafa027e881dddb2 to your computer and use it in GitHub Desktop.
Save Zhangerr/5abfeafa027e881dddb2 to your computer and use it in GitHub Desktop.
twitter phone interview questions

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.

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-^
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment