May A
BAN USER
- 14
0of 2 votes
AnswersYou are given an array A[] of N integers. The array is unsorted, and N integers can take any value from -2,147,483,647 to + 2,147,483,647. You are supposed to find index Q of a pivot point such that, for 0 <= i <= Q, A[i] <= A[Q], and for Q <= j < N, A[Q] <= A[j].
- May A in United States
If no such pivot point exists, you should return -1.
The expected worst case time complexity is O(N), and expected worst case space complexity (in addition to array A) is O(N).| Report Duplicate | Flag | PURGE
Algorithm C - 12
0of 0 votes
AnswersWrite code for computing binomial coefficient. E.g. "n choose k". Additional constraints are if "n choose k" is greater than 1 billion (1000000000), return -1, else return the answer. E.g. "40 choose 20" is > 1 billion, so you should return -1.
- May A in United States
Worse case expected time complexity is O(n * min(k, n-k)), and they had given worst case space complexity too, but I don't remember it.| Report Duplicate | Flag | PURGE
Algorithm C# - 1
0of 0 votes
AnswerYou are given an array A[] of N integers. The array is unsorted, and N integers can take any values from -(2^31) to +(2^31).
- May A in United States
You are required to find index Q of a pivot point, such that for 0 <= i <= Q, A[i] <= A[Q], and for Q <= j < N, A[Q] <= A[j].
The expected time complexity is O(N), and expected additional space requirement complexity is O(N).| Report Duplicate | Flag | PURGE
Algorithm
#import <stdio.h>
int solution(int A[], int N)
{
int minind, maxind;
int max = -2147483647, min = 2147483647;
for (int i = 0; i < N; i++) {
if (A[i] > max) {
max = A[i];
maxind = i;
}
if (A[i] < min) {
min = A[i];
minind = i;
}
}
if (maxind < minind)
return -1;
max = -2147483647; min = 2147483647;
for (int i = 0; i <= minind; i++) {
if (A[i] > max)
max = A[i];
}
for (int i = minind+1; i < N; i++) {
if (A[i] < min)
min = A[i];
}
if (max > min)
return -1;
int q = minind;
for (int i = minind; i <= maxind; i++) {
if (A[i] < max)
q = i+1;
}
return q;
}
int main(int args, char **argv)
{
int A[] = {4,2,2,1,4,6,7,8,9};
printf("%d\n", solution(A, 9));
}
#include <iostream>
using namespace std;
int memoarr[50][50];
int binomial(int n, int k)
{
if (k == 0) {
memoarr[n][0] = 1;
return 1;
} else if (n == k) {
memoarr[n][k] = 1;
return 1;
} else if (memoarr[n][k] > 0) {
return memoarr[n][k];
} else {
int lhs = binomial(n-1, k-1), rhs = binomial(n-1, k);
if (lhs == -1 || rhs == -1)
return -1;
memoarr[n][k] = lhs + rhs;
if (memoarr[n][k] > 1000000000) {
return -1;
}
}
return memoarr[n][k];
}
int main(int args, char **argv)
{
cout << binomial(10,6) << endl;
}
- 10
Repwilliamland1990, Associate at Advent
Gifted in donating shaving cream worldwide. Crossed the country getting my feet wet with the elderly in Salisbury, MD. Have ...
Alternate way is to just compute multiplication of n * (n-1) * (n-2).... (n - max(n-k, k) +1), and factorial of (min(n-k, k))! and do the division of numerator and denimonator. I was not sure which one was expected to be the solution.
- May A November 19, 2013Since they allow some space complexity which was in terms of N*K, I assume that what I have posted is right.
Additionally since their constraint is that if "n choose k" is > 1 billion, return -1, they anyways don't expect memoization array to be greater than 40 x 40.