## Amazon Interview Question

Country: United States

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

Here is an O(n) solution;

Suppose the array is A = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
The longest biotonic sequence would be the sequence {0, 8, 12, 14, 13, 11, 7} of size 7

Motivation:
The solution is a variant of of LIS (Longest Increasing Subsequence) problem.

Idea:
We need to construct two arrays lis[] and lds[] using Dynamic Programming solution of LIS problem.

lis[i] : stores the length of the Longest Increasing subsequence ending with arr[i].
lds[i]: stores the length of the longest Decreasing subsequence starting from arr[i].

Finally, we need to return the max value of (lis[i] + lds[i] – 1) where i is from 0 to n-1. Keep the marker to the elements being chosen to be used to output the subsequence later.

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

1) Create a bool array equal to the size of the input array.
2) Traverse the input array and mark the bool array to
a) 1 if input array is increasing(a[i] > a[i-1])
b) 0 if input array is decreasing (a[i] < a[i-1])
c) Previous bool bit value if non increasing or nondecreasing
3) Now loop through the bit array to find longest sequence of 1 1 .......0.

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

An O(n) approach:

void LongestBitonic(int a[], int n)
{
int start, begin, max=-1,flag=0,i,end;

try
{
if(a==NULL || n<3) throw "\nInvalid Entry\n";
}catch(const char *s)
{
puts(s);
return;
}

for(i=0;i<n;i++)
{
if(a[i]+1==a[i+1] || a[i]-1==a[i+1] || ((a[i]<a[i+1] && (a[i+1]>a[i] && a[i+1]>a[i+2]) && flag!=0)))
{
if(flag==0)
{
flag=1;
begin=i;
}
}
else
{
if(flag!=0)
{
if(i-begin>max)
{
max=i-begin;
start=begin;
end=i;
}
}
flag=0;
}
}
for(i=start;i<start+max;i++)
cout<<a[i]<<"\t";
cout<<endl;
}

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

what is bitonic sequence?

Comment hidden because of low score. Click to expand.
0

A sequence is bitonic if it monotonically increases and then monotonically de- creases, or if it can be circularly shifted to monotonically increase and then monotonically decrease. For example the sequences (1, 4, 6, 8, 3, −2) , (9, 2, −4, −10, −5) , and (1, 2, 3, 4) are bitonic, but (1, 3, 12, 4, 2, 10) is not bitonic.

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

LOGIC:
1. Traverse the array forwards, wrapping around when you hit the end (code below)
2. Count the total number of inflection points you find, if num_inflection_points==2 then your array is bitonic.
3. The runtime of this should be O(n).

-

Here's a working example in c++:

bool is_bitonic(const vector<int>& v) {
bool was_decreasing = v.back() > v.front();
int num_inflections = 0;
for (int i = 0; i < v.size() && num_inflections <= 2; i++) {
bool is_decreasing = v[i] > v[(i+1)%v.size()];
// Check if this element and next one are an inflection.
if (was_decreasing != is_decreasing) {
num_inflections++;
was_decreasing = is_decreasing;
}
}
return 2 == num_inflections;
}

Note 1: Here's the basic idea for traversing an array circularly:

for (int i = ip_index; i < array_length; i++) {
int index = (i + 1) % array_length;  // wraps around to beginning
// Retrieve the value with
DoSomethingWithValue(array[index];)
}

Note 2: It might simplify the code to circularly loop length + 1 elemnts, which will guarantee you find both inflection points.

Note 3: Or, it might simplify the code if you always look for the first inflection point that goes increasing to decreasing (before searching for other inflection points). That way, your scan only has to take worry about finding exactly one other inflection point with the opposite flip.

source : stackoverflow.com/a/3029129/1923790

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

