Exam 2 Rec Quizzes

Question 1

Which of the following methods of your Hash map class might require the resizing of the underlying array?

Answer 1

put

Question 2

Which of the following two implementations of the remove() method is more efficient?

a.
int hash = key.hashCode() & Integer.MAX_VALUE;
int index = hash % this.table.length;
Iterator<SimpleEntry<K, V» iter = this.table[index].iterator();
while (iter.hasNext()) {
SimpleEntry<K, V> entry = iter.next();
if (!entry.getKey().equals(key))
continue;
iter.remove();
this.size –;
return entry.getValue();
}
return null;

b.
for (int i=0; i<this.table.length; i++) {
Iterator<SimpleEntry<K, V» iter = this.table[i].iterator();
while (iter.hasNext()) {
SimpleEntry<K, V> entry = iter.next();
if (!entry.getKey().equals(key))
continue;
iter.remove();
this.size –;
return entry.getValue();
}
}
return null;

Both solutions are equally efficient

Answer 2

a

Question 3

Here are the key-value pairs stored in the hash map implemented according to the description in this recitation:
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
3:”a” 17:”b” 8:”c”
The keys are integers, the values are strings. The hash function used is hash(key) = key % 10.

According to the design of the put(key,value), what would be returned by the put(13,”n”)?

Answer 3

The put(13,”n”) will return null

Question 4

Consider the following implementation of the allStar problem from the recitation:

public static String allStar(String astring) {
if (astring.length() == 0)
return “”;
return astring.substring(0, 1) + ‘*’ + allStar(astring.substring(1));
}
This implementation has a bug. What is the nature of this bag?

Answer 4

One of base cases is missing

Question 5

This is a recursive solution that answers if the LinkedList t is sorted in the increasing order (low to high).

Which code snippet would you insert instead of ✴✴✴ to make it work correctly?

public static boolean isSorted (LinkedList<Integer> t) {
if (t.size() == 1)
return true;
✴✴✴
t.remove(0);</Integer>

return isSorted(t);
}

Answer 5

if (t.get(0) > t.get(1))
return false;

Question 6

Three different recursive implementations of the power(X, n) are presented below.

What is the big O of each implementation?

public static int A(int X, int N) {
if (N == 0)
return 1;
return X * A(X, N-1);
}

public static int B(int X, int N) {
if (N == 0)
return 1;
int res = B(X, N/2);
if (N % 2 == 0)
return res * res;
else
return X * res * res;
}

public static int C(int X, int N) {
if (N == 0)
return 1;
if (N % 2 == 0)
return C(X, N/2) * C(X, N/2);
else
return X * C(X, N/2) * C(X, N/2);
}

Answer 6

A: O(N), B:O(log N), C:O(N)

Question 7

Consider the solution below. What is the asymptotic running time of this solution in terms of the number of non-dirty elements m?

int findInDirtyArray(char [] A, char element) {
int m = 0;
while(A[m]!=’&’)
m++;
return binarySearch (A, element, 0, m);
}

Answer 7

O(m)

Question 8

The code below finds the first occurrence of a number in a sorted array. Unfortunately, it is not correct. The suspicious lines are listed in the answer. Which of them contain a bug? There are more than one.

1. static int getFirstIndex (int [] a, int element, int low, int high) {
2. if (low > high)
3. return 0;
4. int mid = (low + high)/2;
5. if (a[mid] == element) {
6. if (mid == 0)
7. return mid;
8. if (a[mid-1] == element)
9. return mid;
10. return getFirstIndex (a, element, low, mid-1) ;
11. }
12. if (element > a[mid])
13. return getFirstIndex (a, element, mid+1, high) ;
14. else
15. return getFirstIndex (a, element, low, mid-1) ;
16. }
    Line 3
    Line 8
    Line 13
    Line 15
    Something else

Answer 8

3,8