hitansu166
BAN USER- 1of 1 vote
AnswersIt is presidential election time.Mr X is fighting for the president.The country has N number of cities.
- hitansu166 in India for Aelxa
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| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 1of 1 vote
AnswersConstructing City
- hitansu166 in India for Alexa
In a country the cities are connected through roads of 3 types 1, 2, 3.
All the roads are bi-directional. The roads of a city has some restriction.
Road of type 3: both men and women can walk
Road of type 2: only women can walk
Road of type 1: only men can walk
Now the govt. wants to remove extra roads.But the cities should be connected for both men & women.
Connected means one should able to reach from one city to other & vice-versa.
Find out the maximum no of roads can be removed so that the cities can be accessible to both men & women.
Input:
5 5
1 2 3
2 3 3
3 4 3
5 3 2
5 4 1
First line gives no of cities & no of roads. Next each 5 lines gives city source, city destination, type for a roads.
5: no of cities 5: no of roads
1: city-1 2: city-2 3: type 3 road
o/p: 2| Report Duplicate | Flag | PURGE
Amazon SDE-2
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);
}
}
Can you please tell the logic ? I think you are checking by removing each road.
I use the idea of kruskal minimum spanning tree. First I tried to build roads with type 3 as both can access. If a road form a cycle,then that can be taken as extra road which can be remove. Similary for men tried to build road with type 3 & type 1 , for women type 3 & type 2. While building for men & women the type 3 road would have been already built.
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.
- hitansu166 May 04, 2017