Avery had gotten his PhD from CCRMA at Stanford under Julius O Smith. His PhD had been on the topic of automatically ("blind") recovery of individual vocal/instrument tracks from a final mix. From there he joined a startup, Chromatic Research, where I was also at. He created lots of code and patented some algorithms related to resampling and MIDI synthesis, stuff like that. Avery was (and is) a super nice guy, humble but incredibly smart -- he could work not only with the high level mathematics but was also equally excited to fine tune assembly code.
After Chromatic folded, Avery had been struggling to get his own startup off the ground. About the same time, the Shazam guys had the idea for the product but didn't know how to create the algorithm. They approached Smith at CCRMA looking for someone capable of creating something that worked. Smith suggested they try Avery Wang.
At first Avery said, "Hmm, that seems difficult, but let me think about it." Within a week he had a demo running on a few thousand songs he had gathered from CDs. I'm sure a lot of refinements went into it after that, but the core idea took him a weekend.
[ All factual mistakes above are due to me and 20 year old memories -- if I misrepresented something it certainly wasn't due to Avery telling me something that wasn't true ]
EDIT: A blurb about Avery https://www.seti.org/avery-wang