Twitter API & Smartphone as your identity

At Twitter's Flight conference this week, they announced a couple of new toys for developers: Fabric and Digits.

Fabric is a new platform for building mobile apps

The Fabric platform is made of three modular kits that address some of the most common and pervasive challenges that all app developers face: stability, distribution, revenue and identity.

It seems everyone has to be building a platform these days, but really it sounds like Twitter, having previously shut down developers on their API/platform a while ago, realised that actually letting devs on their platform (now that it includes advertising APIs - thanks to their MoPub acquisiting a while ago) is going to be profitable for them.

Maybe it will be well received, and the way the market changes maybe people will go for it - but I wouldn't be building an app based around a Twitter platform given their track record.  The company are a lot older, and maturer now (and they probably released their API too early last time around), but it still seems like quite a risk to have something as central as login/revenue tied to Twitter (I dont like third party logins anyway..).



Anyway, the much more interesting product they released was Digits - which allows sign-in with your mobile number - which as I have ranted before, is an idea that I love, and seems like a really smart move by Twitter. Both in as much that it will move twitter to that space of smartphone is your social-identity/network and also offers a lot more value than just another platform that serves ads and supports login etc.

Amazon & the circle of life

Last week, Amazon announced the planned opening of their first bricks & mortar store - planned to be opened in central New York, not far from Macy's department store. The move is an attempt to provide some of their customers with a traditional face-to-face customer service.

If you have been following other recent Amazon announcements and expansions, you will be familiar with their other recent moves:

Same day delivery - Amazon has been a dominant power in e-commerce for a long time, and given the small margins they operate, and being loss-leaders in some products to drive business elsewhere, it's going to be difficult for any newcomer to genuinely compete, and as Amazon continue to spread more and more into all forms of goods, its also slowly making it harder for shops to operate in a specialist vertical.  However, there is always going to be times when convenience and the ability to have something immediately trumps price, so there was always going to be a market share that Amazon will loose. A lot of the time people will pay a small percentage increase in price for being able to have the product in their hands in a few hours.  Same day delivery will reduce that - again their will be the premium cost of the delivery service, but customers can have products instantly (almost).  There are some significant logistical challenges to do this, but being in a position to do this also opens up another opportunity..

Fresh groceries (having been doing non-perishable groceries for some time). One of the biggest challenges to Amazon rolling out fresh grocery deliveries more widely (currently only available to parts of North America) is building the capacity to enable fast, same day delivery of fresh goods; so the goods can leave a chilled warehouse and be with the customer in a short time - what is a short time exactly? It seems from existing supermarket delivery services that most people are happy with same day delivery (or at least fixed day delivery - e.g. the goods leave the warehouse on the same day they arrive to the customer), using refrigerator delivery vehicles, which seems simple enough for an individual case - in the UK Amazon could ship from their large Swansea warehouse in the morning and deliver the goods to most parts of the UK the same day. The inevitable problem becomes when this starts to scale up, As soon as even a small percentage of the UK want to order their weekly fresh groceries from Amazon the problem gets a lot tougher, and Amazon would need to have a large, distributed warehouse/delivery infrastructure to enable this kind of efficient, same day grocery deliveries.  The kind of infrastructure that existing supermarkets like Tesco or Sainsburys already have, having long built the infrastructure to provide a similar level of stock control and service to their supermarkets.


It's no secret that Amazon returns very little profit to their shareholders, and continues to plough the majority of their revenue into new business and further expansion - a large part of the investment going into expanding their delivery and warehouse capacity and distribution.

Scaling same day delivery is a hard problem to solve, if only because the solution is really just more distributed warehouses. Amazon have tried to ease the scaling problem with Amazon lockers and local partners/shops that can take delivery and can then be picked up from by the customer at a convenient time (a local shop that a customer can pick up their goods from on the way home from work for example), but really their move to bricks and mortar is really just another step to a long established industry.

Is Amazon really disrupting groceries/shopping? Or are they just competing against the usual retail giants?  Neither same/fixed day delivery or fresh grocery delivery is a new feature. Providing both online and physical stores is also not a new model, so really all we are seeing is another retail powerhouse slowly marching onwards and upwards to a fairly conventional business plan**, maybe the only thing of interest is that it is doing it in a different order (Tesco scaled from bricks and mortar, to online shopping, to same day delivery; Amazon are simply starting from online and expanding to the others).


So I guess we will need to wait for drone-delivery to see any real innovation in the retail space.



** Conventional business plan for the retail/groceries aspect of the business - there is still lots of innovation and interesting things that Amazon are doing, with mobile devices, could services, video delivery/production etc.

Graph data structures - Searching

Previously we looked at an introduction to graph data structures and designed a very basic Graph implementation.  I also mentioned that the main things we would likely want to do with a graph is search/explore the graph.


