My Cambridge interview – stay, questions and much more

About 3 months ago I had the opportunity to be interviewed for the University of Cambridge. Though I have not received an offer, I would like to depict my experience and give some advice to future Cambridge applicants.

Intro
I applied for a CompSci major at Christ’s College. Myself, I think that his was my first mistake regarding my application. I have decided to apply to Cambridge on a whim and I have not embarked on a research to select which the most appropriate college. I should have carefully examined all the colleges. My mistake was that Christ’s College is one of the small colleges. There are about 15 CompSci candidates a year and they pick only one or two. Although the chance for every college is about the same, it is more suitable to select a college in which the enrolled students are roughly 60-70 or more.

The travel
There was a storm on the day before my interview and I almost missed my flight. I landed safely in London on the 5th of December. Basically, I caught the bus for St Pancras, got me some food and caught the train for Cambridge from King’s Cross. It took me about an hour to get to Cambridge. The people were exceptionally friendly – I met a priest (as funny as it may seem) who helped me reach Christ’s College. Because I had been a little early, I had to wait for about two hours in the nearby coffee (EAT.). All applicants were irritated because the rooms were quite cold despite the heating. All of the other candidates were nervous due to the imminent interviews – I guess studying in Cambridge could be really important for some people.

The interview
I had two interviews – one in Mathematics and one in Computer Science. I was asked two questions during my Maths interview. Before the questions, he introduced himself and told me not worry if I make some mistakes. The interview went for about 20 minutes. The problems were:
1) Draw me the graph of y^2 – x^2 = -1 . This includes the graphic, asymptotes, and etc. Next I had to talk a little about for a more general case y^2 – x^2 = a where a is a constant. I did a few mistakes but the interviewer gave me the opportunity to correct myself. They know that it is stressful to be in a foreign environment.
2) Given a set of n elements, what is the count of subsets we can derive from the initial set. Again I made a few mistakes, but I managed to correct myself and tackle the problem. After you tell him the answer, which is (2^n), you will have to prove it. You will have to mathematical induction.
Next was the CompSci interview. I had an one-hour break. This time there were two interviewers. They introduced themselves and asked me some introductory questions:
1) Why do I want to study Computer Science?
2) How do I see myself in 5 years?
Next, the main questions followed:
1) You have a set of users and their passwords in a file (handles me a paper with examples). What is the problem? Do you see something which is not right? What would you correct?
The list contained something like:
george 123456
sam qwerty

First I talked about keeping the information in a database, because it is easier to handle the info and it is more secure. Then I mentioned hashing the passwords using md5, sha1 + salt. I guess I had to tell them about setting an appropriate id for every user so that we could search for a user in O(1) given by its index.
2) How would you hack the website?
I told him about a brute force attempt. The interviewer was obviously not familiar what brute force means, so I had to explain to him. We had a little talk and proved him wrong – he was like “Yeah, that’s right”.
3) You have a set of 1000 cards. How would you sort them?
I told him about using quicksort (fast, but harder to code) or bubblesort (slow, but easier to code). He laughed that I would use quicksort for sorting a deck of cards (yeah, it would seem funny using this algorithm in a real life scenario). He told me to explain bubblesort and to calculate the number of comparisons and swaps of cards. Then he told me to explain insertsort. I wold him about using binary search to find the appropriate place for the card in ordered set of cards. He again told me to tell the number of swaps and comparisons.
Basically, this was pretty much everything. I really thought I had aced the interviews, but unfortunately I was rejected.

My advice: I felt in love with Cambridge the moment I visited the city. It is really nice, the people are cool and friendly and London is just an hour away from Cambridge. If you are given the opportunity to study there, unless you have offers from the Ivy League or other cool universities in the U.S., you should definitely enroll.

If you have any questions, I would be more than honored to answer them. : )

C++ implementation of an AVL tree

A simple implementation of an AVL tree:

#include 
using namespace std;
#define MAX 10000

struct binary_tree {
    binary_tree * parent;
    binary_tree * left;
    binary_tree * right;
    int value;
    int index;
};

binary_tree * root = NULL;
binary_tree * nil;
int h[MAX]; // keep values for the heights of the sub trees
int tree_size;

void init_tree() {
    nil = new binary_tree[1];
    nil->left = nil->right = nil->parent = NULL;
    nil->index = 0;
    root = nil;
    tree_size = 0;
}

