Online Test was administered to determine qualification of candidates. Test lasted one hour and had four questions. Questions are generally re-used and are as follows: 1)Bubble sort is O(n) at best, O(n^2) at worst, and its memory usage is O(1) . Merge sort is always O(n log n), but its memory usage is O(n). Explain which algorithm you would use to implement a function that takes an array of integers and returns the max integer in the collection, assuming that the length of the array is less than 1000. What if the array length is greater than 1000? For this I said that if an integer is four bytes and a 32 bit computer has 4GB ram, it could store about 1 billion integers. So, whether the array is on the heap or stack, if you assume there is 512MB available for the heap/stack, you could still store over 100 million integers. So, obviously merge is better for small input because it's faster and memory isn't a concern. And, for big input sizes, merge is orders of magnitude faster and the memory usage is a non issue for array sizes less than 100 million on a modern computer with a reasonable amount of RAM available. 2)You've always been intrigued with the Six Degrees of Kevin Bacon game. Now, let's say if two actors have been in the same movie we call them 'friends' and if two actors have not been in the same movie, we say they are not 'friends'. Now choose any two actors at random -- we want to calculate the number of degrees of separation and the path between them. How do you go about this problem? Discuss ideas, trade-offs, algorithm ideas, and more. So for this your using a un-directed graph. You could store it in an adjacency matrix or whatever. A friendship is an edge between two nodes. Say you start at one node and you want to find another - you have basically two options that I know of, breadth and depth first traversal. I went for breadth not depth because the name of the game basically states any two people are usually connected by no more than six degrees of separation (pretty well-agreed upon theory). So, starting at one node, the node I want to find is likely going to be pretty close by (6 is small) so the fastest way to find it is not to go deep first, its to spread myself out and check all the first degrees of separation, then all the seconds, etc.. Hoping that I can find it in <10 levels of iteration. I didn't touch on finding the shortest path (Dijkstra's algorithm) because the question never really brought that up. 3)Your best friend Betty thinks IMDB is too complicated and challenges you to create a simple movie web site. One page will display movies (with movie name, date it was released, and list of actors). Click on an actor and you're taken to the actor page (with actor name, birthday, bio, and list of movies actor has been in). Please outline the relational table structure of the database for this. I think this is what killed me here. I don't know anything about relational databases so I basically talked about what I would do if I was going to use object-oriented programming and classes. I said I would use encapsulation, meaning each movie would be a Movie object and all actors in a movie would be a data member of the Movie object (ie. each Movie object has Actor objects). I thought I did pretty good for not knowing anything... 4)If you roll 5 standard six-sided dice, what's the probability that you get at least three 2s? This is pretty easy if you know probability, you've got three cases (three 2's, four 2's, all five 2's) and for each case the probability of n two's is 5Cn * (1/6)^n * (5/6)^(5-n)