There are two primary tools that we will use to explore graphs - these are basic computer science concepts, and should be familiar to everyone who has studied computer science at uni and faced graphs before.

Depth First Search (DFS) 

The concept behinds DFS is that given a starting point or root node, we will
search as deep as we can one route before backtracking (e.g. select a neighbour to the root node, visit that neighbour, then select a neighbour from that node and visit - continue this until we reach a node that we cannot follow any more edges from, and then backtrack up the graph considering alternate neighbours at each step)

DFS is pretty simple to implement and nataurally uses a Stack data structure to keep track of the backtracking (the easiest way to do this is to solve recursively using the implicit Stack)

Below is a simple Java implementation of DFS using recursion to handle the backtracking.

Breadth First Search (BFS)

This search takes the different approach of looking as wide as possible before moving down a level. For example, we will visit all the immediate neighbours of the root, then select one of the immediate neighbours and visit their immediate neighbours - then backtrack up to visit other neighbours at this level.



(image also from wikipedia)



BFS is also fairly simple, and pretty close to DFS but it uses a Queue (FIFO) structure rather than a stack to visit nodes from the root down first.  Below is example code of BFS implemented in Java.

Graph data structures - An introduction

With most problems it is largely pretty clear which data structure is going to be appropriate to use - If you just care about storing a list and iterating over it, then you probably want an Array based structure - if you particularly care about the elements being unique you could look as a Set. If you want to capture a key-value pair dictionary data structure then you can use a Map.

Graph data structures are no different, and are very applicable to a subset of problems, and once familiar with graphs and the common algorithms it becomes quite easy to quickly identify the problem type as a graph problem.

The basics

A graph has two main elements:

• Node - a given data point in the graph
• Edge - a connection that joins any two Nodes. A graph can be "directed" or "un-directed" - this simply determines whether the Edge goes both ways or is purely one way. 

A graph is a data strucutre that stores a set of connected elements - the easiest way to understand the structure is with a real world example, the most famous is probably like the social-network graph. If you think about your profile on any popular social network (Facebook/LinkedIn/etc), your profile is a Node in the graph, and each of your friendship/connections is an Edge to another Node in the graph

A while ago, a Facebook intern created a visualisation of the Facebook social graph around the world - you can't really make out the individual Nodes/Edges, but you get the idea.


In Facebook's graph, it is un-directed, that is, when you become friends with another Node in the graph the relationship goes both ways - you are their friend and they are yours.

Twitter, however, is a directed graph - once you follow someone an Edge is created between your Node and theirs, but they don't automatically follow you as well, so the Edge has direction.


If you are a LinkedIn user, you may have noticed whilst browsing another user's profile a widget saying something like

"X of your connections can introduce you to someone who knows Y"

What LinkedIn is telling you, is that the shortest path between your Node and Y's Node in the graph is 3 Edges (3 "hops" - following an Edge between nodes is often called a "hop") - To be able to do this, LinkedIn is searching the social graph space to discover the shortest path (and number of unique paths that are of the shortest distance) between you and this other user.

Graph representations

There are two primary graph representations:

• Adjacency Matrix - This is a matrix/2-D array that captures the relationship between every node. Every node is mapped against the X and Y axis, and the value in the intersecting cell determine if their is an Edge between the nodes. E.g. if we wanted to know if there was an edge between Node "4" and node "13" we would look at matrix[4][13] - the value there would tell us. Normally, value of 1 represents an edge, but other values can be used (for example, if it is a weighted graph the values could represent the weights, or if it is a directed graph it could use -ve/+ve values to represent direction).  This representation is good for "dense" graphs.
• Adjacency List - This representation is simply a List of all Edges and a List of all Nodes. This is a simple representation and is more memory efficient for "sparse" graphs

For the code samples here, I will focus on the Adjacency List representation

Graph representation - Java

Below is a very rudimentary implementation of a Graph class in Java. It uses a Adjacency List representation and will be used in later examples I go through.


Below is a sample unit test setup that shows how a simple graph can be initialised:



In the next post I will go through basic techniques for searching and exploring graph spaces, as well as a post looking at how to solve the LinkedIn shortest path recommendation problem.

Quick Sort - A Java implementation

And now the same for a Quick Sort I implemented. Normally Quick Sort also runs in O(nlogn) time, but its worth noticing that the implementation below just uses the first element as the pivot value, which is not an optimal pivot (performs very badly in partially sorted lists for example), so will leave it to you to think about better ways to choose the pivot value.

MergeSort - A Java implementation

I wrote a Java implementation of Merge Sort a little while ago, just for fun really. I was just about to close the file, noticing it was still open in my IDE, and thought I might as well just post it here quickly. It might be interesting for someone along side the Merge Sort analysis I previously wrote up.