Here is a traditional way of creating a Map and initializing it:
Map<Integer, String> map = new Map<>();
map.put(1, "apple");
map.put(2, "banana");
map.put(3, "cherry");
The following shortcut provides a quick way to initialize a Map in Java. Note that the Map.of() method only supports a maximum of 10 map entries. Also note that the Map.of() method returns a Map that is immutable.
Map<Integer, String> map = Map.of(1,"apple", 2,"banana", 3,"cherry);
The use of Maps tends to be significantly overrepresented in coding competitions. Thus, it is essential that you practice with them.
Before attempting the problems listed below, you may want to revisit the Map problems on the Data Structures Site. There is also review material there you may want to go over to refresh your understanding of Maps.
You can find the sample.txt and official.txt input files for these problems and their corresponding output files by clicking here. Note that you will need these files to test your program and verify that you have gotten the right answers.
Do the Morse Code problem from the 2022 Lockheed Problem Packet (easy).
Do the Get Out the Vote problem from the 2022 Lockheed Problem Packet (medium).
Do the It's an Enigma problem #19 from the 2018 Lockheed Martin Problem Packet (hard).
This last problem (It's an Enigma) was the hardest rated problem on the 2018 contest. The problem is best solved using ArrayLists because it is easier to rotate the elements in an ArrayList than an Array or Map. However, you are being asked to do the problems using Maps to get more practice on the Map data structure.
The Get Out the Vote problem from the 2022 Lockheed Martin Problem Packet is of medium difficulty. You should try to solve the problem without looking at these hints as that would be the closest to replicating the competitive environment. But if time is limited or if you are just getting started in your competitive programming journey, you can use these hints as well as the supplied snippets of code (see below) to make the problem more manageable.
When the tally the votes on a round, if several candidates are tied for last, you should disqualify all of them before going to the next round.
Use a TreeMap (instead of a HashMap) so that your Map entries will remain sorted. This will be useful since you need to know which entries have the most and least votes after each round.
In your class, you should declare a Map of the type: SortedMap<Character, Integer> candidates; Note that SortedMap is the interface type wherease the TreeMap is the concrete class.
In this project, you will need to convert a Map to a List to make it easier to parse, sort, etc. This will give you a chance to practice using the Map.Entry datatype.
public class P17GetOutTheVote {
public static void main(String[] args) throws Exception {
File f = new File("sample.txt");
Scanner scanner = new Scanner(f);
int trials = Integer.parseInt(scanner.nextLine());
for(int i = 0; i < trials; ++i) { // do for each test case in the input file
P17GetOutTheVote election = new P17GetOutTheVote(scanner);
election.go(); // you have to write this part
}
}
public P17GetOutTheVote(Scanner scanner) {
String[] tokens = scanner.nextLine().split(" ");
int voteCount = Integer.parseInt(tokens[0]);
int candidatesCount = Integer.parseInt(tokens[1]);
this.votes = new String[voteCount];
for(int i = 0; i < voteCount; ++i) {
this.votes[i] = scanner.nextLine();
}
}
private void go() {
/* you have to write the go method. In this method you should tally the votes in each round. figure out which candidate(s) have the lowest total and disqualify them. repeat the process until one candidate has the majority of votes (more than 50%). */
}
private int tally() {
/* this method will tally the votes for each round and return the percentage of votes if there is a clear winner. it should return 0 if there was no clear winner */
}
/* here is one technique for disqualifying a candidate at the end of a round */
private void disqualify(Character c) {
if (c != null) {
for(int i = 0; i < this.votes.length; ++i) {
this.votes[i] = this.votes[i].replace(c.toString(), "");
}
}
}
}