CareerCup

Finding maximum of a convex function. Hint: ternary search.

#include <iostream>
#include <vector>
using namespace std;

int findMax(vector<int>& A)
{
    int lb = 0;
    int rb = A.size() - 1;

    while (lb < rb) {
        int m = (rb - lb) / 2 + lb;

        if (A[m] < A[m + 1])
            lb = m + 1; 
        else 
            rb = m;
    }

    return lb;
}

int main()
{
    vector<int> A = {1,2,3,4,5,9, 11, 88, 4, 3,1};

    cout << "max = " << A[findMax(A)] << endl;
    return 0;
}

public class FindMax {

	public int getMax(int[] arr)
	{
		int r = getMaxRecursive(arr, 0 , arr.length-1);
		return r;
	}
	
	// a simple binary search O(logn)
	private int getMaxRecursive(int[] arr, int start, int end)
	{
		if (start > end)
		{
			return -1;
		}
		
		int mid = (start + end)/2;
		if ( (mid-1) >= 0 && arr[mid] > arr[mid-1]
		      && (mid+1) < arr.length && arr[mid] > arr[mid+1])
		{
			return arr[mid];
		}
		
		// increasing case e.g. 1,2,4, so the key must be in right half 
		if ((mid-1)>= 0 && arr[mid-1] < arr[mid]
		     && (mid+1) <arr.length && arr[mid] < arr[mid+1])
		{
			return getMaxRecursive(arr, mid, end);
		}
		else
		{
			// key must be left half
			return getMaxRecursive(arr, start, mid);
		}
		
	}

	public static void main(String[] args) 
	{
		int[] arr = {1,2,3,4,5,3,1};
		int result = new FindMax().getMax(arr);
		System.out.println(result);

	}

}

iterate the array till,next element is greater then current element.
if next element is less then current element return current element.

int t=0;
int n;
int a[]=new int[n]; // 'a' is array name & 'n' is it's size
for(int i=0;i<n;i++)
{
if(t<=a[i])
{
t=a[i];

}

else
{
System.out.println(i-1);
break;
}
}

here is solution for this problem in O(log n ).
it makes use of binary search.

public class RotatedArrayMaxSearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A = {15, 16, 19, 20, 25,31, 42, 1, 3, 4, 5, 7, 10, 14};
		
		int maxnum = RotatedArrayProblem(A, 0, 13);
		System.out.print(maxnum);
	}

	
	public static int RotatedArrayProblem(int A[], int start, int end)
	{
		int mid = start + (end - start)/2;
		
		if(start == end)
			return A[start];
		
		if(A[mid] > A[start]){

			if(A[mid] > A[mid-1] && A[mid] < A[mid+1])
			{
				return RotatedArrayProblem(A, mid, end);
			}
			else if (A[mid]> A[mid-1] && A[mid]> A[mid+1])
			{
				return A[mid];
			}
			else if (A[mid] < A[mid-1] && A[mid]< A[mid+1])
			{
				return RotatedArrayProblem(A, start, mid);
			}
		}
		else{
			if(A[mid] > A[mid-1] && A[mid] < A[mid+1])
			{
				return RotatedArrayProblem(A, start, mid);
			}
			else if (A[mid]> A[mid-1] && A[mid]> A[mid+1])
			{
				return A[mid];
			}
			else if (A[mid] < A[mid-1] && A[mid]< A[mid+1])
			{
				return RotatedArrayProblem(A, start, mid);
			}
		}
		return -1;
		 
	}
}

int findMaxIndex(int a[],int count)
{
for(int i=0; i<count-1; i++)
{
if(a[i] > a[i+1])
return i;
}
return count-1;
}

Complexity : O(log n)

public class Practice107 {
	public static void main(String[] args){
		int arr[] = {1,2,3,45,45,5,5,5,5,5};
		System.out.println(searchLargest(arr,0,arr.length));
	}
	
	public static int searchLargest(int[] arr,int start,int end){
		int mid=0;
		if(start <= end){
			mid = (start+end)/2;
			
			if((mid-1)>=0 && arr[mid-1] > arr[mid]){
				 return searchLargest(arr,start,mid);
			}else if((mid+1) < arr.length && arr[mid+1] >= arr[mid]){
				 return searchLargest(arr,mid,end);
			}
		}
		return arr[mid];
	}
}

static int getMaxIndex(int[] arr) {
	int left=0,right = arr.length-1;
	//arr[left] >= anything to left of it, arr[right] >= anything to right of it

	while(left<right-1) {
		int mid = (left+right)/2;
		if (arr[mid]<arr[mid+1]) left=mid+1; else right=mid;
	}

	if(arr[left]>arr[right]) return left; else return right;
}

