Amazon.com

  www.amazon.com
  www.amazon.com

Interview Question

Senior Software Engineer Interview Seattle, WA

given a large array of int return the length of the longest

  increasing(non-necessarily-adjacent) sub-sequence
Answer

Interview Answer

3 Answers

0

from random import randint
from pprint import pprint

# Constant bounds on the random numbers generated.
LOWER = 0
UPPER = 100

# Number of items in the array.
n = 10

# For this solution, the array doesn't have to be sorted.
array = [randint(LOWER, UPPER) for index in range(n)]

def find_subsequences(array):
    '''
    Returns a list containing subsequences of array.
    '''
    if len(array):
        # The current item to be sequenced and the resulting subsequences.
        current = array[0]
        results = []

        # Create subsequences of everything after the current item.
        subsequences = find_subsequences(array[1:])

        # Loop over the subsequences and compare.
        stored = False
        for subsequence in subsequences:
            if len(subsequence):
                # There are two possibilities; either the current item goes
                # before the subsequence, or it goes in the middle.
                if current < subsequence[0]:
                    results.append([current] + subsequence)
                    stored = True

                else:
                    # Append the original subsequence.
                    results.append(subsequence)

                    # Check for a subsequence in the middle.
                    for index, item in enumerate(subsequence):
                        # Remove any duplicates.
                        if current == item:
                            stored = True
                            break

                        if current < item:
                            results.append([current] + subsequence[index:])
                            stored = True
                            # Ignore anything smaller.
                            break

        # If the current wasn't stored, then we can start a new
        # subsequenece.
        if not stored:
            results.append([current])

        # Return the new set of subsequences.
        return results

    # The base case.
    return [[]]

pprint(array)
result = find_subsequences(array)
pprint(result)
print 'Max: %i' % max([len(item) for item in result])

llvllatrix on Jun 16, 2012
3

public int findLengthOfIncreasingSubsequence(int[] largeArray){
     /// invalid format checking ie: null, empty ///

     int prev = 0;
     int longest = 0;
     int counter = 0;
     boolean isFirst = true; // having this is to

     for(int i : largeArray) {
           if(isFirst) {
                 isFirst = false;
                 counter = 1;
           } else {
                  if(prev <= i){
                       counter++;
                  } else {
                      counter = 1;
                  }
           }

           if(counter > longest){
                longest = counter;
           }
           prev = i;
     }

   return longest;
}

Sorawit on Oct 25, 2012
0

This is a Maximum Subarray problem.

public class LongestIncreasingSequence {
    public int findLongestIncreasingSequence(int[] arr){
        int[] diff = new int[arr.length - 1];
        for(int i = 0; i < arr.length - 1; i++) {
            diff[i] = arr[i + 1] - arr[i];
        }

        int diffMaxLength = findMaxinumSubarryInLinerTime(diff);
        return diffMaxLength;
    }

    //find maximum subarray
    public int findMaxinumSubarryInLinerTime(int[] arr) {
        int result = arr[0];
        int last = arr[0];

        for (int i = 1; i < arr.length; i++) {
            if (last < 0) {
                last = arr[i];
            } else {
                last = last + arr[i];
            }

            if (result < last)
                result = last;
        }

        return result;
    }

    @Test
    public void test() {
        assertEquals(7, findLongestIncreasingSequence(new int[] {8, 9, 1, 2, 3, 1, 4, 1, 5, 6, 2, 8}));
    }
}

Anonymous on Dec 14, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.