Sorting O(n): I thought that's impossible. Quick is nlogn, and it's the fastest one. Unless there's some sort of special case that allows for sorting in O(n), but I've never come across it.
Sorting SSNs: quicksort/merge sort/your favorite nlogn sort, up to a certain point, and at a theoretically optimal point, you switch to a low-overhead sort algorithm, such as insertion.
Well, there is actually a proof using an adversary argument that demonstrates it's impossible to beat O(nlogn) time in a
comparison sort. But let's say we're sorting something discrete, relatively compact, and manageable like 500 million out of 1 billion social security numbers (all integers). Is there a way to sort them faster without a comparison sort?
I can guarantee you that another programmer will be able to solve this problem in faster than O(n log n) time- although we have to abstract memory allocation as happening in O(n) time and reading integers as happening in O(c) time.
Sorting ups and downs: Merge and quicksort are very fast (nlogn) but are complex, recursive algorithms. For smaller data sets, it might be more efficient, at a certain point, to use a simpler algorithm with lower overhead, such as insertion sort.
Both quicksort and mergesort are divide-and-conquer sorts. What are the advantages and disadvantages of each relative to the other?
Fastest way to reverse a linked list: tabulate the node links in a square matrix, and then flip it along the long diagonal to map your new links. If we have a one way linked list, then this matrix would be a triangular one. If it is upper triangular, it then becomes lower triangular, and vice versa. Either way, this process runs in O(n^2).
You should be able to do this in O(n) time with one pass of the linked-list.
Merged linked lists: hmmm...I'd say a similar idea to the one above...make a square matrix of the nodes. This matrix can be subdivided into four sections...the links of the nodes of the first list with other nodes of the same list, the same for the second list, and the co-linkage between the two lists. If there is any link specified in either of those two co-linkage sub-matrices, the lists merge at at least one node, if I interpret the question correctly.
What do we know about the last node on each linked-list if they merge? What do we know about the two linked-lists if we know something about the last node?
Natural numbers: unfortunately, if you're talking about exactly any arbitrary number, then yes, this is NP complete, as it would require you to compare many different combinations and simply check if the numbers add up. This is an O(n^n) problem. If you could come close to this sum, you can at least use dynamic programming to use the complete knapsack algorithm, or a well-implemented integer program.
Think about the definition of subset-sum as an NP-complete problem again and whether the numbers are elements of a countable set or an uncountable set.
What if I told you there was an O(n*t) (where n is the number of elements and t is the target) solution to this for natural numbers? Can you think up an algorithm to solve this?
Bonus points: use this algorithm to give me an avg. case O(n*sqrt(2^t)) solution to the NP-complete subset-sum problem.
Crude algo: since we're talking about oil, I will assume it is a continuous quantity and therefore tell you to use the partial knapsack algorithm. In other words, refine whatever gives you the most bang for your buck until you can no longer make that substance, then repeat down the list.
I think that's correct. It's been a long-time since I've heard "knapsack algorithm" used in the context of optimization, but I think we're talking about the same algorithm.
Dr. Evil's Laser: that would be, if my third semester OR course memory serves me correctly, the max flow min cut algorithm.
You've definitely got the right idea. The name of the algorithm for determining min-cut, btw, is "Ford-Fulkerson".
Threading: I'm screwed here. Never have seen this topic. Makes me wish I have now.
It's not the end of the world but A LOT of financial programming jobs require a knowledge of threading. Just be sure to be up-front if you talk about threading.
Also, remember that nothing in CS is a clear-cut "you know the subject or you don't" If they ask you if you know a subject, just downplay downplay downplay, and say, "I've worked with some of that stuff, but I'm a stats major. If you've got a question, I'd like to take a shot."
Inheritance: My best answer is this--a subclass is an instance of the superclass as it stands. For instance, an object of class mountainBike is already an object of class Bike. So simply by definition of being an instance of a superclass must a subclass's functions have equal or greater access. (Though I may have missed the point here...the whole public protected private thing never hit home to me since I've never coded programs that anyone used besides me).
(Speaking in Java here, sorry if this isn't your favorite language) Let's say I try to override
public Bike.pedal(), with
private MountainBike.pedal(). What happens? Does the compiler reject this? If so, why?