Ch 1 : Arrays & Strings

Question 1

Overview:

Some important

Data Structures

and

Techniques

for manipulating

Arrays and Strings

Answer 1

• Hash Tables
• ArrayList and Resizeable Arrays
• String Builder
• Concatenation

Question 2

What is a

Hash Table?

Answer 2

A data structure that maps keys to values for highly efficient lookup.

There are a number of ways of implementing this.

Question 3

Hash Table:

Common Implementation

Answer 3

Components:

• Array of Linked Lists
• Hash Function
• Key Value Pairs stored in the Linked Lists

Insertion:

• Given a Key, Hash Function produces Hash Code which is an index in the array
• The Value to be stored is placed in the Linked List at that index

Retrieval:

• Given a Key, Calculate Hash Code from Key
• Search for Key in Linked List and return associated Value

Question 4

Hash Tables:

The most basic common Hash Function

Answer 4

Hash Code

=

Key % array_length

Question 5

Hash Tables:
Two Simple Implementation Approaches and their Access Time

Answer 5

1. Array of Linked Lists with Hash Function,
   Access Time: O(n)
2. Balanced Binary Search Tree
   Access Time O(log n)

Question 6

Hash Table:

Benefits of Balanced Binary Search Tree

Implementation

Answer 6

• Lookup time is O(log N)
• Uses less space compared to allocating a large array
• Can iterate through the keys in order, which can be useful sometimes

Question 7

Hash Table:

Complexity Analysis

Answer 7

If number of collisions is high,

Worst Case Runtime is O(N), where N is the number of Keys

If Keys are distributed well by the Hash Function and size of array,

Lookup Runtime is O(1)

If implementation uses a balanced Binary Search Tree, less space is used for the array and Lookup Runtime is O(log N)

Question 8

Arrays vs Lists

Answer 8

In some languages, arrays are automatically resized to accomodate new elements.

These are often called “Lists” rather than “Arrays”, or “Resizeable Arrays”

Question 9

What is an

ArrayList

Answer 9

An array-like data structure

that offers dynamic resizing.

It resizes itself as needed,

while maintaining O(1) access time.

Question 10

ArrayList

Common Implementation

and

Complexity

Answer 10

Maintains an normal array of elements

When the array is full, copies elements into an array twice the size.

Access/Insertion time is O(1) just like a normal array.

Doubling takes O(N), but happens so rarely that this time can be Amortized so insertion time is still O(1) overall.

Different Implementations may use a different “Sizing Factor” than 2.

Question 11

What is a

StringBuilder

Answer 11

A Data Structure that efficiently concatenates multiple strings

by placing them all in a resizeable array until the final string is needed.

Question 12

String Concatenation:

Normal Concatenation

vs

String Builder

Answer 12

Normal Concatenation:

• A new String object is created
• Both of the old String Objects are copied over
• A new string is created for every copy operation
• If all strings are of length X:
  
  • O( x + 2x + . . . + nx) = O(xn²). = O(n²)

String Builder

• Adds strings to a resizeable array of strings
• when toString() called, creates one new string and copies all the strings it has stored to it.
  
  • O(xn) = O(n)

Question 13

Arrays and Strings:

Common Types of Questions (9)

Answer 13

• Unique
• Check Permutation
• Palindrome Permutation
• Insert/Replace
• Number of Edits(“One Away”)
• String Compression
• Matrix Rotation
• Zero Matrix
• String Rotation