Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
Java Implementation for the above..
package ArrayImpl;
public class FindNumbersWithProperties {
public static void main(String[] args) {
int a[] = {5,3,4,6,7,9,3,2,1,5,8};
int min_no_index_so_far = 0;
int max_no_index_so_far = 0, min_no_temp_index_so_far = 0;
int min_no_so_far = a[0];
int max_diff_so_far = Integer.MIN_VALUE;
for (int i = 1 ; i < a.length; i++)
{
if((a[i] - min_no_so_far) > max_diff_so_far)
{
max_diff_so_far = a[i] - min_no_so_far;
max_no_index_so_far = i;
min_no_index_so_far = min_no_temp_index_so_far;
}
if(a[i] < min_no_so_far)
{
min_no_so_far = a[i];
min_no_temp_index_so_far = i;
}
}
System.out.println(max_no_index_so_far + " > " + min_no_index_so_far);
System.out.println(a[max_no_index_so_far] + " > " + a[min_no_index_so_far]);
System.out.println(max_diff_so_far);
}
}
Go through the array from the beginning, for each step pushing the current minimum onto the stack. Then go through the array from the back, at each step checking the current value minus the minimum value, and popping off the stack as you go towards the first element. If the current value minus the minimum is positive and the largest value so far, store it as the max.
O(N) for generating the minimum stack and O(N) for array traversal so O(N) all up.
import java.util.Stack;
public class FindMaxMin {
/**
* @param args
*/
public static void main(String[] args) {
int [] arr = {20,19,18,17,16,16,16,30,17,25,20};
findMaxMin(arr);
}
public static void findMaxMin(int [] arr)
{
Stack <Integer> minStack = new Stack();
Stack <Integer> minAt= new Stack();
int curMin = Integer.MAX_VALUE;
int curMinAt = -1;
for(int i = 0; i < arr.length-1; i++)
{
if(arr[i] < curMin)
{
curMin = arr[i];
curMinAt = i;
}
minStack.push(curMin);
minAt.push(curMinAt);
}
int curMaxSum = Integer.MIN_VALUE;
int curMaxAt = -1;
for(int i = arr.length-1; i >= 1; i--)
{
if(arr[i] - minStack.peek() > curMaxSum)
{
curMaxSum = arr[i] - minStack.peek();
curMaxAt = i;
curMinAt = minAt.peek();
}
minStack.pop();
minAt.pop();
}
if(curMaxAt != -1)
System.out.println("Max: " + curMaxSum + " from " + arr[curMaxAt] + " - " + arr[curMinAt]);
else
System.out.println("No max");
}
}
It is always better to explain using dryruns:
{20,19,18,17,16,16,16,30,17,25,20};
a. start traversing from 0 to rightmost index and put the minimum found til now in stack.So we put numbers in the stack as below:
topmost bottomost
16 16 16 16 16 16 16 17 18 19 20
so 16 is the least.
b.Start traversing from rightmost to leftmost in the array and subtract the array element with topmost element of the stack at each step as below:
20 - 16 = 4
25 - 16 = 9
-
-
30-16 = 14
-
-
-
20 - 20 = 0
so greatest is 14 and we have the answer.
Upvoting this answer.
For your solution, the time complexity is O(N) + O(N) i.e 2N right? Please explain me if I'm wrong.
suppose you are comparing the numbers in pairs so you get a max of the two for each pair proceeding like this save the max and min at every step... you will need n-1 comparisons to get the max continuing in same manner by comparing winners at each stage. Since you saved the min values in first iteration you have saved n/2 comparisons, second now the min value can be one from the numbers that were left out when we were searching for max so that counts another logn comparisons so in all you will have
n-1+n/2+logn or 3n/2+logn-1 comparisons in best case
i missed the i and j condition, yes it can be solved in a single pass in O(n) starting from end and keeping track of the diff and max values...
suppose the array is A = {1,3,45,6,9}
here 9>6 so initialize diff = 3 and i = 3, j = 4, max = 9 and maxID = 4
next comparing A[2] with max as it's larger update maxID = 2, max = 45
again A[1] < max and (max - A[1]) > diff so updating diff = 42 , i = 1, j =maxID
again A[0] < max and (max - A[0]) > diff so updating diff = 43, j = maxID and i = 0;
so i=0 and j=2 gives the solution in single linear scan
public class SpecialProp {
public static void main(String[] args) {
int[] input = {3,2,5,4,1};
findProfit(input);
}
private static void findProfit(int[] input) {
int min=input[0];
int max=input[0];
int minPos=0;
int maxPos=0;
for(int i=0; i<input.length; i++){
if(input[i]>max){
max=input[i];
maxPos=i;
}
}
for(int i=0; i<maxPos; i++){
if(input[i]<min){
min=input[i];
minPos=i;
}
}
System.out.println("Mininum : " +min);
System.out.println("Maximum : " +max);
}
}
This is just Maximum single-sell profit question in different format.
Solution is in O(n)
def main(arr): if len(arr) == 0: return 0 max_diff = 0 min_val = arr[0] for i in range(1, len(arr)): min_val = min(min_val, arr[i]) max_diff = max(max_diff, arr[i] - min_val) return max_diffKeep track of values of current i and j here and your solution is done.
- Expressions April 09, 2013