CareerCup

1. Go through the array once, find the max and the number of occurrences (n).
2. Generate a random number (r) between 1 and n.
3. Go through the array again, return rth occurrence.

Time: O(n)
Space: O(1)

Use the online version of Reservoir Sampling. One pass algorithm.

First go through the array and find max with all indices(store indices in arrayList).
This can be done in O(n).
Now with newly created indices arraylist, return the random element.

int array[] = {1,4,9,7,3,9,4,7,2,7,3,0,1,2,9,6,5,7,8,9};
		int maxIndex = 0;
		int count = 0;
		for(int i= 0;i<array.length;i++){
			if(array[maxIndex] == array[i])
				count++;
			else if(array[maxIndex] < array[i]){
				maxIndex = i;
				count = 1;
			}
		}
		int len = array.length;
		int lenSize = 1;
		while( len != 0){
			len = len / 10;
			lenSize = lenSize * 10;
		}
		int r = (int)(Math.random() * lenSize);
		int randomCount = (r%count)+1;
		int j = maxIndex;
		while(randomCount != 0)
			if(array[j++] == array[maxIndex])
				randomCount--;
		System.out.println("The Max Number is " + array[maxIndex] +" and it's random index is " + (j));

Assumption :
1. If an array contains only 1 max element than return the same indices
2. Random(x1,x2,x3,x4.....xn) = Random(x1, Random(x2, Random.... xn) )
( not sure if this is true , and makes every indices to be picked up with equal probability.)

Observations
1. O(n) algorithm
2. Best-So-Far approach

Pseudo algo:

For each number
If greater than current max
Reset maxIndex
If equal to current max
set Max index as Random(maxIndex , currentIndex)
If less than current max
continue
End

Will think more on Assumption 2 , and see if we can get result without any flaw in boundary scenarios.

int getMaxRandmonIndex(int[] arr) {
  int currentMax = Integer.MIN_VALUE;
  int count = 0;
  ArrayList<Integer> index = new ArrayList<Integer>();

  for (int i = 0; i < arr.length; i++) {
    if (arr[i] > currentMax) {
      currentMax = arr[i];
      count = 1;
      if (index.size > 0) {
        index.removeRange(0, index.size());
      }
      index.add(i);
    } else if (arr[i] == currentMax) {
      count++;
      index.add(i);
    }
  }
  Random rand = new Random();
  int ind = rand.nextInt(count);
  return index.get(ind);
}

It depends, if the values in array is subject to change than each time we need to check the current max.

To randomize the return index each time start the search from a random index 
For the length of array until current index equals random index
  Go through the end of the array
  if at the end move to beginning
  Each time check if the value of current index is larger than the one found so far
return the last or first index found

This will work O(n) each time with no additional memory and will return a random index.

-If the array not subject to change

if first run
  Iterate each item
    if current is larger
       wipe previous
       set current as max
       store current index
    If current equals largest
       store current index
 return random index from stored indexed

This will work O(n) for the first run O(1) for the next (depending on the data structure)

We can have separate array to hold all the indices of max elements. Give any random number among them!

int getIndexOfMaxRandomly(int arr[], int size)
{
  int i = 0;

  if (size <= 0)
    return -1;

  int* idxArr = (int *) malloc (sizeof(int) * size);
  memset (idxArr, 0, size*sizeof(int));

  if (!idxArr)
    return -1;

  srand(time(NULL));

  int curMax = arr[0], maxCnt = 1;
  for (int i = 1; i < size; i++)
  {
    if (curMax < arr[i])
    {
      curMax = arr[i];
      maxCnt = 0;
      idxArr[maxCnt++] = i;
    }
    else if (curMax == arr[i])
      idxArr[maxCnt++] = i;
  }
/*
  for (int i = 0; i < maxCnt; i++)
    printf ("%d  ", idxArr[i]);
*/
  int randIdx = idxArr[rand()%maxCnt];
  free (idxArr);
  return randIdx;
}

import java.util.ArrayList;
import java.util.Random;


public class RandomArray {

