Maximum single sell profit from stock

 Posted on April 30, 2015  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Problem Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit. OR Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[]. [Read More]
max  maxima  stock  divide and conquer  Dynamic Programming  DP  minima  array 

Given an array filled with char elements, find the max length of continuous white space

 Posted on June 12, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given array filled with char elements, can you suggest a most efficient way to find the max length of continuous white space? Solution Scan the array left to right, keep a count of white space. When you reach a non-whitespace character, check that count against the current max; if it’s higher, it becomes the new max. Set the count back to zero, continue scanning. Time complexity - O(n) [Read More]
max  String  morgan-stanley 

Finding the biggest difference between sorted array values

 Posted on March 21, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem finding the biggest difference between sorted array values **Example ** Consider the array : var array = array(1,4,7,8,12,15); The values in the array will always be integers and is sorted, and elements may repeat. Now, we want to print out the biggest step in the array. step is difference between adjacent element: step array - (-,3,3,1,4,3) The biggest step is 4, between 8 and 12. Solution Method 1- Brute force [Read More]
max  kodeknight  sorted-array 

Stack with find-min/find-max in O(1) time

 Posted on February 19, 2014  (Last modified on August 11, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Stack with find-min/find-max in O(1) time Solution Method 1 - using extra stacks for min and max The basic idea of the solution can be found here. Here instead of 2 stacks we will be using 3 stacks -1 stack with normal elements, 1 with only max elements and 1 with min element. Now the operations will be following : push: - If the element being pushed is less than the top element of ‘min_stack’ then push it on ‘min_stack’ as well. [Read More]
max  kodeknight  minmax  O(1)  stack  min 

Find the minimum and maximum in the array

 Posted on February 16, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Here are few question we find on finding min and max in the array, but array type changes. Unsorted 1D array Find the maximum (OR minimum) in an array Find the maximum AND minimum in an array with min number of comparisons Find the max and second maximum in an array (likewise for minimum) Find the max and nth max in an array Rotated Sorted array Find the minimum element in the rotated sorted array. [Read More]
max  kodeknight  Page  minmax  2DSortedArray  unsorted-array  min  sorted-array 

Find Maximum Value in the unsorted array

 Posted on February 16, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Problem : **
Find Maximum Value in the unsorted array

Solution
Method 1 - Linear search

Here is the code to do that :

public int findMax(int\[\] numbers)  
{  
    int max = 0;  
  
    for (int i = 0; i < numbers.length; ++i)  
        if (numbers\[i\] > max) max = numbers\[i\];  
  
    return max;  
}

So, in worst case the number of comparisons will be (n-1).

Time complexity - O(n)

max  kodeknight  unsorted-array  min 

Find kth largest in an Array

 Posted on February 14, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

**Problem : **  You have an array of numbers; you need to find the k-th largest in the arra Solution ** Method 1 - Tournament principle** We have to find the element which has competed with largest element, and is just (k-1)th level.We have discussed this principle here. Method 2 - Using max heap Consider the array of length n. Here is the algo :  Build a max heap in O(n) ;  Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. [Read More]
max  kodeknight  largest  minmax  unsorted-array  kth-largest  min  smallest 

find out the largest and second largest number in an array

 Posted on February 14, 2014  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Question: Write an efficient C program to find smallest and second smallest element in an array. Solution Method 1 - Compare each element with current max and second max Algorithm 1) Initialize both first and second smallest as a00 first = second = a00 2) Loop through all the elements. a) If the current element is greater than firstMax, then update firstMax and secondMax. b) Else if the current element is greater than second then update secondMax pseudocode [Read More]
max  kodeknight  largest  minmax  unsorted-array  min  second-largest 

How to find max. and min. in array using minimum comparisons?

 Posted on February 14, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem : Given an array of integers find the max. and min. using minimum comparisons. Solution Method 1 (Naive) - Iterate through the array, and update min and max pointers 1\. Iterate through the array, select element a 2\. Update min by comparing (min, a) 3\. Update max by comparing (max, a) Number of comparison here will be ~2N, if N is number of element. Time complexity will be O(n) though. [Read More]
max  kodeknight  browserstack  minmax  array  unsorted-array  min