interpret the array as a min heap, return the index where the min heap invariant is violated

return the 2*(last index+1) where the min heap variant is valid... not the index where the invariant is violated.

arr = [2, 3, 4, 5, 6, 6, 3, 2, 1]

a,b = 0, len(arr)

while a != b:
e = int((a+b)/2)
# increasing or equal
if arr[e+1] - arr[e] > 0:
a = e+1
else:
b=e

print("Array: ", str(arr))
print("Maximum: " + str(arr[a]))

arr = [2, 3, 4, 5, 6, 6, 3, 2, 1]

a,b = 0, len(arr)

while a != b:
    e = int((a+b)/2)
    # increasing or equal                                                                                                                                                                                                                                                                                                     
    if arr[e+1] - arr[e] > 0:
        a = e+1
    else:
        b=e

print("Array: ", str(arr))
print("Maximum: " + str(arr[a]))

public int findHighest(int[] array,int left,int right) {
int mid=(left+right)/2;

if(array[mid] > array[mid+1]) {
return array[mid];
} else if(array[mid] > array[mid-1]) {
left=mid+1;
} else {
right=mid;
}

return findHighest(array, left, right);
}

for ( i = 0 ; i < array.legth - 1  ;  i ++ )
{
       if(array[i] > array[i+1])
      return i;
    else  if( array[ array.length - 1 - i ]   > array[ array.length - i - 2 ] )
      return i;
 }

#include<stdio.h>
int main(){

	int a[] = {2, 3, 4, 5, 6, 6, 3, 2, 1};
	int i;
	for( i=0;i<(sizeof(a)/sizeof(int));i++){
		if(a[i]<a[i+1]) continue;
		else break;
	}
	printf("\nIndex of max = %d",i);
}

Will work in any case

int[] intArray = new int[]{1, 3, 5, 7, 8, 6, 4, 2};

		int front_prev = 0;
		int front_next = front_prev + 1;

		int tail_prev = intArray.length - 2;
		int tail_next = intArray.length - 1;

		while (front_next <= tail_prev)
		{
			if (intArray[front_prev] < intArray[front_next])
			{
				front_next++;
				front_prev++;
			}
			if (intArray[tail_prev] > intArray[tail_next])
			{
				tail_prev--;
				tail_next--;
			}
		}

		System.out.println("index " + front_next + " number " + intArray[front_next]);

#include<stdio.h>

int getIndex(int a[],int left,int right)
{
    if(left>right)
      return left;
    int mid=(left+right)/2;
    if(a[mid]>=a[mid-1] && a[mid]>=a[mid+1])
       return mid;
    else if(a[mid]>=a[mid-1])
       return getIndex(a,mid+1,right);
    else
       return getIndex(a,left,mid-1);
}

int main()
{
    int a[100],i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
       scanf("%d",&a[i]);
    printf("Index of Maximum number is %d\n",getIndex(a,0,n-1));
    getch();
    return 0;
}

public static int getMaxNumber(int [] array){
		int start = 0;
		int end = array.length-1;
		while ( start <= end){
			int mid = start + (end -start)/2;
			if ( mid == array.length-1)return -1;
			if(  array[mid] > array[mid-1] && array[mid] > array[mid+1]){
				return array[mid];
			}else
			if( array[mid] < array[mid+1]){
				start = mid+1;
			}else if( array[mid] < array[mid-1]){
				end = mid-1;
			}
		}
		return -1;
	}

public class Main
{
public static void main(String[] args) throws Exception
{

int[] array = {1,2,2,2,3,3,4,5,6,5,3,3,2,2,2,1};

int left = 0;
int right = array.length - 1;
while (left != right)
{
if (array[left] < array[right])
left++;
else
right--;
}
System.out.println(left);
}
}

public class Indexof {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[]={1,2,3,4,5,6,7,8,9,11,23,24,35,67,89,56,45,34,23,12,10,9,8,7,6,5,4,3,2};
for(int i=0;i<array.length;i++){
if(array[i]-array[i+1]>=0){
System.out.println(i);
break;
}
}
}

}

public class Indexof {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int array[]={1,2,3,4,5,6,7,8,9,11,23,24,35,67,89,56,45,34,23,12,10,9,8,7,6,5,4,3,2};
		for(int i=0;i<array.length;i++){
			if(array[i]-array[i+1]>=0){
				System.out.println(i);
				break;
			}
		}
	}

}

#include <iostream>

