Arrays and Strings

Question 1

Hash Table

Answer 1

Maps keys to values for highly efficient lookup. A key is assigned a (not necessarily unique) hash code. The hash code is mapped to an index in an array with a hash function. Two hashes may map to the same index. At the index, a linked list stores key and value pairs to avoid collisions.

Question 2

Hash Table Collisions

Answer 2

Collisions may occur b/c keys share the same hash code or hash codes map to the same index. Since each index comtains a linked list, simply traverse the list until the key is found. Worst case run time is O(N), but O(1) is assumed.

Question 3

How do arrays and lists differ?

Answer 3

Arrays typically contain a static length. Lists typically have a dynamically changing size.

Question 4

What is the sum of 1 + 2 + … n?

Answer 4

If n is even, you can sum two elelemtns in the summation to produce n+1, n/2 times. If n is odd, you can add 0 to the summation, and sum two elements in the summation to produce n, (n+1)/2 tomes. This gives a total of (n+1)*n/2 for both cases.

Question 5

StringBuilder

Answer 5

A resizable array of strings. Can be converted into a string. Greatly reduces time complexity for string concatenation.