Google Interview Question for Software Developers


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.

- xeq March 19, 2016 | Flag Reply
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]);
    }
    
}

- Ravinder March 20, 2016 | Flag Reply
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]);
    }
    
}

- Anonymous March 20, 2016 | Flag Reply
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]);
    }

}

- Ravinder March 20, 2016 | Flag Reply
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.

- EPavlova March 20, 2016 | Flag Reply
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));
    }
}

- burnYourBrain March 20, 2016 | Flag Reply
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();
}

- hnatsu March 22, 2016 | Flag Reply
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 {
      val firstVal = s.head
      if (direction.isEmpty) {
        // start with first increasing
        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.

- Anonymous March 23, 2016 | Flag Reply
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);
        return to - 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());
    }

}

- SHR March 24, 2016 | Flag Reply
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;
		

	}








}

- matt.jackson1294 March 25, 2016 | Flag Reply
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);
}

- abc_abc March 26, 2016 | Flag Reply
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)
				{
					sequences.add(new startEnd(start, end));
				}
				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><><><>

- Ishupreet Singh March 28, 2016 | Flag Reply
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)
				{
					sequences.add(new startEnd(start, end));
				}
				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><><><>

- Ishupreet Singh March 28, 2016 | Flag Reply
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)
                values.Add(int.Parse(arg));

            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);
        }
    }
}

- 7orlum March 31, 2016 | Flag Reply
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);
}

- nghi1129 April 01, 2016 | Flag Reply
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();
}

- funcoolgeek April 03, 2016 | Flag Reply
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
	{
		// your code goes here
		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
					nextSequences.add(nextSequence);
				} 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
			nextSequences.add(new Sequence(i, 1, current, true));
			nextSequences.add(new Sequence(i, 1, current, false));
			
			// 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;
			}			
		}
	}
}

- matt.lavin April 09, 2016 | Flag Reply
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) {
		if(a[_start]==a[_start+1]){	// skip adjacent duplicates
			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
	}

}

- vandu May 05, 2016 | Flag Reply
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) {
		if(a[_start]==a[_start+1]){	// skip adjacent duplicates
			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
	}

}

- vandu May 05, 2016 | Flag Reply
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;
}

- Jay May 06, 2016 | Flag Reply
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;
}

- Jay May 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

- Test May 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

- Test May 06, 2016 | Flag Reply
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); 
}

- fiska May 31, 2016 | Flag Reply
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

- Anonymous July 30, 2016 | Flag Reply
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

- IrinaGabriela July 30, 2016 | Flag Reply
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

- AJ March 19, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More