Google Interview Question for Software Developers

• 0

Country: United States
Interview Type: In-Person

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

Zig Zag subsequence. Variation of increasing subsequence.

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

``````void maxAlternatingSubsequence(int arg[] , int aLength){

if(arg == NULL||aLength == 0 || aLength == 1) return;

// we will store the length of current alternating subsequence here. [ for each index ]
int* results = new int[aLength];

results[0] = 1;

// this will have a value of 0, or 1.
int lastRelation = -1; // 0 < , 1 >

// browse through the entire List.
for(int i=1; i<aLength; i++){

if((arg[i] > arg[i-1] && ( lastRelation == 0 || lastRelation == -1))
||(arg[i] < arg[i-1] && ( lastRelation == 1 || lastRelation == -1))
){
// does not matter just add it.
results[i]=results[i-1]+1;
if(lastRelation == -1){
lastRelation = 1;
}else if(lastRelation == 0) {
lastRelation =1;
}else {
lastRelation = 0;
}
}else {
results[i]=1;
}
}

// get the max out of the list.
for(int i=0; i<aLength; i++){
printf("%d\n",results[i]);
}

}``````

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

``````void maxAlternatingSubsequence(int arg[] , int aLength){

if(arg == NULL||aLength == 0 || aLength == 1) return;

// we will store the length of current alternating subsequence here. [ for each index ]
int* results = new int[aLength];

results[0] = 1;

// this will have a value of 0, or 1.
int lastRelation = -1; // 0 < , 1 >

// browse through the entire List.
for(int i=1; i<aLength; i++){

if((arg[i] > arg[i-1] && ( lastRelation == 0 || lastRelation == -1))
||(arg[i] < arg[i-1] && ( lastRelation == 1 || lastRelation == -1))
){
// does not matter just add it.
results[i]=results[i-1]+1;
if(lastRelation == -1){
lastRelation = 1;
}else if(lastRelation == 0) {
lastRelation =1;
}else {
lastRelation = 0;
}
}else {
results[i]=1;
}
}

for(int i=0; i<aLength; i++){
printf("%d\n",results[i]);
}

}``````

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

``````void maxAlternatingSubsequence(int arg[] , int aLength){

if(arg == NULL||aLength == 0 || aLength == 1) return;

// we will store the length of current alternating subsequence here. [ for each index ]
int* results = new int[aLength];

results[0] = 1;

// this will have a value of 0, or 1.
int lastRelation = -1; // 0 < , 1 >

// browse through the entire List.
for(int i=1; i<aLength; i++){

if((arg[i] > arg[i-1] && ( lastRelation == 0 || lastRelation == -1))
||(arg[i] < arg[i-1] && ( lastRelation == 1 || lastRelation == -1))
){
// does not matter just add it.
results[i]=results[i-1]+1;
if(lastRelation == -1){
lastRelation = 1;
}else if(lastRelation == 0) {
lastRelation =1;
}else {
lastRelation = 0;
}
}else {
results[i]=1;
}
}

for(int i=0; i<aLength; i++){
printf("%d\n",results[i]);
}``````

}

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

Shouldn't max len for {1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 45} be 10?
2- 51 - 50 -60 - 55 -70-68-75-12-45
Problem could be solved using dynamic programming technicue for O(n^2) time complexity.
We define two recursive function rise[i] = Max (fall[j] ) + 1 for j < i
and fall[i] = Max (rise[j] ) + 1 for j < i. rise[i] means length of longest subsequence that end in index i with rise, fall[i] is the opposite. We can store current subsequence in additional memory while we calculate up and fall function.

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

Coudn't edit my previous reply. Hence, adding it as a new post:
Made edits to the code, to remove redundancy

Assumption: the question has a typo in the explanation:
Should be " [a1, a2, a3, ..., ak] where a1 > a2, a2 < a3, a3 > a4, ..." for the graph to look like \/\/\/
Algorithm:
Keep track of a boolean: isLesser. the boolean is relative to current element in consideration
if the sequence is alternating:
a1> a2 => isLesser = false
a2 < a3 => isLesser = true
a3 > a4 => isLesser = false
and so on

Hence for the current pair to be counted in the alternating subsequence, the previous value of isLesser should be the inverse of what the current isLesser is expected to be. If so increment the the length of the subsequence, else
count the length of the currentSubSequence length into the max
Time Complexity: O(n)
Space Complexity: O(1)
Coded in Java:

