Amazon Software Engineer Test I interview questions

I applied online. Heard back in a month in early January, and had two 45-min back-to-back phone interviews in late January. The interviews are technical. But the first interviewer had a strong accent that I couldn't understand some problems and had to ask him to say them again. The first interview asked about my experience with Amazon.com, what I don't like and what I like. Then there were a couple of data structures problems on array, string and etc., regarding time complexity. Then he asked me to program online given a string, convert it to a number. Then test cases of the same problem. The second interview was about graph. Given two nodes in a large relationship graph like Facebook, find the shortest path from one to another.

I had one phone in interview. They called me and the interviewer had an accent so it was somewhat difficult to understand everything he was saying. He first asked me to tell him about some of the projects I did and which one I found most challenging. He then started with technical questions. Here are the ones that I can remember (I did the coding in Java): 1. Write code to reverse a linked list. Ex. null -> a -> b ->c ->d ->e. This should become null <-a <-b <-c <-d <-e 2. Write code to print out each node of a tree in level order and print a new line whenever a new level is to be printed. 3. Describe encapsulation and polymorphism. 4. What is the difference between a vector and arraylist? I was unprepared and did not have the mindset to answer the most basic object oriented questions.