Epic Systems Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
8
of 8 vote

Large,medium,Small reffered as l,m,s respectively,sum=0

take the first three elements and store them in l,m,s such that largest of them is in l,2nd largest in m and the 3rd largest in s

also we are taking the sum of them
sum=l+m+s;
count=3;
do
{
scanf("%d",&a);
sum=sum+a;
if(a>s)
{
s=a;
if(s>m)
{
swap(s,m);
if(m>l)
swap(m,l);
}
}
count++;
}while(a!=0);

after input is terminated by occurence of first 0;
we have total sum=s, total count of no. of inputs,s,m,l.

avg=(sum-(s+m+l))/(count-3);

printf("first three numbers%d %d %d\n\n",l,m,s);

printf("avg=%d\n\n",avg);




this solves the purpose in O(n) and very less memory when all that is required to give top 3 nos and the avg of the remaining.

- jeetu.mfp August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. Use Max heap to get rid of max 3 values (No need to say, exclude 0 in advance).
2. Then calculate average

- Hayato July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just adding this point to assure those people who aren't sure about max heaps and such - Using a max heap to solve this is surely a good idea. If someone has the implementation details of max heap fresh in memory, then thats great. However, epic questions are such that almost all questions can be worked out without having any knowledge of such data structures. So, not having brushed up your data structures doesn't put you at a disadvantage.

- ranechabria July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well I think using heap demonstrates your knowledge, but the heap sort requires O(nlogn), which is worse than O(n). For this particular one linear scanning may be optimal. For a more complicated situation heap may be a better option.

- NathanLRF January 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;

public class MaximumThreeAndAverage {

	int[] arr= new int[10];
	int max1=0;
	int max2=0;
	int max3=0;
	
	public MaximumThreeAndAverage() throws IOException 
	{
		load();
	}
	
	public void load() throws IOException
	{
		System.out.println("Enter 10 numbers in the array:");
		Scanner sc= new Scanner(new InputStreamReader(System.in));
		for(int i=0;i<arr.length;i++)
		{
			arr[i]=sc.nextInt();
			if(arr[i]==0)
				break;
		}
		System.out.println("thankyou");
	}
	 public void calculateThreeMaximums()
	 {
		 System.out.println(" ");
		 max1=arr[0];
		 for(int i=0;i<arr.length;i++)
		 { 
			 if(arr[i]>max1)
			 {
				 max1=arr[i];
			 }
		 } 
		 for(int i=0;i<arr.length;i++)
		 { 
			 if(arr[i]<max1&&arr[i]>max2)
			 {
				 max2=arr[i];
			 }
		 }
		 max3=arr[0];
		 for(int i=0;i<arr.length;i++)
		 { 
			 if(arr[i]<max2&&arr[i]>max3)
			 {
				 max3=arr[i];
			 }
		 }
		 System.out.println("the Final three maximum numbers are: Max1: "+ max1+ " Max2: " + max2 +" Max3: "+max3);
	 }
	 
	 public void averageOfRestNumbers()
	 {
		 int size=arr.length;
		 int sum = 0;
		 double average;
		 for(int i=0;i<arr.length;i++)
		 {
			 if(arr[i]==max1||arr[i]==max2||arr[i]==max3)
			 {
				 arr[i]=0;
				 size--;
			 }
			 sum+=arr[i];
			 
			
		 } 
		 average=(double)sum/size;
		 System.out.println("the average is: " +average);
	 }
	
	public static void main(String[] args) throws IOException {
		
		MaximumThreeAndAverage ax= new MaximumThreeAndAverage();
		ax.calculateThreeMaximums();
		ax.averageOfRestNumbers();

	}

}

- codingAddicted July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it cannot handle the situation that there are identical value items

- Ryan October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sort acending
Find avg from index 1 to n-3

- mayank.tewari.online October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

what if there is a negative number in the list? Then I don't think we can use index 1 to n-3

- Nodame February 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include <iostream>
using namespace std;

void swap(int* arr,int i,int j)
{
		int temp=arr[j];
		arr[j]=arr[i];
		arr[i]=temp;
}
void sort(int* arr,int count)
{
	int temp;
	if (arr[0]<arr[1])
		swap(arr,0,1);
	if(count==3)
	{
		if (arr[0]<arr[2])
			swap(arr,0,2);
		if (arr[1]<arr[2])	
			swap(arr,1,2);
	}
}

