본문 바로가기
Maximum Absolute Difference You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N. f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.For example,A=[1, 3, -1] f(1, 1) = f(2, 2) = f(3, 3) = 0 f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3 f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4 f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5 So, we return 5. .. 더보기
Max Sum Contiguous Subarray Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example:Given the array [-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray [4,-1,2,1] has the largest sum = 6.For this problem, return the maximum sum. My Solutions:import sys def maxSubArray(A): size = len(A) max_sum = max(A[0], -sys.maxsize - 1) for i in range(size): result = A[i] for j in .. 더보기
REC_CMPL3 What is the worst case time complexity of the following code:int memo[101][101]; int findMinPath(vector& V, int r, int c) { int R = V.size(); int C = V[0].size(); if (r >= R || c >= C) return 100000000; // Infinity if (r == R - 1 && c == C - 1) return 0; if (memo[r][c] != -1) return memo[r][c]; memo[r][c] = V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1)); return memo[r][c]; } C.. 더보기
CHOOSE2 Which of the given options provides the increasing order of complexity of functions f1, f2, f3 and f4:f1(n) = 2^n f2(n) = n^(3/2) f3(n) = nLogn f4(n) = n^(Logn) f3, f2, f4, f1 f3, f2, f1, f4 f2, f3, f1, f4 f2, f3, f4, f1Good solution:n < nlog(n)n^x < n^y if x < yn^x < c^n where c is a constant (polynomials will eventually grow slower than exponentials)log(n) < nc^n < n! < n^n where c is a constant 더보기
REC_CMPL2 What is the worst case time complexity of the following code:int findMinPath(vector &V, int r, int c) { int R = V.size(); int C = V[0].size(); if (r >= R || c >= C) return 100000000; // Infinity if (r == R - 1 && c == C - 1) return 0; return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1)); } Assume R = V.size() and C = V[0].size(). O(2^(R + C)) O(R*C) O(R + C) O(R*R + C*C) O(R*.. 더보기
GCD_CMPL In the following C++ function, let n >= m. int gcd(int n, int m) { if (n%m ==0) return m; if (n 0) { n = n%m; swap(n, m); } return n; } What is the time complexity of the above function assuming n > m? Θ(logn) Ω(n) Θ(loglogn) Θ(sqrt(n))Good solution:https://www.youtube.com/watch?v=pqivnzmSbq4Euclidean algorithm 더보기
CHOOSE1 CHOOSE1BookmarkSuggest EditWhich of the following is not bounded by O(n^2)? (15^10) * n + 12099 n^1.98 n^3 / (sqrt(n)) (2^20) * nGood solution:The big O gives an upper bound. It doesn’t have to be tight - just means the function won’t exceed it for n > some constant. In this case O(n^2) serves as an upper bound for a, b and d. Functions a and d are linear - more to the order of O(n). Function b .. 더보기
LOOP_CMPL2 What is the time complexity of the following code : int i, j, k = 0; for (i = n/2; i 더보기
NESTED_CMPL3 What is time complexity of following code : int count = 0; for (int i = N; i > 0; i /= 2) { for (int j = 0; j 더보기

티스토리툴바