Array

Question 1

Array, Even appears first time comp O(n), Space comp O(1)

Answer 1

public static void evenOdd(List A) { int nextEven = 0, nextOdd = A.size() - 1; while (nextEven < nextOdd) { if (A.get(nextEven) % 2 == 0) { nextEven++; } else { Collections.swap(A, nextEven, nextOdd–); } } }

Question 2

Filling an array from 1. the front 2. the back is faster

Answer 2

2. the back

Question 3

Array, 1. delete en entry 2. overwrite an entry is better performance

Answer 3

2. overwrite an entry deleting an entry requires moving all entries to its left

Question 4

Integer encoded by an array 1. processing the digits from the back 2. processing the digits from the front of the array is better

Answer 4

1. processing the digits from the back

Question 5

DutchNational Flag algo Time Comp O(n) Space Comp O(1)

Answer 5

public static void dutchFlagPartition(int pivotIndex, List A) { Color pivot = A.get(pivotIndex); /** * Keep the following invariants during partitioning: * bottom group: A.subList(0, smaller). * middle group: A.subList(smaller, equal). * unclassified group: A.subList(equal, larger). * top group: A.subList(larger, A.size()). */ int smaller = 0, equal = 0, larger = A.size(); // Keep iterating as long as there is an unclassified element. while (equal < larger) { // A.get(equal) is the incoming unclassified element. if (A.get(equal).ordinal() < pivot.ordinal()) { Collections.swap(A, smaller++, equal++); } else if (A.get(equal).ordinal() == pivot.ordinal()) { ++equal; } else { // A.get(equal) > pivot. Collections.swap(A, equal, –larger); } } }

Question 6

Increment an non-negative integer by one Time comp O(n)

Answer 6

public static List plusOne(List A) { int n = A.size() - 1; A.set(n, A.get(n) + 1); for (int i = n; i > 0 && A.get(i) == 10; –i) { A.set(i, 0); A.set(i - 1, A.get(i - 1) + 1); } if (A.get(0) == 10) { // There is a carry-out, so we need one more digit to store the result. // A slick way to do this is to append a 0 at the end of the array, // and update the first entry to 1. A.set(0, 1); A.add(0); } return A; }

Question 7

Multiply Two Integer in the array Time O(nm)

Answer 7

public static List multiply(List num1, List num2) { final int sign = num1.get(0) < 0 ^ num2.get(0) < 0 ? -1 : 1; // MSB shows negative or positive num1.set(0, Math.abs(num1.get(0))); // remove the sign for now num2.set(0, Math.abs(num2.get(0)));// remove the sign for now List result = new ArrayList<>(Collections.nCopies(num1.size() + num2.size(), 0)); // result size will be equal to or more than num1 size + num2 size for (int i = num1.size() - 1; i >= 0; –i) { for (int j = num2.size() - 1; j >= 0; –j) { result.set(i + j + 1, result.get(i + j + 1) + num1.get(i) * num2.get(j)); result.set(i + j, result.get(i + j) + result.get(i + j + 1) / 10); result.set(i + j + 1, result.get(i + j + 1) % 10); } } // Remove the leading zeroes. int firstNotZero = 0; while (firstNotZero < result.size() && result.get(firstNotZero) == 0) { ++firstNotZero; } result = result.subList(firstNotZero, result.size()); if (result.isEmpty()) { return List.of(0); } result.set(0, result.get(0) * sign); return result; }

Question 8

Advancing thru an array Time O(n) Space O(1)

Answer 8

public static boolean canReachEnd(List maxAdvanceSteps) { int furthestReachSoFar = 0, lastIndex = maxAdvanceSteps.size() - 1; for (int i = 0; i <= furthestReachSoFar && furthestReachSoFar < lastIndex; ++i) { furthestReachSoFar = Math.max(furthestReachSoFar, i + maxAdvanceSteps.get(i)); } return furthestReachSoFar >= lastIndex; }

Question 9

Delete Duplicates from a sorted array Time O(n) and Space O(1)

Answer 9

// Returns the number of valid entries after deletion. public static int deleteDuplicates(List A) { if (A.isEmpty()) { return 0; } int writeIndex = 1; for (int i = 1; i < A.size(); ++i) { if (!A.get(writeIndex - 1).equals(A.get(i))) { A.set(writeIndex++, A.get(i)); } } return writeIndex; }

Question 10

Buy and sell stock compute max profit in buying and selling one share of the stock Time O(n) Space O(1)

Answer 10

public static double computeMaxProfit(List prices) { double minPrice = Double.MAX_VALUE, maxProfit = 0.0; for (Double price : prices) { maxProfit = Math.max(maxProfit, price - minPrice); minPrice = Math.min(minPrice, price); } return maxProfit; }

Question 11

Buy and sell stock twice compute max profit in buying and selling stock twice Time O(n) Space O(1)

Answer 11

private static double buyAndSellStockTwiceConstantSpace(List prices) { List minPrices = List.of(Double.MAX_VALUE, Double.MAX_VALUE), maxProfits = List.of(0.0, 0.0); for (Double price : prices) { for (int i = 1; i >= 0; –i) { maxProfits.set(i, Math.max(maxProfits.get(i), price - minPrices.get(i))); minPrices.set( i, Math.min(minPrices.get(i), price - (i - 1 >= 0 ? maxProfits.get(i - 1) : 0.0))); } } return maxProfits.get(1); }

Question 12

rearrange array’s element in an alternation time O(n)

Answer 12

public static void rearrange(List A) { for (int i = 1; i < A.size(); ++i) { if (((i % 2) == 0 && A.get(i - 1) < A.get(i)) || ((i % 2) != 0 && A.get(i - 1) > A.get(i))) { Collections.swap(A, i - 1, i); } } }

Question 13

generate prime Space O(n) Time O(n^(3/2))

Answer 13

// Given n, return all primes up to and including n. public static List generatePrimes(int n) { if (n < 2) { return Collections.emptyList(); } final int size = (int)Math.floor(0.5 * (n - 3)) + 1; List primes = new ArrayList<>(); primes.add(2); // isPrime.get(i) represents whether (2i + 3) is prime or not. // For example, isPrime.get(0) represents 3 is prime or not, // isPrime.get(1) represents 5, isPrime.get(2) represents 7, etc. // Initially, set each to true. Then use sieving to eliminate nonprimes. List isPrime = new ArrayList<>(Collections.nCopies(size, true)); for (long i = 0; i < size; ++i) { if (isPrime.get((int)i)) { int p = (((int)i * 2) + 3); primes.add(p); // Sieving from p^2, whose value is (4i^2 + 12i + 9). The index of this // value in isPrime is (2i^2 + 6i + 3) because isPrime.get(i) represents // 2i + 3. // // Note that we need to use long type for j because p^2 might overflow. for (long j = ((i * i) * 2) + 6 * i + 3; j < size; j += p) { isPrime.set((int)j, false); } } } return primes; }

Question 14

Given an array A of n elements and a permutation P, apply P to A Time O(n) Space O(n)

Answer 14

public static void applyPermutation(List perm, List A) { for (int i = 0; i < A.size(); ++i) { while (perm.get(i) != i) { Collections.swap(A, i, perm.get(i)); Collections.swap(perm, i, perm.get(i)); } } }

Question 15

Write s program that takes as input an array of integers, and returns the next array under lexicographical ordering, from the set of all arrays that are permutations of the input array. Time O(n) Space O(1)

Answer 15

public static List nextPermutation(List perm) { // Find the first entry from the right that is smaller than the entry // immediately after it. int inversionPoint = perm.size() - 2; while (inversionPoint >= 0 && perm.get(inversionPoint) >= perm.get(inversionPoint + 1)) { –inversionPoint; } if (inversionPoint == -1) { return Collections.emptyList(); // perm is the last permutation. } // Swap the smallest entry after index inversionPoint that is greater than // perm.get(inversionPoint). Since entries in perm are decreasing after // inversionPoint, if we search in reverse order, the first entry that is // greater than perm.get(inversionPoint) is the entry to swap with. for (int i = perm.size() - 1; i > inversionPoint; –i) { if (perm.get(i) > perm.get(inversionPoint)) { Collections.swap(perm, inversionPoint, i); break; } } // Entries in perm must appear in decreasing order after inversionPoint, so // we simply reverse these entries to get the smallest dictionary order. Collections.reverse(perm.subList(inversionPoint + 1, perm.size())); return perm; }

Question 16

implement an algorithm that takes as input an array of distinct elements and a size, and returns a subset of the given size of the array elements. All subsets should be equally likely. Return the result in input array itself. Time O(k) Space O(1)

Answer 16

public static void randomSampling(int k, List A) { Random gen = new Random(); for (int i = 0; i < k; ++i) { // Generate a random int in [i, A.size() - 1]. Collections.swap(A, i, i + gen.nextInt(A.size() - i)); } }

Question 17

Design a program that takes as input a size k, and reads packets, continuously maintaining a uniform random subset of size k of the read packets. Time O(n) space O(k)

Answer 17

// Assumption: there are at least k elements in the stream. public static List onlineRandomSample(Iterator stream, int k) { List runningSample = new ArrayList<>(k); // Stores the first k elements. for (int i = 0; stream.hasNext() && i < k; ++i) { runningSample.add(stream.next()); } // Have read the first k elements. int numSeenSoFar = k; Random randIdxGen = new Random(); while (stream.hasNext()) { Integer x = stream.next(); ++numSeenSoFar; // Generate a random number in [0, numSeenSoFar], and if this number is in // [0, k - 1], we replace that element from the sample with x. final int idxToReplace = randIdxGen.nextInt(numSeenSoFar); if (idxToReplace < k) { runningSample.set(idxToReplace, x); } } return runningSample; }

Question 18

(Array)Compute a random permutation Time O(n) Space O(n)

Answer 18

public static List computeRandomPermutation(int n) { List permutation = IntStream.range(0, n).boxed().collect(Collectors.toList()); randomSampling(permutation.size(), permutation); return permutation; } public static void randomSampling(int k, List A) { Random gen = new Random(); for (int i = 0; i < k; ++i) { // Generate a random int in [i, A.size() - 1]. Collections.swap(A, i, i + gen.nextInt(A.size() - i)); } }

Question 19

(Array) Compute a random subset input: integer n size: k <= n returns k size subset Time O(k) Space O(k)

Answer 19

// Returns a random k-sized subset of {0, 1, …, n - 1}. public static List randomSubset(int n, int k) { Map changedElements = new HashMap<>(); Random randIdxGen = new Random(); for (int i = 0; i < k; ++i) { // Generate random int in [i, n - 1]. int randIdx = i + randIdxGen.nextInt(n - i); Integer ptr1 = changedElements.get(randIdx); Integer ptr2 = changedElements.get(i); if (ptr1 == null && ptr2 == null) { changedElements.put(randIdx, i); changedElements.put(i, randIdx); } else if (ptr1 == null && ptr2 != null) { changedElements.put(randIdx, ptr2); changedElements.put(i, randIdx); } else if (ptr1 != null && ptr2 == null) { changedElements.put(i, ptr1); changedElements.put(randIdx, i); } else { changedElements.put(i, ptr1); changedElements.put(randIdx, ptr2); } } List result = new ArrayList<>(k); for (int i = 0; i < k; ++i) { result.add(changedElements.get(i)); } return result; }

Question 20

You are given n numbers as well as probabilities p0, p1,,, which sum up to 1. Given a random number generator that produces values in [0, 1) uniformly, how would you generate one of the n numbers according to the specified probabilities? Time O(n) Space O(n) once the array is constructed, time O( log n)

Answer 20

public static int nonuniformRandomNumberGeneration(List values, List probabilities) { List prefixSumOfProbabilities = new ArrayList<>(); // Creating the endpoints for the intervals corresponding to the // probabilities. probabilities.stream().reduce(0.0, (left, right) -> { prefixSumOfProbabilities.add(left + right); return left + right; }); Random r = new Random(); // Get a random number in [0.0,1.0). final double uniform01 = r.nextDouble(); // Find the index of the interval that uniform01 lies in. int it = Collections.binarySearch(prefixSumOfProbabilities, uniform01); if (it < 0) { // We want the index of the first element in the array which is // greater than the key. // // When a key is not present in the array, Collections.binarySearch() // returns the negative of 1 plus the smallest index whose entry // is greater than the key. // // Therefore, if the return value is negative, by taking its absolute // value minus 1, we get the desired index. final int intervalIdx = Math.abs(it) - 1; return values.get(intervalIdx); } else { // We have it >= 0, i.e., uniform01 equals an entry // in prefixSumOfProbabilities. // // Because we uniform01 is a random double, the probability of it // equalling an endpoint in prefixSumOfProbabilities is exceedingly low. // However, it is not 0, so to be robust we must consider this case. return values.get(it); } }

Question 21

Check whether 9 x 9 2D array representing a partially completed Sudoku is valid. Time: O(n^2) Space: O(n)

Answer 21

// Check if a partially filled matrix has any conflicts. public static boolean isValidSudoku(List> partialAssignment) { // Check row constraints. for (int i = 0; i < partialAssignment.size(); ++i) { if (hasDuplicate(partialAssignment, i, i + 1, 0, partialAssignment.size())) { return false; } } // Check column constraints. for (int j = 0; j < partialAssignment.size(); ++j) { if (hasDuplicate(partialAssignment, 0, partialAssignment.size(), j, j + 1)) { return false; } } // Check region constraints. int regionSize = (int)Math.sqrt(partialAssignment.size()); for (int I = 0; I < regionSize; ++I) { for (int J = 0; J < regionSize; ++J) { if (hasDuplicate(partialAssignment, regionSize * I, regionSize * (I + 1), regionSize * J, regionSize * (J + 1))) { return false; } } } return true; } // Return true if subarray // partialAssignment[startRow, endRow][startCol, endCol] contains any // duplicates in {1, 2, …, partialAssignment.size()}; otherwise return // false. private static boolean hasDuplicate(List> partialAssignment, int startRow, int endRow, int startCol, int endCol) { List isPresent = new ArrayList<>( Collections.nCopies(partialAssignment.size() + 1, false)); for (int i = startRow; i < endRow; ++i) { for (int j = startCol; j < endCol; ++j) { if (partialAssignment.get(i).get(j) != 0 && isPresent.get(partialAssignment.get(i).get(j))) { return true; } isPresent.set(partialAssignment.get(i).get(j), true); } } return false; }

Question 22

Write a program which takes an n X n 2D array and returns the spiral ordering of the array. Time O(n^2) Space O(1)

Answer 22

public static List matrixInSpiralOrder(List> squareMatrix) { List spiralOrdering = new ArrayList<>(); for (int offset = 0; offset < Math.ceil(0.5 * squareMatrix.size()); ++offset) { matrixLayerInClockwise(squareMatrix, offset, spiralOrdering); } return spiralOrdering; } private static void matrixLayerInClockwise(List> squareMatrix, int offset, List spiralOrdering) { if (offset == squareMatrix.size() - offset - 1) { // squareMatrix has odd dimension, and we are at its center. spiralOrdering.add(squareMatrix.get(offset).get(offset)); return; } for (int j = offset; j < squareMatrix.size() - offset - 1; ++j) { spiralOrdering.add(squareMatrix.get(offset).get(j)); } for (int i = offset; i < squareMatrix.size() - offset - 1; ++i) { spiralOrdering.add( squareMatrix.get(i).get(squareMatrix.size() - offset - 1)); } for (int j = squareMatrix.size() - offset - 1; j > offset; –j) { spiralOrdering.add( squareMatrix.get(squareMatrix.size() - offset - 1).get(j)); } for (int i = squareMatrix.size() - offset - 1; i > offset; –i) { spiralOrdering.add(squareMatrix.get(i).get(offset)); } }

Question 23

Write a program which takes an n X n 2D array and returns the spiral ordering of the array. use only a single iteration Time O(n^2) Space O(1)

Answer 23

public static List matrixInSpiralOrder(List> squareMatrix) { final int[][] SHIFT = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; int dir = 0, x = 0, y = 0; List spiralOrdering = new ArrayList<>(); for(int i = 0; i < squareMatrix.size() * squareMatrix.size(); ++1){ spiralOrdering.add(squareMatrix.get(x).get(y)); squareMatrix.get(x).set(y, 0); int nextX = x + SHIFT[dir][0], nextY = y + SHIFT[dir][1]; if (nextX < 0 || nextX >= squareMatrix.size() || nextY < 0 || nextY >= squareMatrix.size() || squareMatrix.get(nextX).get(nextY) == 0 { dir = (dir + 1) % 4; nextX = x + SHIFT[dir][0]; nextY = y + SHIFT[dir][1]; } x = nextX; y = nextY; } return spiralOrdering; }

Question 24

Write a function that takes as input an n x n 2D array, and rotates the array by 90 degrees clockwise, Time O(n^2) Space O(1)

Answer 24

public static void rotateMatrix(List> squareMatrix) { final int matrixSize = squareMatrix.size() - 1; for (int i = 0; i < (squareMatrix.size() / 2); ++i) { for (int j = i; j < matrixSize - i; ++j) { // Perform a 4-way exchange. int temp1 = squareMatrix.get(matrixSize - j).get(i); int temp2 = squareMatrix.get(matrixSize - i).get(matrixSize - j); int temp3 = squareMatrix.get(j).get(matrixSize - i); int temp4 = squareMatrix.get(i).get(j); squareMatrix.get(i).set(j, temp1); squareMatrix.get(matrixSize - j).set(i, temp2); squareMatrix.get(matrixSize - i).set(matrixSize - j, temp3); squareMatrix.get(j).set(matrixSize - i, temp4); } } }

Question 25

Write a program which takes as input a nonnegative integer n and returns the first n rows of Pascal’s triangle. Time O(n^2) Space O(n^2)

Answer 25

public static List> generatePascalTriangle(int numRows) { List> pascalTriangle = new ArrayList<>(); for (int i = 0; i < numRows; ++i) { List currRow = new ArrayList<>(); for (int j = 0; j <= i; ++j) { // Set this entry to the sum of the two above adjacent entries if they // exist. currRow.add((0 < j && j < i) ? pascalTriangle.get(i - 1).get(j - 1) + pascalTriangle.get(i - 1).get(j) : 1); } pascalTriangle.add(currRow); } return pascalTriangle; }