void max3andavg()
{
	int arr[3];
	int t,count=0,sum=0;
	cout<<"Enter the number";
	cin>>t;
	while (t!=0)
	{
		sum=sum+t;
		count++;
		if (count<=3)
		{
			arr[count-1]=t;
			if(count>1)
				sort(arr,count);
		}
		else
		{
			if (t>arr[2])
			{
				arr[2]=t;
				sort(arr,3);
			}
		}
		cout<<"Enter the number";
		cin>>t;
	}

	if (count<=3)
	{
		for (int i =0;i<count;i++)
		{
			sum=sum-arr[i];
			cout <<arr[i]<<"  ";
		}
		cout<< "\n The average is 0";
	}
	else
	{
		cout<<arr[0]<<"  "<<arr[1]<<"  "<<arr[2]<<"  ";
		sum=sum-arr[0]-arr[1]-arr[2];
		cout <<"\n The average is"<< sum/(count-3);
	}
}


int main()
{
	max3andavg();	
}

- priyanshu October 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

#include <iostream>
#include <vector>

using namespace std;

float FindMax (vector<int>& arr) {
	/* convention is : max_1 < max_2 < max_3 */
	int max_1, max_2, max_3, sum;

	max_1 = max_2 = max_3 = sum = 0;

	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] > max_3) {
			max_1 = max_2;
			max_2 = max_3;
			max_3 = arr[i];
		}

		else if (arr[i] > max_2) {
			max_1 = max_2;
			max_2 = arr[i];
		}

		else if (arr[i] > max_1) {
			max_1 = arr[i];
		}
	}

	if (max_1 == max_2 || max_2 == max_3) {
		throw "No three unique maximum numbers.";
	}

	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] != max_1 && arr[i] != max_2 && arr[i] != max_3) {
			sum += arr[i];
		}
	}

	cout << "Max_1: " << max_1 << endl << "Max_2: "
		<< max_2 << endl << "Max_3: " << max_3 << endl;
	return static_cast<float> (sum) / (arr.size() - 3);
}

int main ( ) {
	vector<int> arr;
	int num;

	cout << "Enter a sequence of numbers. Terminate with zero." << endl;

	while (cin >> num && num != 0) {
		arr.push_back(num);
	}

	try {
		if (arr.size() < 3) {
			throw "Not enough numbers were entered.";
		}

		cout << "Average excluding the maximum three is " << FindMax (arr) << endl;
	}

	catch (const char* ex) {
		cout << ex << endl;
	}

	return 0;
}

- ranechabria July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how are you initializing an array when you dont know the size of it.........


the user can give input of any size!!!!

- jeetu.mfp August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the elements using (qsort) and find the average excluding the last three..o(n*logn)

- Rush July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

do the bubble sort for three iterations to find the three maximum numbers and then take the average..

- cobra July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

3 round's of bubble sort will be O(3n) == O(n) but very high constant factor for large n.
instead keeping a stack of largest 3 can be used again complexity will be O(n) but constant factor lower.

- joker July 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

System.out.println("enter the numbers");
                InputStreamReader ir = new InputStreamReader(System.in);
                BufferedReader br = new BufferedReader(ir);

                String str = br.readLine();
                //System.out.println(str);
                String[] arr_str = str.split(" ");

                int[] arr_i= new int[arr_str.length];

                int count =0;
                for(String x: arr_str)
                {
                        int i = Integer.parseInt(x);
                        arr_i[count]=i;
                        count++;
                }

                //sort the integer array
                for(int a=0; a<arr_str.length; a++)
                {
                        for(int b=1; b<(arr_str.length-a); b++)
                        {
                                if(arr_i[b-1]>arr_i[b])
                                {
                                        int temp = arr_i[b-1];
                                        arr_i[b-1]=arr_i[b];
                                        arr_i[b]=temp;
                                }
                        }
                }

                //now calculate the average of all the integers except the two largest ones
                int sum=0;
                for(int num=0; num<(arr_str.length-3); num++)
                {
                        sum=sum+arr_i[num];

                }
                int average_sum = sum/2;
                System.out.println(average_sum);