``````public class Main {

public static void main(String[] args) {

int[] input = {1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 45}; //MaxSubLen:9 (2, 51, 50, 60, 55, 70, 68, 80, 76)
//int[] input = {1, 2, 51, 50, 45, 55, 54, 68, 66, 76, 75, 12, 45}; //MaxSubLen:8 (50, 45, 55, 54, 68, 66, 76, 75)
//int[] input = {1, 2, 3, 4, 5, 6, 70}; //MaxSubLen:2 (1, 2)
//int[] input = {1, 1, 1, 1, 1, 2}; //MaxSubLen: 2 (1, 2)
//int[] input = {3, 3, 3, 3, 3, 2}; //MaxSubLen: 2 (3, 2)
//int[] input = {1, 1, 1, 1, 1, 1}; //MaxSubLen: 1 (1)
//int[] input = {50, 45, 51, 48, 62, 55, 73}; //MaxSubLen:7 (50, 45, 51, 48, 62, 55, 73)
//int[] input = {1, 1, 1, 2, 1, 1, 1}; //MaxSubLen:3 (1, 2, 1)
//int[] input = {2, 2, 2, 1, 2, 2, 2}; //MaxSubLen:3 (2, 1, 2)

boolean isLesser;
int maxLength = 1;
int tmpLength = 1;
int size = input.length;
if (size < 2) {
System.out.println("MaxSubLen: 1");
}

if (input[0] < input[1]) {
isLesser = true;
} else if (input[0] > input[1]) {
isLesser = false;
} else {
isLesser = true;
tmpLength = maxLength = 0;
}

for (int i = 1; i < size - 1; i++) {
boolean isEnd = false;
if (input[i] == input[i + 1]) {
isEnd = true;
isLesser = true;
} else if (input[i] > input[i + 1]) {
if (!isLesser) {
isEnd = true;
}
isLesser = false;
} else {
if (isLesser) {
isEnd = true;
}
isLesser = true;
}

if (!isEnd) {
tmpLength++;

} else {
// we have hit an anomaly in the pattern,
// store the current subsequence length length into max and reset all the values
if (tmpLength > maxLength) {
maxLength = tmpLength;
}

// Reset the values to start again the count
tmpLength = (input[i] == input[i + 1]) ? 0 : 1;
}
}

if (tmpLength > maxLength) {
maxLength = tmpLength;
}

// final Answer is number of elements (which is maxLength+1)
System.out.println("MaxSubLen:" + (maxLength + 1));
}
}``````

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

The idea I got to solve this problem was to use the previous comparation, if they are opposite I continue generating the sub-sequence. Ones I get a subsequence I can skyp lenght-1, I need to start lenght -1 because that can be the starting of the next valid subsequence.

``````public int[] FindLongestAlternatingSequence(int[] a)
{
int maxStart = -1;
int maxEnd = -1;

if (a == null || a.Length < 2)
return new int[0];

int i = 0;
int length = a.Length - 1;
while (i < length)
{
bool equals = a[i] == a[i + 1];
bool curr = a[i] > a[i + 1];
bool prev = !curr;

int start = i;
int j = i;
while (j < length && !equals && curr == !prev)
{
j += 2;
if (j >= length)
break;
prev = curr;
equals = a[j] == a[j + 1];
curr = a[j] > a[j + 1];
}

int end = (j <= a.Length) ? j - 1 : j - 3;
int l = end - start;
if (l > maxEnd - maxStart)
{
maxStart = start;
maxEnd = end;
}

if (l <= 0)
i++;
else
i = end;
}

if (maxStart == -1)
return new int[0];
int n = maxEnd - maxStart + 1;
int[] result = new int[n];
for (int j = 0; j < n; j++)
result[j] = a[j + maxStart];

return result;
}

private void test_Click(object sender, EventArgs e)
{
var a = new int[] { 2, 4, 5, 7, 3, 1, 5, 8, 8, 8, 5, 4, 3, 4, 5, 2, 1, 5, 4, 7, 7 };
var result = FindLongestAlternatingSequence(a);

for (int i = 0; i < result.Length; i+=2)
Console.Write("[" + result[i] + ", " + result[i + 1] + "] - ");
Console.WriteLine();
}``````

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

