Epic Systems Interview Question
Software Engineer / Developers#include<stdio.h>
main()
{
int n,cnt=0,sum=0,max1,max2,max3,i=0,avrg;
while(i<3)
{
scanf("%d",&n);
if(i==0)
max1=n;
if(i==1)
max2=n;
if(i==2)
max3=n;
i++;
sum+=n;
}
while(1)
{
scanf("%d",&n);
if(n==0)
break;
sum+=n;
cnt++;
if(n>max1 && n<max2)
max1=n;
if(n>max2 && n<max3)
{
max1=max2;
max2=n;
}
if(n>max3)
{
max1=max2;
max2=max3;
max3=n;
}
}
avrg=(sum-(max1+max2+max3))/(cnt);
printf("%d\n",avrg);
}
Does anyone spot the boo-boo in garret's solution? I'll give you a big hint: integer division!
Other than that, its simple and fine. O(n) solution though there are 3*n comparisons. There should be cleverer ways to do this though. For instance, building a max-heap out of your input and extracting the max three times. Then average the remaining items. If the interviewer allows you to use STL / Java library functions, this would be trivial, and a lot faster too, since building a heap from a complete input set is 2(N - lg(n)) comparisons, and removing the max 3 times is another 3*lg(n) comparisons. But if you're expected to write the heap functions yourself right there, stick with garret's solution!
C# Code
using System;
using System.Collections.Generic;
using System.Text;
namespace numberprint
{
class Program
{
static void Main(string[] args)
{
//string StringInput="";
string StringInput="";
int[] Max = new int[3];
int count = 0;
int temp = 0;
int sum = 0;
double ave = 0.0;
while (StringInput!= "0")
{
if (StringInput != "")
{
count++;
if (count <= 3)
Max[count - 1] = Convert.ToInt16(StringInput);
else
{
for (int i = 0; i < 3; i++)
{
if (Convert.ToInt16(StringInput) > Max[i])
{
temp = Max[i];
Max[i] = Convert.ToInt16(StringInput);
StringInput = Convert.ToString(temp);
}
}
sum += Convert.ToInt16(StringInput);
}
}
StringInput = (string)Console.ReadLine();
}
count = count - 3;
ave = sum / count;
Console.WriteLine(ave);
Console.ReadLine();
}
}
}
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
int main()
{
vector<int> v(0);
int n1, x;
do
{
cout<<"enter the no.\n";
cin>>n1;
v.push_back(n1);
}
while(n1 != 0);
int l1, l2, l3;
l1 = v[0];
l2 = v[0];
l3 = v[0];
for(int i = 1; i < v.size(); i++)
{
if(v[i] > l1) { l1 = v[i]; }
}
for(i = 1; i < v.size(); i++)
{
x = v[i];
if(x > l2 && x < l1) { l2 = x; }
}
for(i = 1; i < v.size(); i++)
{
if(v[i] > l3 && v[i] < l2 && v[i] < l1 ) { l3 = v[i]; }
}
int sum = 0;
for(int j = 0; j<v.size(); j++)
{
sum += v[j];
}
double average = (sum - (l1+l2+l3))/(v.size()-1-3);
cout<<average<<endl;
return 0;
}
#include <iostream>
using namespace std;
int main (int argc, char* argv[])
{
int input = 0;
int count = 0;
double sum = 0.0;
int maxThree[3] = {0};
while (cin >> input)
{
if (input == 0) break;
if (count < 3)
{
maxThree[count++] = input;
}
else
{
for (int i = 0; i < 3; i++)
{
if (maxThree[i] < input)
{
int temp = input;
input = maxThree[i];
maxThree[i] = temp;
}
}
count++;
sum += input;
}
}
cout << "Average: " << sum/(count-3 <= 0 ? 1 : count-3) << endl;
for (int i = 0; i < 3; i++)
{
cout << maxThree[i] << endl;
}
return 0;
}
how abt :
Step1: keep taking user Input and keep storing in an array
Step2: On being flagged to stop, just apply QuickSort [nlog(n) complexity]
Step 3: Print first n-3 elements
Any comments ?
header
--------------
#include <iostream>
#include <vector>
#include <algorithm>
class NumMax
{
public :
void push(int num);
int calculate();
private:
std::vector<int> nos;
static const int max =3;
int max3[max];
};
cpp file
-------
#include "NumMax.h"
void NumMax::push(int num) {
nos.push_back(num);
}
int NumMax::calculate() {
int avg = 0;
std::vector<int>::iterator it;
std::sort(nos.begin(), nos.end());
std::reverse(nos.begin(), nos.end());
if(nos.size() < 4)
{
return avg;
}
for(it=nos.begin()+3; it != nos.end() ;it++)
{
//std::cout << *it;
avg += *it;
}
return avg;
}
void main() {
int number;
int avg;
std::cout<< "---Program to find the max of numbers-- \n";
std::cout << "Enter the numbers and 0 to end \n";
NumMax ev;
for ( ; ; )
{
std::cin >> number;
if (number == 0)
break;
ev.push(number);
}
//avg = ev.calculate();
std::cout << "The average is : " << ev.calculate() << std::endl;
}
Complete Code:
#include<conio.h>
#include<iostream>
using namespace std;
void main()
{
int max[3]={0,0,0};
float avg=0,sum=0;
int count=0,num;
cin>>num;
while(num !=0)
{
count++;
if(num<max[1] && num>=max[2])
{
max[2]=num;
}
if(num<max[0] && num>=max[1])
{
max[2]=max[1];
max[1]=num;
}
if(num>=max[0])
{
max[2]=max[1]; //shifting
max[1]=max[0];
max[0]=num;
}
sum += num;
cin>>num;
}
cout<<"\nno of elements= "<<count;
if(count>3)
avg=(sum-max[0]-max[1]-max[2])/(count-3);
cout<<"\n first max= "<<max[0];
cout<<"\n second max= "<<max[1];
cout<<"\n third max= "<<max[2];
cout<<"\n avg= "<<avg;
getch();
}
import java.io.*;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Gagan
*/
public class Max3Demo {
static int inp = 0;
static boolean loop = true;
public static void main(String args[]){
int max1 = 0;
int max2 = 0;
int max3 = 0;
int sum=0, ctr=0;
while (loop){
System.out.println("enter number");
BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
try{
inp = Integer.parseInt(br.readLine());
// System.out.println("input: "+inp);
}catch(IOException e) {System.out.println(e);}
if(inp>=max1){
int temp1 = max1;
int temp2 = max2;
max1 = inp;
max2 = temp1;
max3 = temp2;
}
else if(max1>inp && inp>=max2){
int temp;
temp = max2;
max2 = inp;
max3 = temp;
}
else if(max2>inp && inp>= max3)
max3 = inp;
sum = sum+inp;
ctr++;
if(inp == 0) loop = false;
//System.out.println(loop);
}
System.out.println(max1+", "+max2+", "+max3);
System.out.println("sum: "+ (sum-(max1+max2+max3)));
System.out.println("ctr: "+ (ctr-4));
System.out.println("Avrage: "+ (sum-(max1+max2+max3))/(ctr-4));
}
}
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int max1, max2, max3;
void b_sort()
{
int t1, t2, t3;
t1 = max1;
t2 = max2;
t3 = max3;
if(t1>=t2 && t1>=t3)
{
if(t2>=t3)
{max1=t1; max2=t2; max3=t3;}
else
{max1=t1; max2=t3; max3=t2;}
}
else
{
if(t2>=t1 && t2>=t3)
{
if(t1>=t3)
{max1=t2; max2=t1; max3=t3;}
else
{max1=t2; max2=t3; max3=t1;}
}
else
{
if(t1>=t2)
{max1=t3; max2=t1; max3=t2;}
else
{max1=t3; max2=t2; max3=t1;}
}
}
}
int main()
{
int i, j, last_number, count=0;
long total;
double average;
printf("Keep on entering numbers:\n");
while(last_number != 0)
{
scanf("%d",&last_number);
if(count == 0)
{
max1 = last_number;
}
if(count == 1)
{
max2 = last_number;
}
if(count == 2)
{
max3 = last_number;
}
if(count>2)
{
if(last_number>max1 || last_number>max2 || last_number>max3)
{
b_sort();
total = total + max3;
max3 = last_number;
}
else
{
total+=last_number;
}
}
count++;
} // end while
average = total/(count-4);
printf("Average excluding 3 highest numbers = %lf",average);
return 0;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Average_without3largest
{
class Program
{
static void Main(string[] args)
{
int max1=0, max2=0, max3=0,count =0,sum=0,i=0;
float average = 0;
List<int> numbers = new List<int>();
Console.Write("Enter the numbers : Enter 0 to stop:");
int n;
while ( (n=Convert.ToInt32(Console.ReadLine()))!=0)
{
count++;
if (n >= max3)
{
if (n >= max2)
{
if (n >= max1)
{
int t = max1;
max1 = n;
int f = max2;
max2 = t;
t = max3;
max3 = f;
sum = sum + t;
if (t != 0)
numbers.Add(t);
}
else
{
int t = max2;
max2 = n;
int f = max3;
max3 = t;
sum = sum + f;
if (f != 0)
numbers.Add(f);
}
}
else
{
int t = max3;
max3 = n;
sum = sum + t;
if (t != 0)
numbers.Add(t);
}
}
else
{
sum = sum + n;
numbers.Add(n);
}
}
average = ((float)sum / (float)(count-3));
Console.WriteLine("The sum of numbers is :"+sum);
Console.WriteLine("The total number of elements is :"+ count);
Console.WriteLine("The Average of numbers without the three largest is :" + average);
Console.WriteLine("The List of numbers are :");
foreach (int num in numbers)
{
Console.WriteLine(num);
}
Console.Read();
}
}
}
namespace Average_without3largest
{
class Program
{
static void Main(string[] args)
{
int max1=0, max2=0, max3=0,count =0,sum=0,i=0;
float average = 0;
List<int> numbers = new List<int>();
Console.Write("Enter the numbers : Enter 0 to stop:");
int n;
while ( (n=Convert.ToInt32(Console.ReadLine()))!=0)
{
count++;
if (n >= max3)
{
if (n >= max2)
{
if (n >= max1)
{
int t = max1;
max1 = n;
int f = max2;
max2 = t;
t = max3;
max3 = f;
sum = sum + t;
if (t != 0)
numbers.Add(t);
}
else
{
int t = max2;
max2 = n;
int f = max3;
max3 = t;
sum = sum + f;
if (f != 0)
numbers.Add(f);
}
}
else
{
int t = max3;
max3 = n;
sum = sum + t;
if (t != 0)
numbers.Add(t);
}
}
else
{
sum = sum + n;
numbers.Add(n);
}
}
average = ((float)sum / (float)(count-3));
Console.WriteLine("The sum of numbers is :"+sum);
Console.WriteLine("The total number of elements is :"+ count);
Console.WriteLine("The Average of numbers without the three largest is :" + average);
Console.WriteLine("The List of numbers are :");
foreach (int num in numbers)
{
Console.WriteLine(num);
}
Console.Read();
}
}
}
<pre lang="" line="1" title="CodeMonkey75884" class="run-this">// I dont know why people make easy things complicated
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
vector<int> num;
while(cin>>n){
if(n==0)
break;
else
num.push_back(n);
}
sort(num.begin(),num.end());
unsigned long long result=0;
for(int i=0;i<num.size()-3;i++){
result += num[i];
}
cout<<(double)result/(num.size()-3)<<endl;
return 0;
}</pre>
<pre lang="" line="1" title="CodeMonkey53069" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println("Enter numbers for which you want to calculate the average");
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int max = 0;
ArrayList arr = new ArrayList();
while (num != 0) {
if (num >= max) {
arr.add(0, num);
max = num;
} // end if
else
arr.add(num);
num = scan.nextInt();
} // end while
int i = 3;
int sum = 0;
while (i < arr.size()) {
sum += arr.get(i);
i++;
} //end while
float average = 0f;
average = sum/(arr.size()-3)
System.out.println("Required average is: " + average);
}
}
</pre><pre title="CodeMonkey53069" input="yes">
</pre>
Here is a working C++ code:
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
int num, m1, m2, m3, sum=0, ct=3, x, y, z;
cin>>m1>>m2>>m3;
x=max(m1, max(m2, m3));
z=min(m1, min(m2, m3));
cout<<"x: "<<x<<endl;
cout<<"z: "<<z<<endl;
if (x==m1)
{
if (z==m2)
{
y=m3;
}
else if(z==m3)
{
y=m2;
}
}
if (x==m2)
{
if (z==m1)
{
y=m3;
}
else if(z==m3)
{
y=m1;
}
}
if (x==m3)
{
if (z==m1)
{
y=m2;
}
else if(z==m2)
{
y=m1;
}
}
m1=x; m2=y; m3=z;
sum+=(m1+m2+m3);
while (1)
{
cin>>num;
if (num==0)
{
break;
}
ct++;
sum+=num;
if (num>=m1)
{
m3=m2;
m2=m1;
m1=num;
}
else if(num>=m2)
{
m3=m2;
m2=num;
}
else if(num>=m3)
{
num=m3;
}
}
cout<<((sum-(m1+m2+m3))/(ct-3));
return 0;
}
- garret October 21, 2009