- puja July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>                                                             
 37                                                                                 
 37 using std::cout;                                                                
 37 using std::cin;                                                                 
 37 using std::endl;                                                                
  1         }                                                                       
 37                                                                                 
 36 int main()                                                                      
 35 {                                                                               
 34     const int MAX_NUM_COUNT = 3;                                                
 33     int max_nums[ MAX_NUM_COUNT ] = { 0 };                                      
 32                                                                                 
 31     cout << "Enter list of numbers: ";                                          
 30     int number_read( 0 ), number_read_count( 0 ), total( 0 ), temp( 0 );        
 29     while( cin >> number_read )                                                 
 28     {                                                                           
 27         if ( 0 == number_read )                                                 
 26             break;                                                              
 25                                                                                 
 24         total += number_read;                                                   
 23         ++number_read_count;                                                    
 22                                                                                 
 21         for( int i = 0; i != MAX_NUM_COUNT; ++i )   // Swap max_nums and number_read 
 20         {                                           // For loop maks sure that  
 19             if ( max_nums[ i ] < number_read )      // Max numbers are stored   
 18             {                                       // in sorted order from max 
 17                 temp = number_read;                 // to min                   
 16                 number_read = max_nums[ i ];                                    
 15                 max_nums[ i ] = temp;                                           
 14             }                                                                   
 13         }                                                                       
 12     }                                                                           
 11     for( int i = 0; i != MAX_NUM_COUNT; ++i )                                   
 10         total -= max_nums[ i ];                                                 
  9     number_read_count -= MAX_NUM_COUNT;                                         
  8                                                                                 
  7     if ( 0 < number_read_count )                                                
  6         cout << "Average: " << ( static_cast<double>( total ) / number_read_count ) 
  5              << endl;                                                           
  4     else                                                                        
  3         cout << "No number entered." << endl;                                   
  2                                                                                 
  1     return 0;                                                                   
  0 }

- myth July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

IMHO, there can be two solution to this problem:
1. By using std::set, which stores the element in increasing order. Last three entries can be neglected while computing the average.
2. By storing the element in the sorted list and an variable to count the element. Last three element of this list can be ignored while computing the average.

- kamal July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your set solution will miss out duplicates giving wrong result...
and sorting will take atleast O(nlogn).

- R K August 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pastebin: pastebin dot com/cWSPCu9K

Source:

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

int main(){
    
    int* array;
    int count = 0, count_without_zero = 0, i, j;
    int inp = 0;
    int max, max_pos, max_to_remove = 3;
    int sum = 0;
    
    //initial size
    array = (int*) malloc(sizeof(int));
    
    //taking input from user
    printf("Enter numbers seperated by 'space', Enter '0' to finish: \n");
    do {
       scanf("%d", &inp);
       if (inp != 0){
           array = (int*) realloc(array, (count + 1) * sizeof(int));
           array[count] = inp;
           count++;
       }
    } while (inp != 0);
    
    //replacing max three numbers with 0
    for (j = 0; j < max_to_remove; j++){
        max = 0;
        max_pos = 0;
        for (i = 0; i < count; i++){
            if (array[i] > max){
               max = array[i];
               max_pos = i;
            }
        }
        array[max_pos] = 0;
    }
    
    //calculating sum
    for (i = 0; i < count; i++){
        sum = sum + array[i];
    }
    
    //counting number of elements except '0'
    for (i = 0; i < count; i++){
        if (array[i] != 0){
           count_without_zero++;
        }
    }
    
    //output
    printf("Array elements excluding max three:\n");
    for (i = 0; i < count; i++){
        if (array[i] != 0){
           printf("%d ", array[i]);
        }
    }
    
    printf("\nSum of array elements: %d\n", sum);
    printf("Count of array elements: %d\n", count_without_zero);
    printf("Average: %f\n", (float)(sum / count_without_zero));
    
    //cleaning up
    free(array);
    getch();
    return 0;
}

- Fahad Hasan July 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I see this as a simple application of 'Selection in Linear Time'. The algorithm is described here:
http: //www . cs. cmu. edu/afs/cs.cmu.edu/academic/class/15451-s07/www/lecture_notes/lect0125.pdf

Using this algorithm we can find the first, second and third max and then take the average of the remaining.
Also if tomorrow someone changes the problem and asks to find third, fifth and seventh, we wont need to change code.

- AK July 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hey AK the link u posted m unable to open can u plz mail me the pdf file on pravinsankrit@gmail.com asap
thax in advance

- pks August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can use randomized_select algorithm for finding the top 3 max values (they wud b in the indices n-1,n-2,n-3 respectively) and then we can easily do the rest of the manipulations. so running time here wud b O(n).

- fire and ice August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Use selection algorithm (find Kth largest) to put three largest elements to first three.
2. Then calculate average from the third element

Time Complexity would be O(N) in average.

