Amazon Interview Question: given a large array of int re... | Glassdoor

## 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 &lt; 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 &lt; 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 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 &lt; 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 &lt; arr.length; i++) {
if (last &lt; 0) {
last = arr[i];
} else {
last = last + arr[i];
}

if (result &lt; 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
0

Very common and good question. I found this post has a pretty insightful analysis

https://goo.gl/88IpQJ

jim on Feb 10, 2017