	public static void main(String[] args)
	{
		
		int[] array={45,53,73,13,89,73,89,89,89,89,89,73,452,12,132,89};
		int kb=0;
		int big=array[0];
		try
		{
		for(kb=0;kb<array.length;kb++)
		{
			if(array[kb+1]>big)
			{
				big=array[kb+1];
			}
		}
		}
		catch(ArrayIndexOutOfBoundsException e)
		{
		
		}
		ArrayList<Integer> alist=new ArrayList<Integer>();
		
		
		for(int i=0;i<array.length;i++)
		{
			if(array[i]==big)
			{
				
				alist.add(i);
				
			}
		}
		Random r =new Random();
	int random=	r.nextInt(alist.size());

	System.out.println("Max element is"+big);
	System.out.println("Position is"+alist.get(random));
		}
	}

According to the description, the max is guaranteed to be in multiple places.
Set the max number variable to the minimum number.
Loop through the values and store each value in a hashtable.

-If it is the first time insert that number into the table, continue to the next number
-If that number has appeared more than the once, compare it to the current max number and if it is bigger, it becomes the new max. Otherwise continue to the next number.

Loop until you reach the end.
Return max number.

According to the description, the max is guaranteed to be in multiple places.
Set the max number variable to the minimum number.
Loop through the values and store each value in a hashtable.

-If it is the first time inserting that number into the hashtable, continue to the next number.
-If that number has appeared more than the once, compare it to the current max number and if it is bigger, it becomes the new max. Otherwise continue to the next number.

Loop until you reach the end.
Return the max number.

You can return a random index by starting at a random position and wrapping around until you reach the starting point again.

1. Generate a random array of integers
2. Loop through to find max and store max_indices in the array.
3. Generate a random number between 0 and max_indices length.
4. Return that value from the max_indices array.

a= []
250.times { a.push(rand(50)) }
max_indices = []
max = nil
a.each_with_index do |v,i|
  max_indices.push( i ) if v == max  
  if max.nil? || v > max 
    max = v 
    max_indices = [i]
  end
end

p max_indices[rand(max_indices.length)]

<?php

function maxPosition($numbers) 
{
	$maxValue = 0;
	$maxPositions = [];
	foreach ($numbers as $index => $number) {
		if ($number > $maxValue) {
			$maxValue = $number;
			$maxPositions = [$index];
			continue;
		}
		if ($number < $maxValue) {
			continue;
		}
		$maxPositions[] = $index;
	}
	return $maxPositions[rand(0, count($maxPositions) - 1)];
}

#!/usr/bin/env python
from __future__ import print_function
import random

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

maxValue = max(arr)
max_indices = []

for idx,val in enumerate(arr):
    if (val == maxValue):
        max_indices.append(idx)        

random_idx = random.randint(0,len(max_indices)-1)
print("The maximum value is {}. It occurrs at indices {}".format(maxValue,', '.join(map(str,max_indices))))
print("A random index at which this value occurs is: ", max_indices[random_idx])

I think the simplest solution is this:

#include "stdafx.h"
#include <algorithm>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	int array[] = { 1, 4, 9, 7, 3, 9, 4, 7, 2, 7, 3, 0, 1, 2, 9, 6, 5, 7, 8, 9 };
	int elements = sizeof(array) / sizeof(array[0]);

	std::sort(array, array + elements);

	printf("the value is %d", array[elements-1]);

	getchar();

	return 0;
}

public static void main(String[] args){
       
    int[] a = new int[]{9,3,1,2,3,4,5,7,8,9,9};
	solve(a);
	}	
	
	static void solve(int[] a){
		ArrayList<Integer> ar= new ArrayList<>();
		for(int i=0;i<a.length;i++){
			ar.add(a[i]);
		}
		
		Collections.sort(ar);
		
		System.out.println(ar.get(ar.size()-1));
		
	}

private static int getRandomMaxiumNumber(int[] input) {
        if (input==null || input.length==0)
            return -1;
        if (input.length==1) {
            return 0;
        }

        int start = (int) (Math.random()*input.length-1);
        int max = Integer.MIN_VALUE;
        int maxidx = -1;
        int i=start;
        do {
            if (input[i]>max) {
                max = input[i];
                maxidx = i;
            }
            i++;
            if (i==input.length) i=0;
        } while(start!=i);
        return maxidx;

}

