Amazon Software Development Engineer interview questions

As far as I remember, I had following questions. Write a function to implement Huffman encoding. Several principle of OOP in Java such as abstract vs interface, what is static function, how built-in java sorting implemented, etc. Reverse a singly lined list. Nearest ancestor node of binary tree. Write a function to shift array and the follow up was to analysis the possibility of each element got shifted. The last one was like, give you a function which is written in O(n^2), you need to figure out what is it doing for and try to use dynamic programming to optimize it. It is one in LeetCode.