int findMax(int* array, int size, int base)
{
if (size == 2)
{
if (array[1] > array[0])
return base + 1;

return base;
}

if (size == 1)
return base;

int mid = size / 2;
if (array[mid + 1] > array[mid])
{
return findMax(array + mid + 1, size - mid - 1, mid + 1);
}
else
{
return findMax(array, mid + 1, 0);
}
}

int main()
{
int array[] = {7,8,1,2,3,4,5};

std::cout << findMax(array, sizeof(array) / sizeof(int), 0);
return 0;
}

perform binary search. Find center, compare with its adjacent elements and recursively search on larger side.

u can do this using binary search in log(n) time. As its given first increase then decrease mean u have to sorted array in one array.

Do binary search and find if the mid number if it is greater than its left element and that of right ,u r done ,else if left is greater and right is also greter then set low as mid,and similarly for other side

I don't intend to be negative. However, I am finishing up my software engineering degree and am beginning my job search I came across this site for practice problems. What I would like to know is this seriously the level of my competition for jobs, there seems to be a complete lack of understanding of basics including big O notation and the use of data structures and how they relate to solving a problem.

Dupe thread.

here's a solution in python

def divide(na,lo,hi):
  last = na[hi]
  next2last = na[hi-1]
  if last > next2last: 
    # we are still increasing, 
    #so, no sense digging into this half of the array
    return last

  if lo >= hi: #pointers crossed
    return  last

  mid = lo + (hi - lo ) / 2
  leftone = divide(na,lo,mid)#look at left half
  rightone = divide(na,mid+1,hi)#look at right half
  return leftone if leftone > rightone else rightone

#na is an array of numbers that increase and then decrease
#objective is to find the maximum

def convexSearch(na):
  lo = 0
  hi = len(na) - 1
  winner = divide(na,0,hi)
  print "highest is: " , winner·

package com.practice;



public class Practice2 {
	
	public static final void main(String[] args){
		
		int arr[] = {1,2,3,4,5,5,3,1};
		
		int  p = arr.length/2;
		
		if(arr[p-1] <= arr[p] && arr[p] >= arr[p+1]) {
			
			System.out.println(p);
			
			
		} else if( arr[p-1] >= arr[p] ) {
			for(int i = p-1 ; i >= 0; i-- ) {
				if(arr[i] > arr[p]) {
					p--;
				} else {
					System.out.println(p);
					break;
				}
			}
		} else if (arr[p+1] >= arr[p]) {
			for(int i = p+1 ; i < arr.length; i++) {
				if(arr[i] > arr[p]) {
					p++;
				} else {
					System.out.println(p);
					break;
				}
			}
		}
	}

}

//Another non recursive solution.

int FindMax(int *arr, int start, int end)
{
int subStart = start;
int subEnd = end;

while (subStart < subEnd)
{

int median = (subStart + subStart) / 2;

if(arr[median] > arr[median+1] && arr[median] >= arr[median-1])
return median;

// Let us assume a left case
if( arr[median] <= arr[median+1] )
subStart = median+1;
else if( arr[median] > arr[median+1] && arr[median] < arr[median-1])
subEnd = median-1;
}

return -1;
}

#include<stdio.h>
#include<conio.h>
void main()
{
int arr[]={2,3,6,7,9,10,45,60,70,80,100,55,50,10,9,8,7,6,5,4,3,2,1,0,-1};
int a=sizeof(arr);
int b=sizeof(int);
int high=a/b;
printf("%d\n",high);
int low=0;
int mid;
for(int i=0;i<(high+low)/2;i++)
{
mid=(high+low)/2;
if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1])
{
printf("%d",arr[mid]);
break;
}
else if(arr[mid]>arr[mid-1])
low=mid;
else if(arr[mid]>arr[mid+1])
high=mid;
}
getch();
}

public int getBiggestInt(int[] array, int start, int end){
		int mid_index;
		int ret_value;
		int left_value = -1;
		int right_value = -1;
		int current_index;
		boolean bLeft = true;
		boolean bRight = true;
		
		if(end-start == 1)
			ret_value = array[start];
		else if(end-start == 2){
			ret_value = array[start]>=array[start+1]?array[start]:array[start+1];
		}else{
			mid_index = (start+end)/2;
			current_index = mid_index - 1;
			while(bLeft && current_index >= start ){
				if(array[mid_index] > array[current_index]){
					left_value = array[mid_index];
					bLeft = false;
				}else if (array[mid_index] == array[current_index]){
					current_index --;						
				}else{
					left_value = getBiggestInt(array,0,current_index + 1);
					bLeft = false;
				}
			}
			current_index = mid_index + 1;
			while(bRight && current_index < end){
				if(array[mid_index] > array[current_index]){
					right_value = array[mid_index];										
					bRight = false;
				}else if (array[mid_index] == array[current_index]){
					current_index ++;
				}else{
					right_value = getBiggestInt(array,current_index,end);
					bRight = false;
				}
			}
			ret_value = left_value > right_value ? left_value : right_value;
		}
		return ret_value;
	}

 }

