## Adobe Interview Question for Interns

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

solution O(n*lg(n)) time O(n) space:
1) iterate j from 0 to n-1
2) maintain a vector, e.g dp. That vector gets extended if element a[j] is smaller than
last element of vector
3) if element doesn't get extended, binary search in vector for the element that is smaller
than a[j] it's index will be i, max on j-i

``````#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// returns index of largest element < value in a[dp[i]]
int largest_smaller_idx(const vector<int>&a, const vector<int>& dp, int value)
{
int l = 0;
int r = dp.size() + 1;
while (l + 1 < r) {
int m = (l + r - 2) / 2;
if (a[dp[m]] < value) {
r = m + 1;
} else {
l = m + 1;
}
}
return l;
}

int max_dist_larger_right(const vector<int>& a)
{
if (a.size() < 2) return -1;

int max_d = -1;
vector<int> dp(1, 0);
for (int j = 1; j < a.size(); ++j) {
if (a[j] < a[dp.back()]) {
dp.push_back(j);
} else if (a[j] > a[dp.back()]) {
int i = largest_smaller_idx(a, dp, a[j]);
max_d = max(j - dp[i], max_d);
}
}
return max_d;
}

int main()
{
cout << "TC1: " << (max_dist_larger_right({ 9, 11, 7, 8, 3, 6, 6, 11, 9, 8, 7 }) == 7) << endl;
cout << "TC2: " << (max_dist_larger_right({ 1, 2 }) == 1) << endl;
cout << "TC3: " << (max_dist_larger_right({ 1, 2, 1 }) == 1) << endl;
cout << "TC4: " << (max_dist_larger_right({ 1, 1, 2, 1 }) == 2) << endl;
cout << "TC5: " << (max_dist_larger_right({ 1, 2, 1, 3 }) == 3) << endl;
cout << "TC6: " << (max_dist_larger_right({ 9, 8, 1, 2, 1, 2, 1, 3, 2, 1, 0 }) == 6) << endl;
cout << "TC7: " << (max_dist_larger_right({ 1, 1 }) == -1) << endl;
cout << "TC8: " << (max_dist_larger_right({ 2, 1 }) == -1) << endl;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Variant of Longest Increasing Subsequence problem.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.