新鲜G家店面

mojolady

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

题目是排名选举系统
刚刚面了狗家店面，题目是这样的：
假如，有4个可以选的candidate [红，黄，蓝，绿]。顺序[红，黄，蓝，绿] 代表红》黄》蓝》绿。每个选民提交自己的选票顺序，比如，选民a可以提交【绿，蓝，红，黄】，选民b可以提交【红，绿，蓝，黄】等等。写出下面算法完成选举：
第一

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

觉得这个题不太好做phone interview的candidate，做onsite还好。面试过程中，我们说半天都说不清楚。面试官一会说这样，一会儿又推翻之前说的，我真的是很懵逼。。。大家有没有碰到类似说不清的情况？

林微熙

LC 911变形???????

mojolady

林微熙发表于 2019-4-9 03:37
LC 911变形???????

感觉比911复杂多了。。。

mhsasd

选票占比怎么算的？

mojolady

mhsasd 发表于 2019-4-9 05:28
选票占比怎么算的？

出题人只说了上面那些，他说怎么算出选票分布要自己想。所以我就给了一个weight在不同的position上，然后计算的，不过也不知道对不对。

mojolady

直接给大家粘一卡他要的代码。。。。

import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
import java.util.Map;
import java.util.TreeSet;
import java.util.TreeMap;
/**
* Runs an instant runoff election.
* In an instant runoff election each voter submits a list of candidates,
* in order of preference. The first name on the list is the voter's
* first choice, the second the voter's second choice, etc. The voter
* need not list all of the candidates.
*
* The election is conducted in rounds. Each voter's first choice is
* tallied, and the candidate with the fewest first-place votes is
* eliminated. (If there is a tie one of the lowest vote-getters is chosen
* at random to be eliminated.) In each round the voter's top choice
* amongst the remaining candidates gets that voter's vote for that round.
* If no current candidate is on a voter's list that voter casts no vote
* for this round.
*
* The process ends when there is a single candidate left, who is declared
* the winner.
*
* This version is written in a procedural style, with lots of static methods.
*
* @author Scot Drysdale
*/
public class InstantRunoffProc {
private static boolean debugOn = true; // Print debugging output?
/**
* Creates a set of candidate names. A candidate is someone who appears
* on at least one ballot.
* @param ballots the set of ballots
* @return the set of candidate names
*/
public static Set<String> getInitialCandidates(List<List<String>> ballots) {
Set<String> candidateSet = new TreeSet<String>();
// Add all names on all ballots to the set. Adding a candidate who
// is already in the set does not change the set.
for(List<String> ballot : ballots)
if(ballot.size() > 0)
candidateSet.add(ballot.get(0));
return candidateSet;
}
/**
* Counts the number of votes that each candidate gets. Only current
* candidates can receive votes.
* @param candidates the current list of candidates
* @param ballots a set of lists of voter preferences
* @return the vote tally for each candidate
*/
public static Map<String, Integer> countVotes(Set<String> candidates,
List<List<String>> ballots) {
Map<String, Integer> voteTally = new TreeMap<String, Integer>();
// Set up an entry for each current candidate with no votes.
for(String candidate : candidates)
voteTally.put(candidate, 0);
// Tally up top choice on each ballot
for(List<String> ballot : ballots) {
String topChoice = getTopChoice(ballot, candidates);
if(topChoice != null) {
int currentTally = voteTally.get(topChoice);
voteTally.put(topChoice, currentTally + 1);
}
}
return voteTally;
}
/**
* Finds and returns the top choice among the remaining candidates.
* @param ballot a voter's ballot (preferential list of candidates).
* @param candidates the current set of candidates
* @return name of top choice in candidates.
*/
public static String getTopChoice(List<String> ballot, Set<String> candidates) {
Iterator<String> iter = ballot.iterator();
while(iter.hasNext()) {
String candidate = iter.next();
if(candidates.contains(candidate))
return candidate;
}
return null; // None of the candidates on ballot were in candidates
}
/**
* Finds the candidates with the fewest votes.
* @param candidates the current list of candidates
* @param voteTally a map from candidates to votes
* @return a list of candidates with the fewest votes.
*/
public static ArrayList<String> getLosers(Set<String> candidates,
Map<String, Integer> voteTally) {
ArrayList<String> loserList = new ArrayList<String>();
int minTally = Integer.MAX_VALUE; // Bigger than any possible vote count
for(String candidate : voteTally.keySet()) {
int candidateTally = voteTally.get(candidate);
if(candidateTally < minTally) { // Found new loser?
loserList.clear();
loserList.add(candidate); // Remember new loser
minTally = candidateTally;
}
else if(candidateTally == minTally)
loserList.add(candidate); // Have another with the same low tally
}
return loserList;
}
/**
* Picks random item from a list
* @list the list to choose from
* @return an item chosen randomly from list
*/
public static String pickRandomItem(ArrayList<String> list) {
return list.get((int) (Math.random()*list.size()));
}
/**
* Runs an instant-runoff election
* @param ballots the ballots for this election
* @return winner of the election
*/
public static String runInstantRunoffElection(List<List<String>> ballots) {
Set<String> candidates = getInitialCandidates(ballots);
// Run rounds until down to a single candidate
while(candidates.size() > 1) {
Map<String, Integer> voteTally = countVotes(candidates, ballots);
String loser = pickRandomItem(getLosers(candidates, voteTally));
candidates.remove(loser);
if(debugOn) {
System.out.println("Vote tally:\n" + voteTally);
System.out.println("Loser: " + loser);
}
}
if(candidates.size() > 0)
return candidates.iterator().next(); // Return the surviving candidate
else
return null;
}
/**
* Test program
*/
public static void main(String[] args) {
List<List<String>> ballots = new ArrayList<List<String>>();
System.out.println("Enter candidate names in order of preference,");
System.out.println("separated by spaces. End with a blank line.");
List<String> ballot;
Scanner in = new Scanner(System.in);
System.out.print("Enter a ballot: ");
String line = in.nextLine();
while(!line.equals("")) {
ballot = new ArrayList<String>();
Scanner inLine = new Scanner(line);
while(inLine.hasNext()) {
String candidate = inLine.next();
ballot.add(candidate);
}
ballots.add(ballot);
System.out.print("Enter a ballot: ");
line = in.nextLine();
}
String winner = runInstantRunoffElection(ballots);
if (winner != null)
System.out.println("The winner of the instant runoff election is: " +
winner);
else
System.out.println("No valid votes cast");
}
}

复制代码

大头菜

这个电面好狠啊楼主有消息了吗

mojolady

大头菜发表于 2019-4-23 05:20
这个电面好狠啊楼主有消息了吗

据掉了。。。哭😢

新鲜G家店面

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

浏览过的版块