A typical top-down approach would be to maintain a direction (up/down) in each recursive call to the function that's calculating the longest subsequence.

``````def longestAlternatingSub(soFar: Vector[Int],
direction: Option[Boolean],
s: Vector[Int]): Vector[Int] = {

if (s.isEmpty)
soFar
else {
if (direction.isEmpty) {
val long1 = longestAlternatingSub(soFar :+ firstVal, Some(true), s.tail)
val long2 = longestAlternatingSub(soFar :+ firstVal, Some(false), s.tail)
val long3 = longestAlternatingSub(soFar, None, s.tail)
List(long1, long2, long3).sortBy(_.length).last
}
else if (direction.exists(_ == true) && soFar.lastOption.exists(_ < firstVal)){
val long1 = longestAlternatingSub(soFar :+ firstVal, Some(false), s.tail)
val long2 = longestAlternatingSub(soFar, Some(true), s.tail)
List(long1, long2).sortBy(_.length).last
}
else if (direction.exists(_ == false) && soFar.lastOption.exists(_ > firstVal)) {
val long1 = longestAlternatingSub(soFar :+ firstVal, Some(true), s.tail)
val long2 = longestAlternatingSub(soFar, Some(false), s.tail)
List(long1, long2).sortBy(_.length).last
}
else
Vector.empty
}
}``````

This can be easily memoized, or made a bottom-up dynamic programming solution to save space.

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

Java Code with test cases:

``````public class LongestAlternatingSubsequence
{
private int array[];

LongestAlternatingSubsequence(int[] array)
{
this.array = array;
}

public void setArray(int[] array)
{
this.array = array;
}

int findLongestAlternatingSubSequence()
{
//Null and length checks
if (this.array == null)
{
return -1;
}
int length = this.array.length;

if (length == 0)
{
return -1;
}

//Core logic starts
int from=-1, to=-1;
int tempFrom=-1, tempTo=-1;
for (int i=1; i<length; i++)
{
tempTo=i;

if (i%2 == 1)
{
if (!(this.array[i-1] > this.array[i]) &&  tempTo-tempFrom > to-from)
{
to=tempTo;
from=tempFrom;
tempFrom=i-1;
}
}
else
{
if (!(this.array[i] > this.array[i-1]) &&  tempTo-tempFrom > to-from)
{
to=tempTo;
from=tempFrom;
tempFrom=i-1;
}

}
}
System.out.println("To: " +to+"From: "+from);
}
}

//Test Case:
import org.junit.Test;

import java.util.Arrays;

import static org.junit.Assert.*;

public class LongestAlternatingSubsequenceTest
{
@Test
public void findLongestAlternatingSubSequence() throws Exception
{
LongestAlternatingSubsequence subsequence = new LongestAlternatingSubsequence(null);
assertEquals(-1, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 45});
assertEquals(10, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 11});
assertEquals(10, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 52, 60, 55, 70, 68, 80, 76, 75, 12, 11});
assertEquals(8, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 52, 60, 55, 54, 68, 80, 76, 75, 12, 11});
assertEquals(8, subsequence.findLongestAlternatingSubSequence());
}

}``````

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

``````public class LongestAlternatingSubsequence{

public static int[] getLongestAlternatingSequence(int[] array){
if(array==null || array.length ==1){
return array;
}

int lowIndex,highIndex;
int tempLow=0, tempHigh;

boolean peak=false;
boolean sequenceEnd=false;

if(array[0] >array[1]){
peak = true;
}

for(int i=1; i<array.length;i++){
if(peak){
if(array[i] <array[i-1]){
tempHigh=i;
peak= false;
}
else{
sequenceEnd=true;
}
}
else{
if(array[i] > array[i-1]){
tempHigh=i;
peak=true;
}
else{
sequenceEnd=true;
}
}
if(sequenceEnd){
if(tempHigh-tempLow >= highIndex-lowIndex){
lowIndex= tempLow;
highIndex = tempHigh;
}
tempLow= i;
tempHigh=i;
sequenceEnd=false;

}
}

arraycopy(array, lowIndex, longestaltseq, 0, highIndex-lowIndex);
return longestaltseq;

}

}``````

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

