Amazon Software Development Engineer Intern interview questions

Applied online and got invited for phone interviews. There were 2 bak-to-back technical phone interviews, each for 45 mins. The questions were very technical, mostly problems that require you to write out some classes and develop some algorithms. There were a couple "which data structure is best for this". One of the interviewers ask me to write a naive approach and write 2 other versions that improve the performance. They also asked for performance of your algorithm.