I applied through a recruiter. The process took 3 days. I interviewed at Spotify (New York, NY) in Sept 2011
Interview
Started off taking a programming test which was very open-ended. I passed that test and was interviewed by their VP of technology over the phone.
After the phone interview and after the team examined my code I as brought in for a 4 hour in-person interview.
You interview with 4 people - each playing different roles within the organization (analytics, web development, backend development, etc).
First couple of interviews were pretty straightforward. Everyone asks you how you would solve common problems they face (scalability, big data, ad hoc querying from billions of records, etc). The last interview was more academic (and ultimately were I failed). It focused entirely on algorithm analysis, sorting, process, heaps, etc.
A little disappointing but overall a great experience. REALLY nice people, great environment... would literally kill to work there.
Interview questions [1]
Question 1
You have 1000 computers. Each computer contains a text file containing 1 billion floating point numbers. Design an algorithm or algorithms for extracting the top 1000 numbers from the entire list. Describe in detail how long it would take to process and why.