public static void LIS_bottom_up(int[] array,int length)
{
int[] array2 = {4,6,7,3,9,5,7,0,-1,10};
int max = Integer.MIN_VALUE;
int[] tmparray_increase = new int[length+1];
int[] tmparray_decrease = new int[length+1];
for(int i=0;i<=length;i++)
{
tmparray_increase[i]=1;
tmparray_decrease[i]=1;
for(int j=0;j<=i;j++)
{
if(array[j]<array[i])
{
tmparray_increase[i]=Math.max(tmparray_increase[i], tmparray_decrease[j]+1);
}
if(array[j]>array[i])
{
tmparray_decrease[i]=Math.max(tmparray_decrease[i], tmparray_increase[j]+1);
}
}
max = Math.max(max, Math.max(tmparray_increase[i],tmparray_decrease[i]));
}
for(int i=0;i<=length;i++)
{
System.out.print(tmparray_increase[i]+"\t");
}
System.out.print("\n");
for(int i=0;i<=length;i++)
{
System.out.print(tmparray_decrease[i]+"\t");
}
System.out.println("Max = "+max);
}

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

``````List<startEnd> sequences = new ArrayList<startEnd>();
boolean sequenceRunning = false;
int start = -1, end = 0;
int next=0;//0=>, 1=<

Integer a[] = { 6, 7, 1, 9, 4, 3, 2, 5 };// new Integer[10];
Integer b[]= new Integer[a.length - 1];
//		reArrangeOrder(a);
for (int i = 0; i < a.length - 1; i++) {
b[i] = a[i+1] - a[i];
}
for (int i = 0; i < b.length; i++) {
if(b[i]<0){
b[i] = 0;
}
else{
b[i] = 1;
}
}
//previous code subtract a[i] from a[i+1] after which if a[i] is >0 then puts 1 else 0
printArray(b);
for (int i = 0; i < b.length; i++) {
if((i+1) < b.length && b[i] != b[i+1])
{
//continue the sequence
if(start == -1){
start = i;
}
}
else{
end =i+1;
if(start !=-1)
{
}
start = -1;
}
}
//previous code tells the start and end index of alternating 1,0
printList(sequences);//this method prints the start and end index of the subsequences which justify the order><><><>``````

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

``````List<startEnd> sequences = new ArrayList<startEnd>();
boolean sequenceRunning = false;
int start = -1, end = 0;
int next=0;//0=>, 1=<

Integer a[] = { 6, 7, 1, 9, 4, 3, 2, 5 };// new Integer[10];
Integer b[]= new Integer[a.length - 1];
//		reArrangeOrder(a);
for (int i = 0; i < a.length - 1; i++) {
b[i] = a[i+1] - a[i];
}
for (int i = 0; i < b.length; i++) {
if(b[i]<0){
b[i] = 0;
}
else{
b[i] = 1;
}
}
//previous code subtract a[i] from a[i+1] after which if a[i] is >0 then puts 1 else 0
printArray(b);
for (int i = 0; i < b.length; i++) {
if((i+1) < b.length && b[i] != b[i+1])
{
//continue the sequence
if(start == -1){
start = i;
}
}
else{
end =i+1;
if(start !=-1)
{
}
start = -1;
}
}
//previous code tells the start and end index of alternating 1,0
printList(sequences);//this method prints the start and end index of the subsequences which justify the order><><><>``````

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

``````using System;
using System.Collections.Generic;
using System.Linq;

namespace Ed1
{
public class Program
{
public static void Main(string[] args)
{
List<int> values = new List<int>(args.Length);

foreach (string arg in args)

int resultPosition = 0;
int resultLength = 0;

FindSequence(values, ref resultPosition, ref resultLength);

string result = "";

for (int i = resultPosition; i < resultPosition + resultLength; i++)
result = result + values[i] + " ";

Console.WriteLine(result);
}

public static void FindSequence(IList<int> values, ref int resultPosition, ref int resultLength)
{
resultLength = 0;
resultPosition = 0;
int position = 0;

while (position < values.Count())
{
int length = SequenceLength(values, position);

if (length > resultLength)
{
resultLength = length;
resultPosition = position;
}

position = position + length;
}
}

static int SequenceLength(IList<int> values, int start)
{
if (start < 0 || start >= values.Count())
throw new IndexOutOfRangeException("start");

if (start == values.Count() - 1)
return 1;

if (values[start] == values[start + 1])
return 1;

int i = start + 2;

while
(
i < values.Count() &&
(
values[i - 2] < values[i - 1] &&
values[i] < values[i - 1]
||
values[i - 2] > values[i - 1] &&
values[i] > values[i - 1]
)
)
i = i + 1;

return i - start;
}
}
}``````