package pkg;

import java.util.Arrays;
import java.util.Random;

public class MaxRandom {

	/**
	 * Given an array of integers. We have to find the max element of the array,
	 * which is at multiple places in the array and return any one of the
	 * indices randomly.
	 */
	public static int findMaxElementIndiceRandom(int[] a) {

		int maxIndice = 0;

		for (int i = 0; i < a.length; i++) {
			if (a[i] > a[maxIndice]) {
				maxIndice = i;
			} else if (a[i] == a[maxIndice]) {
				maxIndice = randSelect(maxIndice, i);
			}
		}

		return maxIndice;
	}

	public static int randSelect(int numberOne, int numberTwo) {
		Random random = new Random();
		return (random.nextInt(2) % 2) == 0 ? numberOne : numberTwo;
	}

	public static void main(String[] args) {
		int[] a = new int[] { 3, 6, 3, 9, 8, 9, 4, 3, 2, 9, 1, 6 };
		System.out.println(findMaxElementIndiceRandom(a));

	}

}

Here my solution:

public static int randomPosition(int[] array) {
		int max = 0;
		List<Integer> positionsMax = null;
		for (int i = 0; i < array.length; i++) {
			if (array[i] > max) {
				max = array[i];
				positionsMax = new ArrayList<Integer>();
				positionsMax.add(i);
				System.out.println("new max found: " + max + " in position " + i);
			} else {
				if (array[i] == max) {
					System.out.println("another max in position " + i);
					positionsMax.add(i);
				}
			}

		}
		Random random = new Random();
		return positionsMax.get(random.nextInt(positionsMax.size()+1));
	}

uint find_max(vector<int> intArray) {
int max =std::numeric_limits<int>::min();
uint index=0, count=0;
for(std::vector<int>::iterator it = intArray.begin(); it< intArray.end(); ++it) {
if(*it> max) {
max = *it;
index = count;
}
count++;
}

Are there any other constraints to this question? Can we use additional memory ?

If yes,

1. Create a TreeMap of element value vs ArrayList of element position. Create this TreeMap with reverse Sort class

Map<Integer, List<Integer>> valueMap = new TreeMap<Integer, List<Integer>>(new ReverseSort());

2. This ReverseSort class implements Comparator interface which implements compare method.

Class ReverseSort implements Comparator<Integer>(){

	public int compare(int a, int b){
		return b - a; //reverse sorting
}

Now get the keySet from the treeMap and get ArrayList for the 0th Key which gives you the largest element in the array.

The value of this key is an array list of all the locations where this largest element appears, return any location randomly.

Total time complexity: O(N)
Total Space complexity: O(N)

#include <stdio.h>
#include <stdlib.h>

// randomly select an index of the two
int
randomSelect(int a, int b)
{
    if (rand() % 2 || a < 0) {
       return b;
    }

    return a;
}


//find max and maxIndex
int
findMax(int a[], int size)
{
    int max = 0;
    int maxIndex = -1;
    int i = 0;
    time_t t;

    srand((unsigned) time(&t));

    for (i = 0; i < size; i++) {
        if (max < a[i]) {
            max = a[i];
            maxIndex = i;
        } else if (max == a[i]) {
            maxIndex = randomSelect(maxIndex, i);
        }
    }

    return maxIndex;
}

int
main()
{
    int a[6] = {1, 2, 1, 2, 1, 2};
    printf("%d \n", findMax(a, 6));
}

One big issue here is the inclusion of multiples in the data set. One way to not have to deal with comparisons is to use a Hashtable.

Basically we dump the array into a Hashtable using the array value as the key and the index as the hashtable value. Some java code would like like this:

t = new Hashtable<Integer, Integer>();
		
		//list is an array of ints, but this should scale to doubles and floats as well
		for(int i = 0; i < list.length; i++)
			t.put(list[i], i);
		
		Enumeration<Integer> e = t.keys();
		int biggest = 0;
		if(e.hasMoreElements())
			biggest = e.nextElement();
		
		System.out.println(t.get(biggest));

From this you can see that all we need to do, after the dump, is to get the first key and returns its corresponding value. Mileage may vary for other Hashmap implementations