It was a pretty basic interview. The Interviewer asked me to implement a basic dictionary in my chosen language. I chose Java and asked for more criteria, which he said he didn't care. I went with a basic double array data structure, which solved the problem. He then asked for the runtime (note: do not use the term linearithmic for nlgn, some people do not know what it means). Afterwards, he asked me if there was a data structure that had a O(c), which I didn't know of. He suggested Hash function (which is not an O(c), but a O(lgn) with an average run-time of O(c)). Finally, he asked questions about the nice program.