``````using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Ed1;

namespace Ed1UnitTest
{
[TestClass]
public class UnitTest
{
[TestMethod]
public void TestMethod1()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = {1};

Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);

Assert.AreEqual(resultPosition, 0);
Assert.AreEqual(resultLength, 1);
}

[TestMethod]
public void TestMethod2()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = { };

Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);

Assert.AreEqual(resultPosition, 0);
Assert.AreEqual(resultLength, 0);
}

[TestMethod]
public void TestMethod3()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = {0, 2 };

Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);

Assert.AreEqual(resultPosition, 0);
Assert.AreEqual(resultLength, 2);
}

[TestMethod]
public void TestMethod4()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = {-1, -1, 4, 2, 5,  3, 2, 5, 0};

Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);

Assert.AreEqual(resultPosition, 1);
Assert.AreEqual(resultLength, 5);
}

[TestMethod]
public void TestMethod5()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = { -1, -1, 4, 2, 5, 3 };

Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);

Assert.AreEqual(resultPosition, 1);
Assert.AreEqual(resultLength, 5);
}
}
}``````

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

Here's an O(n) solution:
public static int longestAltSeqStart(int [] input)
{
if (input == null || input.length == 1) // must be 2 or more to have alternating?
{
return -1;
}

int resultIndex = 0;
int curAltIndex = 0;
int lastAltLength = 1;
int curAltLength = 1;
int lastDirection = input[1] - input[0]; // increase (+), decrease (-), neither (0)
for (int i = 1; i < input.length - 1; i++)
{
int curDir = input[i + 1] - input[i];
if (curDir == 0) // end of a seq
{
if (curAltLength > lastAltLength)
{
resultIndex = curAltIndex;
lastAltLength = curAltLength;

System.out.println("L1: " + lastAltLength);
}
curAltLength = 0;

curAltIndex = -1;
System.out.println("Index: " + curAltIndex);
}
else if (lastDirection == 0 || sameDir(curDir, lastDirection)) // end of seq, start of new seq
{
if (curAltLength > lastAltLength)
{
resultIndex = curAltIndex;
lastAltLength = curAltLength;

System.out.println("L2: " + lastAltLength);
}
curAltLength = 1;

curAltIndex = i;
System.out.println("Index: " + curAltIndex);
}
else // continuing seq
{
curAltLength++;
}

lastDirection = curDir;
}

System.out.println("R Index: " + resultIndex);
System.out.println("R Length: " + lastAltLength);

return resultIndex;
}

public static boolean sameDir(int dir1, int dir2)
{
return (dir1 < 0 && dir2 < 0) || (dir1 > 0 && dir2 > 0);
}

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

``````enum direction {
Up, Down, NoChange
};
size_t LongestAlternatingSubSequence(const vector<long>& data, vector<long>& result)
{
map<size_t, size_t> sequences;
direction direction = NoChange, flag = NoChange;
size_t count = 0, start = 0, index = 0;
if (data.size() > 1) {
for (vector<long>::const_iterator it = data.begin() + 1; it != data.end(); it++, index++) {
flag = *it > *(it - 1) ? Up : *it < *(it -1 ) ? Down : NoChange;
if (flag != direction) {
count++;
direction = flag;
} else {
direction = NoChange;
if (sequences.find(index - start) == sequences.end())
sequences.emplace(index - start, start);
start = index;
}
}
}
if (sequences.size() > 0)
for (size_t i = 0; i <= sequences.rbegin()->first; i++)
result.push_back(data[i + sequences.rbegin()->second]);
return result.size();
}``````

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

A lot of the other answers were very dense and lacking comments. Additionally, the solutions were brittle to maintenance or changing requirements. Here is a solution that might be found in a real application.

``````import java.util.*;
import java.lang.*;
import java.io.*;

