Amazon Interview Question SDE-2s
Team: Aelxa
Country: India
The first 3 cities are developing so we have 25 certain votes for Mr X.
The rest 7 cities are developed and 3 from them are going to vote for Mr X.
Let's say we sort the remaining cities according to their number of voters. The array will looking something like that: 5,6,8,12,17,20,22.
The maximum no of votes will then be: 25 + (17+20+22) = 64.
In than case the minimum votes against Mr X will be:
(Total votes) - (Max votes for Mr X) = 115 - 64 = 51
If all developing cities will vote for Mr X, then he has 25 certain votes.
From the developed cities, 3 of them are going to vote for Mr X.
If we order the developed cities according to their number of votes, we will have the following array: 5,6,8,12,17,20,22.
The maximum number of votes for Mr X will be:
the number of certain votes plus the votes of the 3 biggest cities 25 +(17+20+22)=64
The minimum votes against Mr X are: (Total Votes) - (Max Votes for Mr X) = 115-64 = 51
It was a straight question.I use a min heap to find k largest no. Sample test case passed. But after the final submission it got rejected. I am pasting my code. May be somebody will help to point out the mistake in the solution.
public class Source2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T= in.nextInt();
while(T> 0) {
solve(in);
T--;
}
}
private static void solve(Scanner in) {
final int totalCity= in.nextInt();
final int developedCityFavVoteCount= in.nextInt();
int totalPeopleDevelopingCity= 0;
int totalPeopleDevelopedCity= 0;
final int DEVELOPED= 1;
final int DEVELOPING= 0;
// Min heap to get the top k fav vote
PriorityQueue<Integer> minHeap= new PriorityQueue<>(developedCityFavVoteCount, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return a.compareTo(b);
}
});
int k= 0;
for(int i= 1;i<= totalCity;i++) {
int developmentIndex= in.nextInt();
int people= in.nextInt();
if(developmentIndex== DEVELOPING) {
totalPeopleDevelopingCity+= people;
} else if(developmentIndex== DEVELOPED){
if(k< developedCityFavVoteCount) {
minHeap.offer(people);
k++;
} else {
if(minHeap.peek()<people) {
minHeap.poll();
minHeap.offer(people);
}
}
totalPeopleDevelopedCity+= people;
}
}
//count for total fav vote
int total_fav_vote= totalPeopleDevelopingCity;
//count for total fav vote in developed city
int total_fav_vote_developed= 0;
for(int i= 0;i< developedCityFavVoteCount;i++) {
total_fav_vote_developed+= minHeap.poll();
}
total_fav_vote+= total_fav_vote_developed;
int min_against_vote= totalPeopleDevelopedCity - total_fav_vote_developed;
System.out.println(total_fav_vote+" "+min_against_vote);
}
}
It was a straight question.I use a min heap to find k largest no. Sample test case passed. But after the final submission it got rejected. I am pasting my code. May be somebody will help to point out the mistake in the solution.
public class Source2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T= in.nextInt();
while(T> 0) {
solve(in);
T--;
}
}
private static void solve(Scanner in) {
final int totalCity= in.nextInt();
final int developedCityFavVoteCount= in.nextInt();
int totalPeopleDevelopingCity= 0;
int totalPeopleDevelopedCity= 0;
final int DEVELOPED= 1;
final int DEVELOPING= 0;
// Min heap to get the top k fav vote
PriorityQueue<Integer> minHeap= new PriorityQueue<>(developedCityFavVoteCount, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return a.compareTo(b);
}
});
int k= 0;
for(int i= 1;i<= totalCity;i++) {
int developmentIndex= in.nextInt();
int people= in.nextInt();
if(developmentIndex== DEVELOPING) {
totalPeopleDevelopingCity+= people;
} else if(developmentIndex== DEVELOPED){
if(k< developedCityFavVoteCount) {
minHeap.offer(people);
k++;
} else {
if(minHeap.peek()<people) {
minHeap.poll();
minHeap.offer(people);
}
}
totalPeopleDevelopedCity+= people;
}
}
//count for total fav vote
int total_fav_vote= totalPeopleDevelopingCity;
//count for total fav vote in developed city
int total_fav_vote_developed= 0;
for(int i= 0;i< developedCityFavVoteCount;i++) {
total_fav_vote_developed+= minHeap.poll();
}
total_fav_vote+= total_fav_vote_developed;
int min_against_vote= totalPeopleDevelopedCity - total_fav_vote_developed;
System.out.println(total_fav_vote+" "+min_against_vote);
}
}
/*
It is presidential election time.Mr X is fighting for the president.The country has N number of cities.
The cities are divided into developed & developing city on basis of a developemt index A.
If A is 1, then the city is developed. If A is 0, then the city is developing.
A close source to Mr X told that all the people from developing cities will vote for him while people
from only k number of developed cities will vote for him.
Find out the no of maximum vote in favour & minimum vote in against Mr X will get.
Input
------
10 3
0 12
0 6
0 7
1 8
1 12
1 17
1 20
1 22
1 5
1 6
First 2 line gives no of cities N= 10 & number of developed cities vote for Mr X k= 3
Next 10 lines give the development index A & number of people in the city
For example in the first line A= 0, no of people= 12
Algorithm -
1) Build the rank of residents by sorting the lines
2) Used quick sort to do that
3) Finally, computed the max & min votes prediction
Test Cases -
If all developing cities will vote for Mr X, then he has 25 certain votes.
From the developed cities, 3 of them are going to vote for Mr X.
If we order the developed cities according to their number of votes, we will have the following array: 5,6,8,12,17,20,22.
The maximum number of votes for Mr X will be:
the number of certain votes plus the votes of the 3 biggest cities 25 +(17+20+22)=84
The minimum votes against Mr X are: (Total Votes) - (Max Votes for Mr X) = 115-84 = 31
Time & Space complexity
O(LogN)
O(N) - Auxilary Array
*/
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
typedef struct city_developed
{
int No_Of_City;
int No_Of_DevelopedCity_vote;
};
typedef struct development_index
{
int index;
int No_of_resident;
};
void printPresidentVotePrediction(city_developed city_developed_arr, development_index *development_index_arr, int development_index_arr_size, int *rank)
{
int total_certain_votes = 0, total_developed_votes = 0, total_votes = 0;
for (int i = 0; i < development_index_arr_size; i++)
{
if (development_index_arr[i].index == 0)
total_certain_votes += development_index_arr[i].No_of_resident;
total_votes += development_index_arr[i].No_of_resident;
}
for (int i = 0; i < city_developed_arr.No_Of_DevelopedCity_vote; i++)
{
total_developed_votes += rank[i];
}
cout << "The maximum number of votes for Mr X will be : the number of certain votes plus the votes of the 3 biggest cities = " << (total_certain_votes + total_developed_votes) << endl;
cout << "The minimum votes against Mr X are: (Total Votes) - (Max Votes for Mr X) = " << (total_votes - (total_certain_votes + total_developed_votes)) << endl;
}
// Function for comparing two students according
// to given rules
int compareTwoCity(const void* a, const void* b)
{
development_index *I1 = (development_index*)a;
development_index *I2 = (development_index*)b;
// If No_of_resident are not same then returns true for higher total
return (I2->No_of_resident - I1->No_of_resident);
}
// Fills ranks of all city residents
void computeRanks(development_index *a, int n, int *rank)
{
// Sort structure array using user defined
// function compareTwoCity()
qsort(a, n, sizeof(development_index), compareTwoCity);
// Assigning ranks after sorting
for (int i = 0, j = 0; i<n; i++, j++)
rank[j] = a[i].No_of_resident;
}
// Driver program to test above functions
int main()
{
city_developed city_developed_arr = { 10, 3 };
development_index development_index_arr[] = { {0,12}, {0,6}, {0,7}, {1,8}, {1,12}, {1,17}, {1,20}, {1,22}, {1,5}, {1,6} };
int development_index_arr_size = sizeof(development_index_arr) / sizeof(development_index_arr[0]);
int rank[sizeof(development_index_arr) / sizeof(development_index_arr[0])] = { 0 };
computeRanks(development_index_arr, development_index_arr_size, rank);
// Print ranks after sorting
/*for (int i = 0; i<sizeof(rank) / sizeof(rank[0]); i++)
cout << rank[i] << endl;*/
printPresidentVotePrediction(city_developed_arr, development_index_arr, development_index_arr_size, rank);
getchar();
return 0;
}
If all developing cities will vote for Mr X, then he has 25 certain votes.
- Dorianna May 04, 2017From the developed cities, 3 of them are going to vote for Mr X.
If we order the developed cities according to their number of votes, we will have the following array: 5,6,8,12,17,20,22.
The maximum number of votes for Mr X will be:
the number of certain votes plus the votes of the 3 biggest cities 25 +(17+20+22)=64
The minimum votes against Mr X are: (Total Votes) - (Max Votes for Mr X) = 115-64 = 51