## Amazon Interview Question

SDE-2s**Team:**Marketplace

**Country:**United States

**Interview Type:**In-Person

```
/**
* Created by akhil on 12/13/2015.
*/
public class FindMaDifference {
public static int findDiff(int[] arr) {
int diff = 0;
int maxDiff = 0;
int first = 0;
int sec = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] - arr[j] > maxDiff) {
maxDiff = arr[i] - arr[j];
first = arr[i];
sec = arr[j];
}
}
}
System.out.println(" first " + first + " " + "sec " + sec);
return maxDiff;
}
public static void main(String args[]) {
int[] arr = {10, 15, 90, 200, 110};
System.out.println(" Maximum diff is " + findDiff(arr));
}
}
```

/**

* Created by akhil on 12/13/2015.

*/

public class FindMaDifference {

public static int findDiff(int[] arr) {

int diff = 0;

int maxDiff = 0;

int first = 0;

int sec = 0;

for (int i = 1; i < arr.length; i++) {

for (int j = 0; j < i; j++) {

if (arr[i] - arr[j] > maxDiff) {

maxDiff = arr[i] - arr[j];

first = arr[i];

sec = arr[j];

}

}

}

System.out.println(" first " + first + " " + "sec " + sec);

return maxDiff;

}

public static void main(String args[]) {

int[] arr = {10, 15, 90, 200, 110};

System.out.println(" Maximum diff is " + findDiff(arr));

}

}

```
/**
* Created by akhil on 12/13/2015.
*/
public class FindMaDifference {
public static int findDiff(int[] arr) {
int diff = 0;
int maxDiff = 0;
int first = 0;
int sec = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] - arr[j] > maxDiff) {
maxDiff = arr[i] - arr[j];
first = arr[i];
sec = arr[j];
}
}
}
System.out.println(" first " + first + " " + "sec " + sec);
return maxDiff;
}
public static void main(String args[]) {
int[] arr = {10, 15, 90, 200, 110};
System.out.println(" Maximum diff is " + findDiff(arr));
}
}
```

```
{ /**
* Created by akhil on 12/13/2015.
*/
public class FindMaDifference {
public static int findDiff(int[] arr) {
int diff = 0;
int maxDiff = 0;
int first = 0;
int sec = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] - arr[j] > maxDiff) {
maxDiff = arr[i] - arr[j];
first = arr[i];
sec = arr[j];
}
}
}
System.out.println(" first " + first + " " + "sec " + sec);
return maxDiff;
}
public static void main(String args[]) {
int[] arr = {10, 15, 90, 200, 110};
System.out.println(" Maximum diff is " + findDiff(arr));
}
}
```

```
void maxDiff(int iArr[n])
{
int max = iArr[0];
int maxIndex =0;
for(int i=0;i<n-1;i++)
{
if(max < iArr[i+1])
{
max = iArr[i+1];
maxIndex = i+1;
}
}
int min = iArr[maxIndex];
for(int i=maxIndex;i<n-1;i++)
{
if(min > iArr[i+1])
min = iArr[i+1];
}
cout << endl<< "max diff is " << max-min;
}
```

```
def maxprofit(prices):
return max(prices) - min(prices)
```

This is O(2N). You can do O(1) with two heaps, but then you must first build up your data as a heap.

Very elegant O(n) solution in python

```
def max_profit(l):
new = []
for i in range(1,len(l)):
new.append(l[i]-l[i-1])
return max_sum(new)
def max_sum(arr):
temp_sum = 0
sumn = 0
for i in arr:
temp_sum += i
temp_sum = max(temp_sum, 0)
sumn = max(sumn, temp_sum)
return sumn
print(max_profit([5, 2, 3, 4, 9, 1, 6, 2]))
```

Brute force solution is to iterate over all future stock values for a given stock value at a time and return max profit. This is O(n^2). But optimal solution is O(n) using dynamic programming.For this we need to scan through array only once. Here is the Java code

```
int [] stockArray = {10,7,9,8,6,4,2,4,6,5,6,4,7,9,8,9,16,15,12,9,10,7};
if(stockArray.length<=1)
return;
Stock stock = new Stock(0,0,0);
Stock prev = new Stock(0,0,0);
for(int i=1;i<stockArray.length;i++)
{
int tempProfit = stockArray[i]-stockArray[stock.getBuy()];
if(tempProfit>stock.getProfit())
{
stock.setSell(i);
stock.setProfit(tempProfit);
}
else if(tempProfit<0)
{
if(stock.getProfit()>prev.getProfit())
{
prev = stock;
}
stock = new Stock(i,i,0);
}
}
if(stock.getProfit()<prev.getProfit())
{
stock = prev;
}
System.out.println("Stock details : buy at "+stockArray[stock.getBuy()]+", sell at "+stockArray[stock.getSell()]+" with profit of "+stock.getProfit());
```

public class Maxdist {

public static int findDiff(List<Integer> list) {

Collections.sort(list);

return (Math.abs(list.get(0).intValue()-list.get(list.size()-1).intValue()));

}

public static void main(String args[]) {

Integer[] arr = {10, 15, 90, 200, 110};

System.out.println(" Maximum diff is " + findDiff(Arrays.asList(arr)));

}

```
public class Maxdist {
public static int findDiff(List<Integer> list) {
Collections.sort(list);
return (Math.abs(list.get(0).intValue()-list.get(list.size()-1).intValue()));
}
public static void main(String args[]) {
Integer[] arr = {10, 15, 90, 200, 110};
System.out.println(" Maximum diff is " + findDiff(Arrays.asList(arr)));
}
```

.

```
public class ShareProfit {
public static void main(String[] args) {
int a[]={90,99,50,66,79,85};
int small=a[0],big=a[0];
for(int i=0;i<a.length;i++){
if(a[i]<small){
small=a[i];
}
if(a[i]>big){
big=a[i];
}
}
System.out.println(" purchase"+big+ " sell "+small+ " profit "+ (big-small));
}
}
```

```
public class ShareProfit {
public static void main(String[] args) {
int a[]={90,99,50,66,79,85};
int small=a[0],big=a[0];
for(int i=0;i<a.length;i++){
if(a[i]<small){
small=a[i];
}
if(a[i]>big){
big=a[i];
}
}
System.out.println(" purchase"+big+ " sell "+small+ " profit "+ (big-small));
}
}
```

Improved time complexity of O(n)

```
public static int findMaxDiff(int[] arr) {
int max = arr[0];
int min = arr[0];
int minIndex = 0;
int maxIndex = 0;
int diff = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
maxIndex = i;
}
if (arr[i] < min) {
min = arr[i];
minIndex = i;
}
if (maxIndex > minIndex && diff < Math.abs(max - min))
diff = max - min;
}
return diff;
}
```

```
a = [5, 6, 1, 4]
def find_max_stock(prices):
max_value = 0
min_index = 0
buy_range = None
for i in xrange(1, len(prices)):
if prices[i] - prices[min_index] > max_value:
max_value = prices[i] - prices[min_index]
buy_range = (min_index, i)
if prices[i] < prices[min_index]:
min_index = i
return buy_range
print find_max_stock(a)
```

- PoWerOnOff December 12, 2015