class LongestAlternatingSubsequence
{
public static void main (String[] args) throws java.lang.Exception
{
int[] numbers = new int[]{1,2,3,2,5,8};

int[] longestSubsequence = findLongest(numbers);
System.out.println(Arrays.toString(longestSubsequence));
}

private static int[] findLongest(int[] numbers) {
// For empty or single elemnt lists, the whoe list is the answer
if (numbers.length < 2) {
return numbers;
}

// Track the lonst sequence seen so far, and the list of sequences
// still under consideration
Sequence longest = null;
List<Sequence> activeSequences = new ArrayList();

for (int i=0;i<numbers.length;i++) {
int current=numbers[i];

// Track the sequences that survive the newly seen number
List<Sequence> nextSequences = new ArrayList();

// For every active sequence, evaluate whether the newly seen
// number breaks or continues the chain
for (Sequence sequence : activeSequences) {
Sequence nextSequence = sequence.considerNext(current);
if (nextSequence != null) {
// If the chain continues, then add it to the collection
// of sequences to keep watching
} else {
// If the chain is broken, then check to see if it was a
// new longest chain seen
if (longest == null || longest.length < sequence.length) {
longest = sequence;
}
}
}

// For every element in the list, a new sequence is started with
// the possibility of the next number being smaller or larger

// Keep only the sequences that are unbroken for the next
// loop iteration
activeSequences = nextSequences;
}

// After all elements in the list are considered, evaluate all active
// sequences to see if the longest is in the list
for (Sequence sequence : activeSequences) {
if (longest == null || longest.length < sequence.length) {
longest = sequence;
}
}

// Using the longest sequence seen, find the substring of elements that
// represents the longest alternating substring
return Arrays.copyOfRange(numbers, longest.startIndex, longest.startIndex+longest.length);
}

}

/**
* Track an active sequence and provide a method of evaluating a new element to
* see if the sequence has been broken or should be continued. In a performance
* critical application, this logic could be rolled into the loops above, but
* in a practical application keeping is separate allows each substitution of
* new subsequence rules.
*/
class Sequence {
int length;
int startIndex;
int last;
boolean expectLarger;

public Sequence(int startIndex, int length, int last, boolean expectLarger) {
this.length = length;
this.startIndex = startIndex;
this.last = last;
this.expectLarger = expectLarger;
}

public Sequence considerNext(int next) {
if (this.expectLarger) {
if (next > this.last) {
return new Sequence(this.startIndex, this.length+1, next, !this.expectLarger);
} else {
return null;
}
} else {
if (next < this.last) {
return new Sequence(this.startIndex, this.length+1, next, !this.expectLarger);
} else {
return null;
}
}
}
}``````

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

``````void getLongestAlternatingSequence(const vector<int>& a, int& start, int& end) {
start=end=-1;		// init output with -1
if (a.size()==0 || a.size()==1) {
return;	// error handling
}

for (int _start=0, _end=0; _start<a.size()-1; ++_start) {
continue;
}

_end =_start+1;	// start of candidate sequence
while( ( (_end+1) < a.size() ) &&  (a[_end]>a[_end-1]) ? (a[_end+1]<a[_end]) : (a[_end+1]>a[_end]) {
_end++;		// continue accumulating current alternating sequence
}

if ((end-start) < (_end-_start)) {	// update outputs if longer sequence found
start=_start;
end=_end;
}
_start=_end;	// reset start position of next candidate alt sequence
}

}``````

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

``````void getLongestAlternatingSequence(const vector<int>& a, int& start, int& end) {
start=end=-1;		// init output with -1
if (a.size()==0 || a.size()==1) {
return;	// error handling
}

for (int _start=0, _end=0; _start<a.size()-1; ++_start) {
continue;
}

_end =_start+1;	// start of candidate sequence
while( ( (_end+1) < a.size() ) &&  (a[_end]>a[_end-1]) ? (a[_end+1]<a[_end]) : (a[_end+1]>a[_end]) {
_end++;		// continue accumulating current alternating sequence
}

if ((end-start) < (_end-_start)) {	// update outputs if longer sequence found
start=_start;
end=_end;
}
_start=_end;	// reset start position of next candidate alt sequence
}

}``````

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