- cli22 October 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have used C# and the complexity is O(n)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TestDemo
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter the sequence of Integer's and press 0 to end it");
List<int> numbers=new List<int>();
string inp;
do
{
inp = Console.ReadLine();
numbers.Add(Convert.ToInt32(inp));
} while (inp != "0");

int[] arr = numbers.ToArray();
Array.Sort(arr);
int max1 = arr[arr.Length - 1];
int max2 = arr[arr.Length - 2];
int max3 = arr[arr.Length - 3];
Console.WriteLine("Max Numbers:" + max1 + " " + max2 + " " + max3);

int sum = 0; int l = 0;
for (l = 1; l < arr.Length - 3; l++)
sum = sum + arr[l];

float avg =(float) sum / (l-1);
Console.WriteLine("Avg of rest:" + avg);

}
}
}

- kulkarniaks007 November 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pseudocode:

sort the elements in increasing orderfirst
sort(a[])
for(i=o;i<a.length-3;i++)
sum+=a[i];
avg=sum/(i+1);
print avg;

- Anonymous February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do selection sorting 3 times , 3n computation , then compute average form 4th to last element

- Jayanti March 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
User inputs a series of numbers and terminates the series by a zero. Your program should find the first three maximum values in the series and exclude them from the series and compute the average of the remaining numbers. (excluding zero as well)
Ex - 3, 7, 12, 2, 25, 8, 9, 13, 10, 0
First three maximum numbers = 25, 13, 12
Average of the rest = (3 + 7 + 2 + 8 + 9 + 10) / 6 = 6.5
*/

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int main()
{
vector<int> arr;
int l, m, s, temp, avg, sum, num, i, j, k;

l = m = s = 0;

while(1)
{
scanf("%d", &num);

if(0 == num)
break;

temp = max(l, num);

if(temp == l)
{
temp = max(m, num);
if(temp == m)
{
temp = max(s, num);
if(temp != s)
{
if(0 != s)
arr.push_back(s);
s = temp;
}
else
arr.push_back(num);
}
else
{
if(0 != s)
arr.push_back(s);
s = m;
m = num;
}
}
else
{
if(0 != s)
arr.push_back(s);
s = m;
m = l;
l = num;
}

printf("l=%d m=%d s=%d\n", l, m, s);
}

k = arr.size();

for(i=0, sum=0; i<k; i++)
{
printf("%d ", arr[i]);
sum += arr[i];
}

printf("\n%f\n", sum*1.0/k);

return 0;
}

- Ankit Agarwal March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Working Python version using sort().
If sort() is not allowed to use, the best algo will be have 3 extra vars keep the max three, and you sum the array as you scan it, finally deduct the 3 vars. This yields to O(n).

"""
2:12
@Python 2.7

User inputs a series of numbers and terminates the series by a zero. Your program should find the first three maximum values in the series and exclude them from the series and compute the average of the remaining numbers. (excluding zero as well) 
Ex - 3, 7, 12, 2, 25, 8, 9, 13, 10, 0 
First three maximum numbers = 25, 13, 12 
Average of the rest = (3 + 7 + 2 + 8 + 9 + 10) / 6 = 6.5
"""

class NotMaxThree(object):
  def __init__(self, input):
    if input is None:
      print 'Invalid Input!'
      raise SystemExit
    
    self._input = []
    
    for c in input:
      if c != 0:
        self._input.append(c)
      else:
        break
    print self._input
    
  def getAvg(self):
    self._input.sort()
    self._input = self._input[:-3]
    return sum(self._input) * 1.0 / len(self._input)
    
if __name__ == '__main__':
  input = NotMaxThree([3, 7, 12, 2, 25, 8, 9, 13, 10, 0])
  print input.getAvg()

- tosay.net March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <set>

int main()
{
   int vals[] = {2, -5, 1, 8, 2, -8, 9, 4, 2, 6, 0, 8, 3, 5, 6, 5};
   
   std::multiset<int> m_set;
   
   // Shove values into multiset.
   for (int i = 0; i < 16; i++)
      m_set.insert(vals[i]);
        
   int setSize = m_set.size();
   float avg = 0;
   
   // Get iterator to end of multiset, then back it down by 3 (multiset iterator doesn't support subtraction.
   std::multiset<int>::iterator x = m_set.end();
   for (int i = 0; i < 3; i++)
      x--;
   
   // Print out values, and accumulate average
   for (std::multiset<int>::iterator i = m_set.begin(); i != x; i++)
   {
      std::cout << *i << std::endl;
      avg += *i;
   }
      
   std::cout << "Average: " << avg / (setSize - 3) << std::endl;
      
}