I think the complexity is less than o(n)

b = [1,2,3,4,5,5,10,11,32,23,12,3,2,1,0]

def findMaxIndex():
    mx = b[0]
    mxidx = 0
    for i in range (1, len(b)):
        if b[i] >= mx:
            mx = b[i]
            mxidx+= 1
            continue
        else:
            break
    print 'Max Index is...', mxidx
    print 'Max number is...', b[mxidx]
        
findMaxIndex()

b = [1,2,3,4,5,5,10,11,32,23,12,3,2,1,0]

def findMaxIndex():
    mx = b[0]
    mxidx = 0
    for i in range (1, len(b)):
        if b[i] >= mx:
            mx = b[i]
            mxidx+= 1
            continue
        else:
            break
    print 'Max Index is...', mxidx
    print 'Max number is...', b[mxidx]
        
findMaxIndex()

Please check the below code..

public class ArrayInIncreasingDecreasingorder {

public static void main(String args[]){
int arr[] = {1,2,9, 5,4,3,2};
System.out.println("Largest index :" +findLargestIndex(arr, 0, arr.length -1));
}

private static int findLargestIndex(int[] arr, int low, int high) {
if (high < low) return -1;
int mid = (low + high)/2;

System.out.println(low+" :"+high+": "+mid);

if(mid < high && arr[mid] == Math.max(arr[mid], arr[mid+1]) &&
arr[mid] == Math.max(arr[mid], arr[mid-1])){
return mid;
}else if(mid > low && arr[mid-1] == Math.max(arr[mid], arr[mid-1]) &&
arr[mid-1] == Math.max(arr[mid-1], arr[mid-2])){
return (mid-1);
}else if(arr[mid]>= arr[low]){
return findLargestIndex(arr, mid+1, high);
}else{
return findLargestIndex(arr, low, mid-1);
}
}
}

public static int searchLargestMiddle(int[] arr)
        {
            int mid = 0;
            int end = arr.Length;
            int start = 0;
            while (true)
            {
                mid = (start + end) / 2;
                if (mid - 1 >= 0 && arr[mid - 1] > arr[mid])
                    end = mid;

                else if ((mid + 1) < arr.Length  && arr[mid + 1] >= arr[mid])
                    start = mid;
                else 
                    return arr[mid];
            }
        }

#include<conio.h>
#include<stdio.h>
int getMaxIndex(int* a,int length)
{
	int max = length;
	int i;
	if(length>1)
	{
		length = length/2;
			if((a[length+1]<a[length]) && (a[length]>a[length-1]))
			{
				return a[length];
			}else if((a[length+1]<a[length]) && (a[length]<a[length-1]))
			{
                	for(i=length;i>0;i--)
                	{
                        	if((a[i+1]<a[i]) && (a[i]<a[i-1]))
							{
								return a[i-1];
							}
                	}
			}else if(a[length+1]>a[length] && a[length]>a[length-1])
			{
                for(i=length;i<max;i++)
                	{
                        	if(a[i+1]>a[i] && a[i]>a[i-1])
							{
								return a[i+1];
							}
                	}

			}

		
	}else
	{
		return -1 ;
	}
}
main()
{
	int a[] = {1,2,3,4,8,5};
	int s;
	s =sizeof(a)/sizeof(int);
	int num = getMaxIndex(a,s);
	printf("result is %d",num);
	getch();
}

above code will work for all below cases-
{1,2,3,4,3,2,1}
{2}
{8,7,6,5,4}
{1,2,3,4,5}

package com.pz.careercup;

public class RotatedOrder {
public static void main(String[] args) {
int a[] = new int[] { 1,15,12,11,10,9,8,7,6,5 };

int index = maxValueIndex(a, 0, a.length - 1);

System.out.println("Max value: " + a[index]);
}

private static int maxValueIndex(int[] arr, int start, int end) {
if (start == end) {
return start;
}

int mid = start + (end - start) / 2;
int j = mid+1;
for ( ;j < end; j++) {
if (arr[j ] != arr[j-1]) {
break;
}
}
int comp = arr[mid] - arr[ j];
if (comp >= 0) {
return maxValueIndex(arr, start, mid);
} else {
return maxValueIndex(arr, j, end);
}
}
}

