Java Interview

1 Arrays and strings

HashMap

Key -> Hashcode -> array of linked list->in case of collisions

Resizeable arrays

The array copied itself to a new array each time, let's say doubling its origin size to get a new size array. Even with resizing, the amortized insertion is still of O(1) time complexity. Proof: Given a array of size N, the total number of copies to insert N elements is roughly: $$N/2+N/4+N/8+...+2+1 < N$$

StringBuilder

Assume all strings have the same length (x), there are n strings, and the time complexity of concatenating a list of strings would be: $$O(x)+O(2x)+O(3x) + .. + O(nx) = O(xn^2)$$ But if using a StringBuilder which is implemented by arraylist, the time complexity ccan achieve O(n) as well.

If thread safe is a problem, then use StringBuffer.

2 Linked Lists

Delete from node is easier than ArrayList

3 Stacks and Queues

Stacks: Last-in first-out, implemented by a LinkedList. Queue: First-in first-out, implemented by a LinkedList-> Breadth-frist search or a cache.

4. Trees and Graphs

Type of Trees

Tree: May have various number of children Binary Tree: Only have max two children Binary Search Tree: Left descendents are less than or equal to the current node, which is less than the right descendents. Complete binary Trees: A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right. Full Binary Tree: No nodes have only one child. Perfect Binary Trees: A perfect binary tree is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.

Balanced vs. Unbalanced

AVL tree and red-black tree

Binary Tree Traversal

In-Order Traversal: left-> Current-> Right Pre-Order Traversal: Current -> Left -> Right Post-Order Traversal: Left -> Right -> Current

Binary Heaps (Min-Heaps or Max-Heaps)

Min-heap: A complete binary tree where each node is smaller than its children.

Insert

Extract Min Element

Tries(PrefixTrees)

Store Englush language words to check if the string is valid word.

Graphs

Java Knowledges

Private Constructor: In terms of inheritance, what is the effect of keeping a constructor private? Hints: #404

Return from Finally: In Java, does the finally block get executed if we insert a return state- ment inside the try block ofa try-catch-finally? Hints: #409

Final,etc.:What is the difference between final, finally, and finalize? Hints: #412

Generics vs. Templates: Explain the difference between templates in C++ and generics in Java. Hints: #4 16, #425

Object Reflection: Explain what object reflection is in Java and why it is useful. Hints: #435

Lambda Expressions: There is a class Country that has methods getContinentO and getPopulationO.Writeafunction int getPopulation(List countries, String continent) that computes the total population of a given continent, given a list of all countries and the name o f a continent. Hints: #448, #461, #464

Lambda Random: Using Lambda expressions, write a function List getRandomSubset(List list) that returns arandom subset ofarbitrary size. All subsets (including the empty set) should be equally likely to be chosen. Hints: #443, #450, #457