- SixDegrees August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity of the above: building multiset is O(log(N)), but computing average afterward is O(N).

- SixDegrees August 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TermByZero{
	public static void main(String[] args) throws Exception
	{ 
	    int []arr = {3,7,12,2,25,8,9,13,10,0,9,4,2,56};
	    int tot =0,sum=0,len=arr.length;
	    for(int i=0;i<=len;i++)
	    {
	    	if(i>=3)
	    	{
	    	   tot++;
	    	   sum = sum + arr[len-i];
	    	   continue;
	    	}
	    	int index = i;
	    	while(index < len)
	    	{
	    		if(arr[index+1]==0)
		    	     {len =index;
		    	       break;
		    	     }
	    		if(arr[index] > arr[index+1])
	    		{
	    			int temp = arr[index];
	    			arr[index]=arr[index+1];
	    			arr[index+1] = temp;
	    		}
	    		index++;
	    	}
	    }
        float avg=(float)sum/tot;
        System.out.println(avg);	
    }
}

- Anonymous August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TermByZero{
	public static void main(String[] args) throws Exception
	{ 
	    int []arr = {3,7,12,2,25,8,9,13,10,0,9,4,2,56};
	    int tot =0,sum=0,len=arr.length;
	    for(int i=0;i<=len;i++)
	    {
	    	if(i>=3)
	    	{
	    	   tot++;
	    	   sum = sum + arr[len-i];
	    	   continue;
	    	}
	    	int index = i;
	    	while(index < len)
	    	{
	    		if(arr[index+1]==0)
		    	     {len =index;
		    	       break;
		    	     }
	    		if(arr[index] > arr[index+1])
	    		{
	    			int temp = arr[index];
	    			arr[index]=arr[index+1];
	    			arr[index+1] = temp;
	    		}
	    		index++;
	    	}
	    }
        float avg=(float)sum/tot;
        System.out.println(avg);	
    }
}

- kanha August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using MaxHeap.

public class epic20 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int t;
		int count = 0, sum = 0;
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>(3);
		do {
			t = sc.nextInt();
			sum += t;
			count++;
			if (pq.size() < 3)
				pq.add(t);
			else {
				if (t > pq.peek()) {
					pq.poll();
					pq.add(t);
				}
			}
		} while (t != 0);

		int threeMax = (pq.poll() + pq.poll() + pq.poll());
		sum -= threeMax;
		count -= 4;// including 0

		System.out.println((double) sum / count);

	}

}

- ajay October 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def f1(series):
    cnt = 0
    sum_num = 0.0
    max_list = []
    for s in series:
        sum_num+=s
        cnt+=1
        if s==0:
            break
        if (len(max_list)<3):
            max_list.append(s)
        elif min(max_list)<s:
            max_list.remove(min(max_list))
            max_list.append(s)

    if (cnt<=4):
        return 0
    else:
        return (sum_num-sum(max_list))/(cnt-4)

- Anonymous November 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Heap, complexity O(n*log3), almost linear
3 variables for 3 largest so far, complexity O(3n), linear with constant
Quick select, complexity O(2n). after select, need to sum all those non-negligible elements.
Quick select using hoare partition:

int hoare(int A[], int st, int ed) {
	if (st == ed) return st;
	int left(st - 1), right(ed + 1), key(A[st]);
	while (1) {
		while (A[++left] < key);
		while (A[--right] > key);
		if (left < right) swap(A[left], A[right]);
		else return right;
	}
}

int select(int A[], int st, int ed, int k) {
	if (k < st || k > ed) return -1;
	if (st == ed) return A[st];
	int pivot = hoare(A, st, ed);
	if (pivot >= k) return select(A, st, pivot, k);
	return select(A, pivot + 1, ed, k);
}

double averageWithout3Largest(int A[], int n) {
	if (n <= 3) return 0;
	select(A, 0, n - 1, n - 3);

	int sum = 0;
	int totalnum = n - 3;
	for (int i = 0; i < n - 3; ++i) {
		if (A[i] == 0) --totalnum;
		else sum += A[i];
	}
	return double(sum) / double(totalnum);
}

IMO, getting quick select right during an interview is hard enough though...

- XiaoPiGu December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if __name__ == '__main__':
	numList = [3,7,12,2,25,8,9,13,10,0]
	numList.pop(len(numList)-1)
	for i in range(3):
		numList.pop(numList.index(max(numList)))
	print "Average is " + str(float(sum(numList))/float(len(numList)))

- natch January 15, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More