int longestIncreasingSeq(int a[], int aSize)
{
int* increasingSeq = new int[aSize];
int* decreasingSeq = new int[aSize];

for (int index = 0; index < aSize; index++)
{
increasingSeq[index] = 0;
decreasingSeq[index] = 0;
}
decreasingSeq[0] = -1;

for (int index = 1; index < aSize; index++)
{
if (a[index] > a[index -1])
{
increasingSeq[index ] = decreasingSeq[index - 1]+ 1;
}
else if (a[index] < a[index - 1])
{
decreasingSeq[index] = increasingSeq[index - 1] + 1;
}
cout << increasingSeq[index] << ":" << decreasingSeq[index]<<endl;
}

int maxIncreasingSeq = 0;
for (int index = 0; index < aSize; index++)
{
if (maxIncreasingSeq < increasingSeq[index])
{
maxIncreasingSeq = increasingSeq[index];
}
if (maxIncreasingSeq < decreasingSeq[index])
{
maxIncreasingSeq = decreasingSeq[index];
}
}
return maxIncreasingSeq;
}

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

``````int longestIncreasingSeq(int a[], int aSize)
{
int* increasingSeq = new  int[aSize];
int* decreasingSeq = new  int[aSize];

for (int index = 0; index < aSize; index++)
{
increasingSeq[index] = 0;
decreasingSeq[index] = 0;
}
decreasingSeq[0] = -1;

for (int index = 1; index < aSize; index++)
{
if (a[index] > a[index -1])
{
increasingSeq[index ] = decreasingSeq[index - 1]+ 1;
}
else if (a[index] < a[index - 1])
{
decreasingSeq[index] = increasingSeq[index - 1] + 1;
}
cout << increasingSeq[index] << ":" << decreasingSeq[index]<<endl;
}

int maxIncreasingSeq = 0;
for (int index = 0; index < aSize; index++)
{
if (maxIncreasingSeq < increasingSeq[index])
{
maxIncreasingSeq = increasingSeq[index];
}
if (maxIncreasingSeq < decreasingSeq[index])
{
maxIncreasingSeq = decreasingSeq[index];
}
}
return maxIncreasingSeq;
}``````

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

Test

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

``Test``

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

Solution in C++

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

typedef std::vector<int> vec_t;

int
findMax(vec_t& aVec) {
int lMax  = 0;
for(int i = 0; i < aVec.size(); ++i)
if (aVec[i] > lMax) lMax = aVec[i];
return lMax;
}

void
print(vec_t& aVec) {
for(auto& a : aVec)
std::cout << a << ' ';
std::cout << std::endl;
}

int
maxZigZag(vec_t& aVec) {
vec_t pos(aVec.size(),1);
vec_t neg(aVec.size(),1);

for(int i = 1; i < aVec.size(); ++i) {
for(int j = 0; j <= i-1; ++j) {
if(aVec[i] - aVec[j] > 0) {
pos[i] = std::max(neg[j]+1, pos[i]);
} else if (aVec[i] - aVec[j] < 0) {
neg[i] = std::max(pos[j]+1, neg[i]);
}
}
}

int l1 =  findMax(pos);
int l2 =  findMax(neg);

/* print(pos); print(neg); */
return std::max(l1, l2);
}``````

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

My solution has O(n) complexity - it goes through the array only once, and what is does is keep track of 2 elements before the current one, and check on the sign of the difference between the current element and the previous multiplied by the difference between the previous and the pre-previous element. The result of this multiplication needs to be negative for the sequence of 3 elements currently assessed (crt elem, previous, pre-previous) to be alternative. And then it reports the maximum length.

# The code assumes that the array has a length >= 2
def find_largest_alt_seq(array):
max = 0
crt_len = 2
prev = array[1]
prev_prev = array[0]
for elem in array[2:]:
if (elem - prev) * (prev - prev_prev) < 0:
crt_len += 1
else:
if crt_len > 0:
if max < crt_len:
max = crt_len
crt_len = 0
prev_prev = prev
prev = elem
if crt_len > 0 and max < crt_len:
max = crt_len
return max

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

``````def find_largest_alt_seq(array):
max = 0
crt_len = 2
prev = array[1]
prev_prev = array[0]
for elem in array[2:]:
if (elem - prev) * (prev - prev_prev) < 0:
crt_len += 1
else:
if crt_len > 0:
if max < crt_len:
max = crt_len
crt_len = 0
prev_prev = prev
prev = elem
if crt_len > 0 and max < crt_len:
max = crt_len
return max``````

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

1) Insert All Elements in min Heap.
2) start filling every other element in the array going forward, while popping elements from heap.
3) fill every other elements going backwards

Example:

Input: 3,1,4,2,5

First pass: 1, ,2, ,3
Second Pass: 1,5,2,4,3

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.