// does a single left rotation
void left_rotate(binary_tree * x) {
    binary_tree * y = x->right;
    x->right = y->left;
    if (y->left != nil) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nil) {
        root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

// does a single right rotation
void right_rotate(binary_tree * x) {
    binary_tree * y = x->left;
    x->left = y->right;
    if (y->right != nil) {
        y->right->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nil) {
        root = y;
    } else if (x == x->parent->right) {
        x->parent->right = y;
    } else {
        x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
}

// returns the height of the subtree with root x
int height(binary_tree * x) {
    if (x == nil) return 0;
    return max(height(x->left),height(x->right))+1;
}

// balances the tree after insert from leaves to the root
// currently you could observe that there is a problem in this code:
// we traverse the tree and begin balacing from every leaf when that's not actually neeeded
// instead we could keep a reference to the leaf node we have added and balance the tree upwards. The author leaves this to the reader
void balance(binary_tree * x) {
    if (x == nil) return;
    balance(x->left);
    balance(x->right);
    int h1 = height(x->left);
    h[x->left->index] = h1;
    int h2 = height(x->right);
    h[x->right->index] = h2;
    if (h1 - h2 == 2) {
        int lh = h[x->left->left->index];
        int rh = h[x->left->right->index];
        if (lh-rh == 1) {
            right_rotate(x);
        } else {
            // zig zag case
            left_rotate(x->left);
            right_rotate(x);
        }
    } else if (h1 - h2 == -2) {
        int lh = h[x->right->left->index];
        int rh = h[x->right->right->index];
        if (lh-rh == -1) {
            left_rotate(x);
        } else {
            // zig zag case
            right_rotate(x->right);
            left_rotate(x);
        }
    }
}

void add_to_binary_tree(int a) {
    binary_tree * x = root;
    binary_tree * y = nil;
    binary_tree * z = new binary_tree[1];
    z->value = a;
    z->left = z->right = nil;
    z->index = ++tree_size;
    while (x != nil) {
        y = x;
        if (z->value < x->value) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == nil) {
        root = z;
    } else if(z->value < y->value) {
        y->left = z;
    } else {
        y->right = z;
    }
    balance(root);
}

// in-order print
void print(binary_tree * el, int i) {
    cout < < el->value < < " " << ++i << endl;
    if (el->left != nil) print(el->left,i);
    if (el->right != nil) print(el->right,i);
}

binary_tree * search(int x) {
    binary_tree * temp = new binary_tree[1];
    temp = root;
    while (true) {
        if (temp == nil) {
            return nil;
        }
        if (temp->value == x) {
            return temp;
        }
        if (temp->value < x) {
            temp = temp->right;
            continue;
        }
        if(temp->value > x) {
            temp = temp->left;
            continue;
        }
    }
}

void transplant(binary_tree * node1, binary_tree * node2) {
    if (node1->parent == nil) {
        root = node2;
    } else if (node1->parent->left == node1) {
        node1->parent->left = node2;
    } else {
        node1->parent->right = node2;
    }
    node2->parent = node1->parent;
}

binary_tree * minimum(binary_tree * node) {
    while (node->left != nil) node = node->left;
    return node;
}

void delete_balance(binary_tree * x) {
    int h1 = height(x->left);
    h[x->left->index] = h1;
    int h2 = height(x->right);
    h[x->right->index] = h2;

    if (h1-h2 == 2) {
        if (h[x->left->left->index]-h[x->left->right->index] == -1) {
            // zig zag cas
            left_rotate(x->left);
        }
        right_rotate(x);
    } else if (h1-h2 == -2) {
        if (h[x->right->left->index]-h[x->right->right->index] == 1) {
            // zig zag case
            right_rotate(x->right);
        }
        left_rotate(x);
    }
    if (x == root) return;
    delete_balance(x->parent);
}

void delete_from_binary_tree(int val) {
    binary_tree * x = new binary_tree[1];
    binary_tree * y = new binary_tree[1];
    binary_tree * q = new binary_tree[1];
    x = search(val);
    if (x == nil) {
        cout < < "NOT FOUND" << endl;
        return;
    }
    q = x;
    if (x->left == nil) {
        transplant(x,x->right);
    } else if (x->right == nil) {
        transplant(x,x->left);
    } else {
        y = minimum(x->right);
        if (y->parent != x) {
            transplant(y,y->right);
            y->right = x->right;
            y->right->parent = y;
        }
        transplant(x,y);
        y->left = x->left;
        y->left->parent = y;
    }
    delete_balance(q);
}

int main() {
    int n,a;
    init_tree();
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        add_to_binary_tree(a);
    }
    delete_from_binary_tree(0);
    delete_from_binary_tree(-5);
    delete_from_binary_tree(100);
    delete_from_binary_tree(150);
    print(root,0);

}

/*
10
10 5 7 0 -5 6 100 70 125 150
*/