Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
1. Use Max heap to get rid of max 3 values (No need to say, exclude 0 in advance).
2. Then calculate average
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.
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();
}
}
#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();
}
#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;
}
sort the elements using (qsort) and find the average excluding the last three..o(n*logn)
do the bubble sort for three iterations to find the three maximum numbers and then take the average..
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);
#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 }
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.
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;
}
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.
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);
}
}
}
/*
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;
}
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()
#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;
}
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);
}
}
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);
}
}
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);
}
}
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...
Large,medium,Small reffered as l,m,s respectively,sum=0
- jeetu.mfp August 21, 2012take 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.