void LongestBitonic(int a[], int n)
{
int start, begin, max=-1,flag=0,i,end;
int increase=0;
int decrease=0;
try
{
if(a==NULL || n<=0) throw "\nInvalid Entry\n";
}catch(const char *s)
{
puts(s);
return;
}

if(n==1 || n==2)
cout<<"\nLength"<<n<<" : Entire vector is the longest Bitonic\n";
for(i=0;i<n;i++)
{
if(a[i]<=a[i+1] && increase==0)
{
if(flag==0)
{
increase=1;
flag=1;
begin=i;
}
}
else if(a[i]<=a[i+1] && increase==1 && decrease==0)
continue;
else if(a[i]>=a[i+1] && increase==1)
{
if(decrease==0)
decrease=1;
continue;
}

else
{
if(flag==1)
{
if(i-begin>max)
{
max=i-begin;
start=begin;
end=i;
}
i--;
}
increase=0;
decrease=0;
flag=0;
begin=-1;
}
}
for(i=start;i<=end;i++)
cout<<a[i]<<"\t";
cout<<endl;
}

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

From Stack Overflow
A bitonic sequence:

/\
/ \
\/
Not a bitonic sequence:

/\
/ \ / (higher than start)
\/
Obviously if the direction changes more than two times we cannot have a bitonic sequence.
If the direction changes less than two times, we must have a bitonic sequence.

If there are two changes in direction, we MAY have a bitonic sequence. Consider the two ascii images above. Clearly a sequence with two changes in direction will match one of the patterns (allowing for a reflection). Thus, we set the initial direction by comparing the first and last elements. Since these can be the same, we use the first element that is not equal to the last element.

Here is an implementation in Java:

public static Boolean bitonic(int[] array) {
if (array == null) return false;
if (array.length < 4) return true;
Boolean dir;// false is decreasing, true is increasing
int pos = 0, switches = 0;
while (pos < array.length) {
if (array[pos] != array[array.length - 1])
break;
pos++;
}
if (pos == array.length) return true;
//pos here is the first element that differs from the last
dir = array[pos] > array[array.length - 1];
while (pos < array.length - 1 && switches <= 2) {
if ((array[pos + 1] != array[pos]) &&
((array[pos + 1] <= array[pos]) == dir)) {
dir ^= true;
switches++;
}
pos++;
}
return switches <= 2;
}

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

finding the maximum length of a bitonic subsequence as a reference:

int find_max_bitonic_len(int a[], int n)
{
int i, j, k, l, maxl;

l = maxl = 0;

i = 0;

while (i < n) {
//finds possible heads of bitonic subsequences
while (i < n - 1 && a[i + 1] < a[i]) i++;
if (i == n - 1) return maxl;

//monotonic increasing
j = i;
while (j < n - 1 && a[j + 1] >= a[j]) j++;
if (j == n - 1) return maxl;

//monotonic decreasing
k = j;
while (k < n - 1 && a[k + 1] <= a[k]) k++;

l = k - i + 1;
if (l > maxl) maxl = l;

i = k;
}

return maxl;
}

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

What do you mean by WAP?
Here's my attempt for printing the longest bitonic sequence, it has a small bug when the longest bitonic sequence is preceded by many equal integers.

public class Bitonic {
private enum ParseState {
Ascending,
Descending
}

public static String PrintLongest(int[] input) {
String result = "";
String candidate = "";

ParseState state = ParseState.Ascending;

// we need at least 3 integers to satisfy bitonic criteria
assert input.length >= 3;
candidate += String.valueOf(input[0]);

for (int i = 1; i < input.length; i++) {
if ((input[i-1] <= input[i] && state == ParseState.Ascending) ||
(input[i-1] >= input[i] && state == ParseState.Descending))
candidate += "," + input[i];
else if (input[i-1] > input[i] && state == ParseState.Ascending)
{
candidate += "," + input[i];
state = ParseState.Descending;
}
else if (input[i-1] < input[i] && state == ParseState.Descending)
{
// is this candidate longer than the current best?
if (candidate.length() > result.length())
result = candidate;

// now start building the next one
candidate = input[i-1] + "," + input[i];
state = ParseState.Ascending;
}
}

// if we aren't currently descending then the current candidate doesn't work
if (state == ParseState.Descending) {
if (candidate.length() > result.length())
result = candidate;
}

return result;
}
}

Comment hidden because of low score. Click to expand.
0

WAP -> Write a Program

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.