package com.pz.careercup;
public class RotatedOrder
{public static void main(String[] args)
{int a[] = new int[] { 1,15,12,11,10,9,8,7,6,5 };
int index = maxValueIndex(a, 0, a.length - 1);
System.out.println("Max value: " + a[index]);
}

private static int maxValueIndex(int[] arr, int start, int end)
{if (start == end)
{
return start;
}

int mid = start + (end - start) / 2;
int j = mid+1;
for ( ;j < end; j++) {
if (arr[j ] != arr[j-1]) {
break;
}
}
int comp = arr[mid] - arr[ j];
if (comp >= 0) {
return maxValueIndex(arr, start, mid);
} else {
return maxValueIndex(arr, j, end);
}
}
}

package com.pz.careercup;

public class RotatedOrder {
public static void main(String[] args) {
int a[] = new int[] { 1,15,12,11,10,9,8,7,6,5 };

int index = maxValueIndex(a, 0, a.length - 1);

System.out.println("Max value: " + a[index]);
}

private static int maxValueIndex(int[] arr, int start, int end) {
if (start == end) {
return start;
}

int mid = start + (end - start) / 2;
int j = mid+1;
for ( ;j < end; j++) {
if (arr[j ] != arr[j-1]) {
break;
}
}
int comp = arr[mid] - arr[ j];
if (comp >= 0) {
return maxValueIndex(arr, start, mid);
} else {
return maxValueIndex(arr, j, end);
}
}
}

void Main() {
Search(0,a.Length - 1);
print(max);
}


void Search (int low,int high) {
print(low + ":" + high);
if(low <= high)
{
int mid = (low + high) / 2;
if(low == high || (a[mid] > a[mid-1] && a[mid] > a[mid + 1]))
max = a[mid];
else if(a[mid] < a[mid-1])
Search(low,mid - 1);
else if(a[mid] <= a[mid + 1])
Search(mid + 1,high);
}
int max = 0;

Using Ternary Search :

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <cassert>

using namespace std;


#define rep(i,a,b) for(long long i=a;i<b;i++)
#define repe(i,a,b) for(long long i=a;i<=b;i++)
#define vi vector<int>
#define vll vector<long long>
#define ll long long
#define vll vector<long long>
#define s(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pb push_back
#define mp make_pair


vi arr;

int ts(int left, int right)
{
// printf("left = %d right = %d\n",left, right);
if(right - left <1)
{
return arr[(left + right)/2];
}
int leftThird = left + (right - left)/3;
int rightThird = right - (right - left)/3;
if(arr[leftThird] < arr[rightThird])
ts(leftThird+1,right);
else if(arr[leftThird] > arr[rightThird])
ts(left,rightThird-1);
else
ts(leftThird, rightThird);
}
int main()
{
int n;
cin>>n;
arr.resize(n);
rep(i,0,n)
{
s(arr[i]);
}
int ans = ts(0,n-1);
printf("%d\n",ans);
}

Can be done in logn time...
Divide the array in two equal parts and compare the numbers at end of first part and begining of second part. If the later is greater, continue the same process with second part, else check if a[i]>a[i-1], i is the ans otherwise continue the same with first part until u get a point i where a[i-1]<a[i] and a[i]>a[i+1]

current_max = 0
for(i = 0; i < array.length; i++){
	if(list[i] < current_max){
		return i-1
	}
	current_max = list[i]
}

public static void main(String[] args)
{
int[] arr = {1,2,3,4,5,3,1};
Arrays.sort(arr);
int result = arr[arr.length-1];
System.out.println(result);

}

int findMaxIndex(int a[],int count)
{
	for(int i=0; i<count-1; i++)
	{
		if(a[i] > a[i+1])
			return i;
	}
	return count-1;
}

Easiest and best answer ;0))

private static void findMaxSinglePointer(int[] intArray)
	{
		int front_prev = 0;
		int front_next = front_prev + 1;

		while (front_next < intArray.length && intArray[front_prev] < intArray[front_next])
		{

			front_next++;
			front_prev++;
		}

		System.out.println(" index " + front_prev + " number " + intArray[front_prev]);

}

#include<iostream>
using namespace std;
int main()
{int a[20];
cout<<"Enter the numbers in the array"<<endl;
for(int i=0;i<20;i++)
{cin>>a[i];
}
int j;
while(a[j+1]>a[j])
{j=j+1;
}
cout<<j;
system("pause");
return 0;
}