Amazon Interview Question
Country: United States
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.
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;
}
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.
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;
}
Notes, depending on your implementation:
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
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;
}
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;
}
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;
}
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;
}
}
Here is an O(n) solution;
- zahidbuet106 December 16, 2013Suppose 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.