Amazon.com

  www.amazon.com
Work in HR? Unlock Free Profile

Amazon.com Senior Software Engineer Interview Question

I interviewed in Seattle, WA and was asked:
"given a large array of int return the length of the longest increasing(non-necessarily-adjacent) sub-sequence"
Add Tags [?]
Answer

Part of a Senior Software Engineer Interview Review - one of 4,774 Amazon.com Interview Reviews

Answers & Comments

0
of 1
vote

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
of 4
votes

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
of 0
votes

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

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.