Maximum continous sequence profit

An interesting concept in Finance and Computer Science is if we have some historical data about the price of a security and we want to see the maximum profit we can make. (Assumption: we can only carry out one buy and one sell action)

Let’s assume that time is represented by natural numbers as opposed to timestamps. With this, we can represent the prices as an array and the index of the array representing the timestamp value (the lower values being earlier prices).

So given the array: [4.5, 6.0, 4.2, 4.4, 7.0, 3.2] the maximum profit we can make is 7.0 – 4.2 = 2.8

The solution may seem tricky as there are local sub-array problems that need to be solved, for example if we have gone through the first four elements of the array above, we can’t really say anything about the profit until we see more elements of the array.

The solution that I came up with had two variables and keeps track of the current maximum profit by continuous calculation and the minimum price value. This concept surprisingly leads to an elegant solution.

My solution (implemented in Python) is below, it’s got a complexity of O(n) – there has to be at least one element in the array.

[sourcecode language=”python”]

def max_profit(array):
profit = 0
min = array[0]
for i in array:
if i < min:
min = i
if (i – min > profit):
profit = (i – min)
return profit

[/sourcecode]

My final piece of homework

I just recently completed my degree at Imperial College London and my masters project was on ‘Performance Evaluation of Cloud Services’ (yes, I didn’t even know what this mean’t when I chose the project).

Essentially what I tried to accomplish was to look at the performance and cost implications of hosting cloud computing applications. My main focus was on Amazon EC2 instances (they are used by major internet companies like Instagram). I used a fancy mathematical topic called queuing theory to try and model requests to EC2 instances and I looked at the response times for these requests. They were database and web server requests.

If you are more interested in my work and conclusions reached have a look at my report on Github here.

The end of the password

Came up with this way of getting rid of the password entirely.

  1. Let your web app X allow people to log in by inputting their email address
  2. Send them an authentication link in their email address.
  3. Let people use this session link to log in.
  4. When they click on logout then destroy this session and start again from step 1

No where was a single password inputted.

Now, just need to write some libraries to implement this method of authentication. 🙂

Facebook Puzzles : Liar, Liar

I have been meaning to write this post for some time. I had some time on my hands last year and decided to try and solve the Facebook Puzzle Liar Liar (spec here). The solution was accepted by the Facebook Robot.

The first thing to realise is that (like most of these Computer Science related challenges) this problem can be translated into a graph traversal problem. We have 2 distinct groups of people, liars and truth tellers. The problem can be represented using a bipartite graph as truth tellers give the names of liars and vice versa.

So the first step of the solution is to go through the input specification and create a graph with each person connected to the list of people they are accusing. At the time of solving this problem my strongest language was Java, hence the solution is in Java as well.

I used a HashMap of Strings (people’s names) as the key and the value was a set of strings (accusers of the particular key).

When this is done, we can use breadth first search to traverse the graph (as the graph is fully connected) and we can create two sets, one of liars and one of truth tellers (we will never know which one is the liars though) and output the size of both.

The solution is here, feel free to send me feedback.