All Weeks Algorithms, Part I Coursera Quiz Answers
Table of Contents
Week 01 Algorithms, Part I Coursera Quiz Answer
Interview Questions: Union–Find (ungraded)
Q 1. Social network connectivity. Given a social network containing nn members and a log file containing mm timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend … of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be m \log nmlogn or better and use extra space proportional to nn.
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer:
class SocialNetworkConnectivity{
private static final int N;
private int[] id;
private int[] size;
private Log[] logs;
private int numOfTrees;
public SocialNetworkConnectivity() {
id = new int[N];
numOfTrees = N;
for(int i=0; i<N; i++){
id[i] = i;
size[i] = 1;
}
}
private int root(int i) {
while(id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
private boolean connected(int p, int q) {
return root(p) == root(q);
}
private void union(int p, int q) {
int i = root(p);
int j = root(q);
if(i == j) return;
if(size[i] > size[j]){
id[j] = i;
size[i] += size[j]
} else {
id[i] = j;
size[j] += size[i];
}
}
public int earliestTime() {
for(log in logs) {
if(!connected(log.p, log.q)) {
union(log.p, log.q);
numOfTrees--;
}
if(numOfTrees == 1) {
return log.timestamp;
}
}
return -1;
}
}Q 2. Union-find with specific canonical element. Add a method \mathtt{find()}find() to the union-find data type so that \mathtt{find(i)}find(i) returns the largest element in the connected component containing ii. The operations, \mathtt{union()}union(), \mathtt{connected()}connected(), and \mathtt{find()}find() should all take logarithmic time or better.
For example, if one of the connected components is \{1, 2, 6, 9\}{1,2,6,9}, then the \mathtt{find()}find() method should return 99 for each of the four elements in the connected components.
Answer:
class UnionFind{
private static final int N;
private int[] id;
private int[] size;
private Map<Integer, Integer> components = new HashMap<>();// (root, maxElement)
public UnionFind() {
id = new int[N];
for(int i=0; i<N; i++){
id[i] = i;
size[i] = 1;
components.put(i, i);
}
}
private int root(int i) {
while(id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
private boolean connected(int p, int q) {
return root(p) == root(q);
}
private void union(int p, int q) {
int i = root(p);
int j = root(q);
if(i == j) return;
if(size[i] > size[j]){
id[j] = i;
size[i] += size[j]
int maxJ = components.get(j);
maxJ > components.get(i) && components.put(i, maxJ);
} else {
id[i] = j;
size[j] += size[i];
int maxI = components.get(i);
maxI > components.get(j) && components.put(j, maxI);
}
}
public int find(int i) {
int root = root(i);
return components.get(root);
}
}Q 3. Successor with delete. Given a set of nn integers S = \{ 0, 1, … , n-1 \}S={0,1,…,n−1} and a sequence of requests of the following form:
- Remove xx from SS
- Find the successor of xx: the smallest yy in SS such that y \ge xy≥x.
design a data type so that all operations (except construction) take logarithmic time or better in the worst case.
Answer: balanced tree.
Interview Questions: Analysis of Algorithms (ungraded)
Q 1. 3-SUM in quadratic time. Design an algorithm for the 3-SUM problem that takes time proportional to n^2n2 in the worst case. You may assume that you can sort the nn integers in time proportional to n^2n2 or better.
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer: given an integer x and a sorted array a[] of n distinct integers, design a linear-time algorithm to determine if there exists two distinct indices i and j such that a[i]+a[j]==x.
Q 2. Search in a bitonic array. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of nn distinct integer values, determines whether a given integer is in the array.
- Standard version: Use \sim 3 \lg n∼3lgn compares in the worst case.
- Signing bonus: Use \sim 2 \lg n∼2lgn compares in the worst case (and prove that no algorithm can guarantee to perform fewer than \sim 2 \lg n∼2lgn compares in the worst case).
Answer: Standard version. First, find the maximum integer using ∼1lgn compares—this divides the array into the increasing and decreasing pieces. Signing bonus. Do it without finding the maximum integer.
Q 3. Egg drop. Suppose that you have an nn-story building (with floors 1 through nn) and plenty of eggs. An egg breaks if it is dropped from floor TT or higher and does not break otherwise. Your goal is to devise a strategy to determine the value of TT given the following limitations on the number of eggs and tosses:
- Version 0: 1 egg, \le T≤T tosses.
- Version 1: \sim 1 \lg n∼1lgn eggs and \sim 1 \lg n∼1lgn tosses.
- Version 2: \sim \lg T∼lgT eggs and \sim 2 \lg T∼2lgT tosses.
- Version 3: 22 eggs and \sim 2 \sqrt n∼2n tosses.
- Version 4: 22 eggs and \le c \sqrt T≤cT tosses for some fixed constant cc.
Answer: Version 0: sequential search. Version 1: binary search. Version 2: find an interval containing T of size ≤2T, then do binary search. Version 3: find an interval of size n√, then do sequential search. Note: can be improved to ∼2n−−√ tosses. Version 4: 1+2+3+…+t∼12t2. Aim for c=22√.
Week 02 Algorithms, Part I Coursera Quiz Answer
Interview Questions: Stacks and Queues (ungraded)
Q 1. Queue with two stacks. Implement a queue with two stacks so that each queue operations takes a constant amortized number of stack operations.
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer:
import java.util.Stack;
class StackQueue<Item> {
private Stack<Item> input = new Stack<Item>();
private Stack<Item> output = new Stack<Item>();
public StackQueue() {
}
public int size() {
return input.size() + output.size();
}
public boolean isEmpty() {
return (size() == 0);
}
public void enqueue(Item item) {
if (item == null) {
throw new java.lang.NullPointerException();
}
input.push(item);
}
public Item dequeue() {
if (isEmpty()) {
throw new java.util.NoSuchElementException();
}
if (output.isEmpty()) {
while (!input.isEmpty()) {
output.push(input.pop());
}
}
return output.pop();
}
// unit testing
public static void main(String[] args) {
StackQueue<Integer> squeue = new StackQueue<Integer>();
int i = 0;
int N = 100;
System.out.println("Size: " + squeue.size());
squeue.enqueue(i);
while (i <= N) {
if (i % 3 == 0) {
System.out.println("Dequeue: " + squeue.dequeue());
} else {
squeue.enqueue(i);
System.out.println("Enqueue: " + i);
}
++i;
}
System.out.println("Size: " + squeue.size());
while (!squeue.isEmpty()) {
System.out.println("Dequeue: " + squeue.dequeue());
}
System.out.println("Size: " + squeue.size());
}
}Q 2. Stack with max. Create a data structure that efficiently supports the stack operations (push and pop) and also a return-the-maximum operation. Assume the elements are real numbers so that you can compare them.
Answer:
import java.util.Stack;
import java.util.TreeSet;
class StackWithMax<Item> extends Stack<Item> {
private TreeSet<Item> tree = new TreeSet<Item>();
public Item max() {
return tree.last();
}
public Item push(Item item) {
super.push(item);
tree.add(item);
return item;
}
public Item pop() {
Item item = super.pop();
tree.remove(item);
return item;
}
public static void main(String[] args) {
StackWithMax<Integer> stack = new StackWithMax<Integer>();
int i = 1;
int N = 100;
System.out.println("Size: " + stack.size());
while (i <= N) {
if (i % 3 == 0) {
System.out.println("Max: " + stack.max());
} else {
System.out.println("Push: " + i);
stack.push(i);
}
++i;
}
System.out.println("Size: " + stack.size());
while (!stack.isEmpty()) {
System.out.println("Pop: " + stack.pop());
}
System.out.println("Size: " + stack.size());
}
}Q 3. Java generics. Explain why Java prohibits generic array creation.
Answer: Quote: Arrays of generic types are not allowed because they’re not sound
Interview Questions: Elementary Sorts (ungraded)
Q 1. Intersection of two sets. Given two arrays \mathtt{a[]}a[] and \mathtt{b[]}b[], each containing nn distinct 2D points in the plane, design a subquadratic algorithm to count the number of points that are contained both in array \mathtt{a[]}a[] and array \mathtt{b[]}b[].
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer:
package jobinterviewquestions;
import algs4.Shell;
/**
* Created by Leon on 7/9/15.
*/
public class ElementarySorts {
/*
Question 1
Intersection of two sets.
Given two arrays a[] and b[], each containing N distinct 2D points in the plane,
design a subquadratic algorithm to count the number of points that are contained both in array a[] and array b[].
*/
class Point implements Comparable<Point>{
private int x;
private int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point that) {
if (that.x > this.x) return -1;
if (that.x < this.x) return 1;
if (that.y > this.y) return -1;
if (that.y < this.y) return 1;
return 0;
}
public int countIntersection(Point[] a, Point[] b) {
Shell.sort(a);
Shell.sort(b);
int i = 0;
int j = 0;
int count = 0;
while (i < a.length && j < b.length) {
if (a[i].compareTo(b[j]) == 0) {
count++;
i++;
j++;
}
else if (a[i].compareTo(b[j]) < 0) i++;
else j++;
}
return count;
}
}Q 2. Permutation. Given two integer arrays of size nn, design a subquadratic algorithm to determine whether one is a permutation of the other. That is, do they contain exactly the same entries but, possibly, in a different order.
Answer:
public boolean isPerm(Integer[] a, Integer[] b) {
if (a.length != b.length) return false;
Shell.sort(a);
Shell.sort(b);
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) return false;
}
return true;
}Q 3. Dutch national flag. Given an array of nn buckets, each containing a red, white, or blue pebble, sort them by color. The allowed operations are:
- swap(i, j)swap(i,j): swap the pebble in bucket ii with the pebble in bucket jj.
- color(i)color(i): determine the color of the pebble in bucket ii.
The performance requirements are as follows:
- At most nn calls to color()color().
- At most nn calls to swap()swap().
- Constant extra space.
Answer:
enum Pebble {
Red,
White,
Blue
}
class Buckets {
private Pebble[] pebbles;
private Pebble color(int i) {
return pebbles[i];
}
private int compare(Pebble p) {
Pebble white = Pebble.White;
return p.ordinal() - white.ordinal();
}
private void swap(int i, int j) {
Pebble tmp = pebbles[i];
pebbles[i] = pebbles[j];
pebbles[j] = tmp;
}
public void sort() {
assert pebbles.length > 0;
int r = 0;
int runner = 0;
int b = pebbles.length - 1;
while (runner <= b) {
Pebble color = color(runner);
int cmp = compare(color);
if (cmp < 0) {
swap(runner++, r++);
}
else if (cmp > 0) {
swap(runner, b--);
}
else {
runner++;
}
}
}
}
}Week 03 Algorithms, Part I Coursera Quiz Answer
Interview Questions: Mergesort (ungraded)
Q 1. Merging with smaller auxiliary array. Suppose that the subarray \mathtt{a[0]}a[0] to \mathtt{a[n-1]}a[n−1] is sorted and the subarray \mathtt{a[n]}a[n] to \mathtt{a[2*n-1]}a[2∗n−1] is sorted. How can you merge the two subarrays so that \mathtt{a[0]}a[0] to \mathtt{a[2*n-1]}a[2∗n−1] is sorted using an auxiliary array of length nn (instead of 2n2n)?
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer:
package jobinterviewquestions;
import stdlib.StdRandom;
/**
* Created by Leon on 7/12/15.
*/
public class Mergesort {
private boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
public void mergeWithSmaller(Comparable[] a, Comparable[] aux) {
int N = aux.length;
assert a.length == 2*N;
for (int i = 0; i < N; i++) {
aux[i] = a[i];
}
int l = 0;
int r = N;
int i = 0;
for (; i < N; i++) {
if (less(aux[l], a[r])) a[i] = aux[l++];
else a[i] = a[r++];
}
while (l < N) {
if (r >= 2*N || less(aux[l], a[r]) ) a[i++] = aux[l++];
else a[i++] = a[r++];
}
}Q 2.Counting inversions. An inversion in an array a[\,]a[] is a pair of entries a[i]a[i] and a[j]a[j] such that i < ji<j but a[i] > a[j]a[i]>a[j]. Given an array, design a linearithmic algorithm to count the number of inversions.
Answer:
private int merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
int k = lo;
int i = lo;
int j = mid + 1;
int count = 0;
while (k < hi) {
if (i > mid) a[k++] = aux[j++];
else if (j > hi) a[k++] = aux[i++];
else if (less(aux[j], aux[i])) {
count += mid + 1 - i;
a[k++] = aux[j++];
}
else a[k++] = aux[i++];
}
return count;
}
public int countInversion(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
int count = 0;
for (int sz = 1; sz < a.length; sz += sz) {
for (int i = 0; i < a.length - sz; i += 2*sz) {
int lo = i;
int m = i + sz - 1;
int hi = Math.min(i + 2*sz - 1, a.length - 1);
count += merge(a, aux, lo, m, hi);
}
}
return count;
}Q 3. Shuffling a linked list. Given a singly-linked list containing nn items, rearrange the items uniformly at random. Your algorithm should consume a logarithmic (or constant) amount of extra memory and run in time proportional to n \log nnlogn in the worst case.
Answer:
private class Node {
Object item;
Node next;
}
private void merge(Node lh, Node rh) {
Node left = lh;
Node right = rh;
if (StdRandom.uniform(1) > 0) {
lh = right;
right = right.next;
}
else {
left = left.next;
}
Node runner = lh;
while (right != null || left != null) {
if (left == null) {
runner.next = right;
right =right.next;
}
else if (right == null) {
runner.next = left;
left = left.next;
}
else if (StdRandom.uniform(1) > 0) {
runner.next = right;
right = right.next;
}
else {
runner.next = left;
left = left.next;
}
runner = runner.next;
}
}
public void shuffle(Node head, int N) {
if (N == 1) return;
int k = 1;
Node mid = head;
while (k < N / 2) {
mid = mid.next;
k++;
}
Node rh = mid.next;
mid.next = null;
shuffle(head, N / 2);
shuffle(rh, N - N / 2);
merge(head, rh);
}
}Interview Questions: Quicksort (ungraded)
Q 1. Nuts and bolts. A disorganized carpenter has a mixed pile of nn nuts and nn bolts. The goal is to find the corresponding pairs of nuts and bolts. Each nut fits exactly one bolt and each bolt fits exactly one nut. By fitting a nut and a bolt together, the carpenter can see which one is bigger (but the carpenter cannot compare two nuts or two bolts directly). Design an algorithm for the problem that uses at most proportional to n \log nnlogn compares (probabilistically).
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer:
package jobinterviewquestions;
import algs4.Bag;
import stdlib.In;
import java.util.TreeMap;
import java.util.TreeSet;
/**
* Created by Leon on 7/14/15.
*/
public class QuickSort {
class Nut {
private int size;
public int compare(Bolt bolt) {
if (bolt.size > this.size) return -1;
else if (bolt.size < this.size) return 1;
else return 0;
}
}
class Bolt {
private int size;
}
public void pair(Bolt[] bolts, Nut[] nuts) {
int n = nuts.length;
assert bolts.length == n;
Nut[] auxN = new Nut[n];
Bolt[] auxB = new Bolt[n]; //need TreeMap to implement
for (int i = 0; i < n; i++) {
int lo = floor(auxB, nuts[i]); //use floor api in TreeMap
int hi = ceil(auxB, nuts[i]); //use ceil api in TreeMap
int index = partition(bolts, nuts[i], lo, hi);
auxB[index] = bolts[index];
auxN[index] = nuts[i];
}
for (int i = 0; i < n; i++) {
nuts[i] = auxN[i];
}
}
private int partition(Bolt[] bolts, Nut nut, int lo, int hi) {
int l = lo;
int r = hi;
while (true) {
while (nut.compare(bolts[++l]) > 0) if (l == hi) break;
while (nut.compare(bolts[--r]) < 0) if (r == lo) break;
if (l >= r) break;
exch(bolts, l, r);
}
return l;
}
private void exch(Bolt[] bolts, int l, int r) {
Bolt tmp = bolts[l];
bolts[l] = bolts[r];
bolts[r] = tmp;
}
private int floor(Bolt[] b, Nut nut) {
return 0;
}
private int ceil(Bolt[] b, Nut nut) {
return 0;
}Q 2. Selection in two sorted arrays. Given two sorted arrays a[\; ]a[] and b[ \; ]b[], of lengths n_1n1 and n_2n2 and an integer 0 \le k < n_1 + n_20≤k<n1+n2, design an algorithm to find a key of rank kk. The order of growth of the worst case running time of your algorithm should be \log nlogn, where n = n_1 + n_2n=n1+n2.
- Version 1: n1=n2 (equal length arrays) and k=n/2 (median).
- Version 2: k=n/2 (median).
- Version 3: no restrictions.
Answer:
int MAX = Integer.MAX_VALUE;
int MIN = Integer.MIN_VALUE;
public int select(int[] a, int ah, int[] b, int bh, int k) {
int n1 = a.length - ah;
int n2 = b.length - bh;
int i = ah + (int)(double)(n1/(n1 + n2)*(k - 1));
int j = bh + k - i - 1;
int ai = i == n1 ? MAX : a[i];
int bj = j == n2 ? MAX : b[j];
int ai1 = i == 0 ? MIN : a[i - 1];
int bj1 = j == 0 ? MIN : b[j - 1];
if (ai > bj1 && ai < bj) return ai;
else if (bj > ai1 && bj < ai) return bj;
else if (ai < bj1) return select(a, i + 1, b, bh, k - i - 1);
else return select(a, ah, b, j + 1, k - j - 1);
}Q 3. Decimal dominants. Given an array with nn keys, design an algorithm to find all values that occur more than n/10n/10 times. The expected running time of your algorithm should be linear.
Answer:
class DecimalDominants {
private TreeMap<Integer, Integer> counts;
private int K;
private int N;
private int[] A;
public DecimalDominants(int[] a, int k) {
A = a;
N = a.length;
K = k;
buildCounts(a);
}
private void buildCounts(int[] a) {
for (int i = 0; i < N; i++) {
if (counts.containsKey(i)) counts.put(i, counts.get(i) + 1);
else counts.put(i, 1);
if (counts.keySet().size() >= K) removeCounts();
}
}
private void removeCounts() {
for (int k : counts.keySet()) {
int c = counts.get(k);
if (c > 1) counts.put(k, c - 1);
else counts.remove(k);
}
}
public Iterable<Integer> find() {
Bag<Integer> result = new Bag<Integer>();
for (int k : counts.keySet()) {
if (count(k) > N/K) result.add(k);
}
return result;
}
private int count(int k) {
int count = 0;
for (int i = 0; i < N; i++) {
if (A[i] == k) count++;
}
return count;
}
}
}Week 04 Algorithms, Part I Coursera Quiz Answer
Interview Questions: Priority Queues (ungraded)
Q 1. Dynamic median. Design a data type that supports insert in logarithmic time, find-the-median in constant time, and remove-the-median in logarithmic time. If the number of keys in the data type is even, find/remove the lower median.
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer:
package jobinterviewquestions;
import algs4.MaxPQ;
import algs4.MinPQ;
import algs4.Queue;
import algs4.SymbolDigraph;
/**
* Created by Leon on 7/19/15.
*/
public class PriorityQueue {
/*
Question 1
Dynamic median.
Design a data type that supports insert in logarithmic time, find-the-median in constant time, and remove-the-median in logarithmic time.
*/
class MediaHeap {
private MaxPQ<Integer> left;
private MinPQ<Integer> right;
private int L;
private int R;
MediaHeap() {
left = new MaxPQ<Integer>();
right = new MinPQ<Integer>();
}
public double findMedian() {
int L = left.size();
int R = right.size();
if (L == R)
return ((double)left.max() + (double)right.min()) / 2;
else if (L > R)
return left.max();
else
return right.min();
}
public void insert(int key) {
double median = findMedian();
int L = left.size();
int R = right.size();
if (key <= median) {
left.insert(key);
if (L - R > 1)
right.insert(left.delMax());
}
else {
right.insert(key);
if (R - L > 1)
left.insert(right.delMin());
}
}
public void removeMedian() {
int L = left.size();
int R = right.size();
if (L > R) {
left.delMax();
}
else {
right.delMin();
}
}
}Q 2. Randomized priority queue. Describe how to add the methods \mathtt{sample()}sample() and \mathtt{delRandom()}delRandom() to our binary heap implementation. The two methods return a key that is chosen uniformly at random among the remaining keys, with the latter method also removing that key. The \mathtt{sample()}sample() method should take constant time; the \mathtt{delRandom()}delRandom() method should take logarithmic time. Do not worry about resizing the underlying array.
Answer:
generate random number from 0 - N, sample() just return that number
when delete random, exchange with last, delete last, then compare with parent and children to decide whether swim or sinkQ 3. Taxicab numbers. A taxicab number is an integer that can be expressed as the sum of two cubes of positive integers in two different ways: a^3 + b^3 = c^3 + d^3a3+b3=c3+d3. For example, 17291729 is the smallest taxicab number: 9^3 + 10^3 = 1^3 + 12^393+103=13+123. Design an algorithm to find all taxicab numbers with aa, bb, cc, and dd less than nn.
- Version 1: Use time proportional to n^2 \log nn2logn and space proportional to n^2n2.
- Version 2: Use time proportional to n^2 \log nn2logn and space proportional to nn.
Answer:
class Taxicab implements Comparable<Taxicab>{
int n1;
int n2;
int cube;
Taxicab(int n1, int n2) {
this.n1 = n1;
this.n2 = n2;
this.cube = n1 * n1 * n1 + n2 * n2 * n2;
}
@Override
public int compareTo(Taxicab that) {
if (that.cube > this.cube) return -1;
if (that.cube < this.cube) return 1;
return 0;
}
@Override
public boolean equals(Object o) {
if (o instanceof Taxicab) {
if (((Taxicab)o).compareTo(this) == 0)
return true;
}
return false;
}
@Override
public String toString() {
return "number: " + cube + " (" + n1 + ", " + n2 + ")";
}
}
public void findTaxinumber(int N) {
MinPQ<Taxicab> candidates = new MinPQ<Taxicab>();
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
Taxicab t = new Taxicab(i, j);
if (candidates.size() < N) {
candidates.insert(t);
}
else {
Queue<Taxicab> temp = new Queue<Taxicab>();
Taxicab min = candidates.delMin();
while (candidates.min().equals(min)) {
temp.enqueue(candidates.delMin());
}
if (!t.equals(min)) {
candidates.insert(t);
}
else {
temp.enqueue(t);
}
if (!temp.isEmpty()) {
for (Taxicab taxi: temp) {
System.out.println(taxi);
}
System.out.println(min);
}
}
}
}
}
public static void main(String[] args) {
PriorityQueue p = new PriorityQueue();
p.findTaxinumber(12);
}
}Interview Questions: Elementary Symbol Tables (ungraded)
Q 1. Java autoboxing and equals(). Consider two \mathtt{double}double values \mathtt{a}a and \mathtt{b}b and their corresponding \mathtt{Double}Double values \mathtt{x}x and \mathtt{y}y.
- Find values such that \mathtt{(a == b)}(a==b) is \mathtt{true}true but \mathtt{x.equals(y)}x.equals(y) is \mathtt{false}false.
- Find values such that \mathtt{(a == b)}(a==b) is \mathtt{false}false but \mathtt{x.equals(y)}x.equals(y) is \mathtt{true}true.
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer:
package jobinterviewquestions;
import algs4.DoublingRatio;
import algs4.Queue;
/**
* Created by Leon on 7/20/15.
*/
public class ElementarySymbolTables {
/*
1. a=0.0, b=-0.0
2. a=b=Double.NaN
*/Q 2. Check if a binary tree is a BST. Given a binary tree where each \mathtt{Node}Node contains a key, determine whether it is a binary search tree. Use extra space proportional to the height of the tree.
Answer:
private class Node {
private int key; // sorted by key
private int val; // associated data
private Node left, right; // left and right subtrees
private int N; // number of nodes in subtree
public Node(int key, int val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
public boolean checkBST(Node p, int min, int max) {
if (p == null) return true;
if(p.key >= max || p.key <= min ) return false;
return checkBST(p.left, min, p.key) && checkBST(p.right, p.key, max);
}Q 3. Inorder traversal with constant extra space. Design an algorithm to perform an inorder traversal of a binary search tree using only a constant amount of extra space.
public void inorder(Node root) {
if (root == null) return;
Node previous;
Node current = root;
while (current != null) {
//current has no left child, print current, then go right
if (current.left == null) {
System.out.println(current.val);
current = current.right;
}
else {
previous = current.left;
//go down to current left children's rightmost child
while (previous.right != null && previous.right != current) {
previous = previous.right;
}
//if the rightmost child hasn't being linked to current, then link it, and traverse to current left
if (previous.right == null) {
previous.right = current;
current = current.left;
}
//if the rightmost child already linked to current (current left children being traversed), then print current and cut the link to restore tree structure
else {
previous.right = null;
System.out.println(current.val);
current = current.right;
}
}
}
}Q 4. Web tracking. Suppose that you are tracking nn web sites and mm users and you want to support the following API:
- User visits a website.
- How many times has a given user visited a given site?
What data structure or data structures would you use?
Answer:
public static void main(String[] args) {
double a = Double.NaN;
double b = Double.NaN;
Double x = new Double(a);
Double y = new Double(b);
System.out.println(a==b);
System.out.println(x.equals(y));
}
}Week 05 Algorithms, Part I Coursera Quiz Answer
Interview Questions: Balanced Search Trees (ungraded)
Q 1. Red–black BST with no extra memory. Describe how to save the memory for storing the color information when implementing a red–black BST.
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer: Hint: modify the structure of the BST to encode the color information.
Q 2. Document search. Design an algorithm that takes a sequence of nn document words and a sequence of mm query words and find the shortest interval in which the mm query words appear in the document in the order given. The length of an interval is the number of words in that interval.
Answer: Hint: for each word, maintain a sorted list of the indices in the document in which that word appears. Scan through the sorted lists of the query words in a judicious manner.
Q 3. Generalized queue. Design a generalized queue data type that supports all of the following operations in logarithmic time (or better) in the worst case.
- Create an empty data structure.
- Append an item to the end of the queue.
- Remove an item from the front of the queue.
- Return the ith item in the queue.
- Remove the ith item from the queue.
Answer: Hint: create a red–black BST where the keys are integers and the values are the items such that the ith largest integer key in the red–black BST corresponds to the ith item in the queue.
Week 06 Algorithms, Part I Coursera Quiz Answer
Interview Questions: Hash Tables (ungraded)
Q 1. 4-SUM. Given an array a[ \; ]a[] of nn integers, the 4-SUM problem is to determine if there exist distinct indices ii, jj, kk, and ll such that a[i] + a[j] = a[k] + a[l]a[i]+a[j]=a[k]+a[l]. Design an algorithm for the 4-SUM problem that takes time proportional to n^2n2 (under suitable technical assumptions).
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
Answer:
Hint: create a hash table with n \choose{2}(2n) key-value pairs
Q 2. Hashing with wrong hashCode() or equals(). Suppose that you implement a data type \mathtt{OlympicAthlete}OlympicAthlete for use in a \mathtt{java.util.HashMap}java.util.HashMap.
- Describe what happens if you override \mathtt{hashCode()}hashCode() but not \mathtt{equals()}equals().
- Describe what happens if you override \mathtt{equals()}equals() but not \mathtt{hashCode()}hashCode().
- Describe what happens if you override \mathtt{hashCode()}hashCode() but implement \verb#public boolean equals(OlympicAthlete that)#public boolean equals(OlympicAthlete that) instead of \verb#public boolean equals(Object that)#public boolean equals(Object that).
Answer: Hint: it’s code—try it and see!
Get All Course Quiz Answers of Software Development Lifecycle Specialization
Software Development Processes and Methodologies Quiz Answers
Agile Software Development Coursera Quiz Answers
Lean Software Development Coursera Quiz Answers
Engineering Practices for Building Quality Software Quiz Answers
