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

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