cyrus
BAN USERInstead of calculating average each time from priority queue, it would be better to store it and keep on changing it without browsing whole queue
class TestResult {
int studentId;
String testDate=null;
int testScore;
public TestResult() {
// TODO Auto-generated constructor stub
}
TestResult(int studentId, int testScore){
this.studentId=studentId;
this.testScore=testScore;
}
}
class PriorityQueueWithAverage {
PriorityQueue<Integer> pq = new PriorityQueue<>();
Double avg = 0.0;
static int maxTestToConsider = 5;
public void add(int i) {
if (pq.isEmpty()) {
pq.add(i);
avg = (double) i;
}
else if (pq.size() < maxTestToConsider) {
avg = (((avg * pq.size()) + i) / (pq.size() + 1));
pq.add(i);
} else {
if (pq.peek() < i) {
int temp = pq.peek();
avg = (((avg * pq.size()) + i - temp) / (pq.size()));
pq.poll();
pq.add(i);
}
}
}
@Override
public String toString(){
return("AVG :"+avg+", Queue:"+pq);
}
}
public class FinalScoreQuestion {
Map<Integer, Double> calculateFinalScores(List<TestResult> results) {
Map<Integer, Double> finalScore = new HashMap<Integer, Double>();
Map<Integer, PriorityQueueWithAverage> nonFinalMapWithAverage = new HashMap<Integer, PriorityQueueWithAverage>();
for (TestResult testResult : results) {
if (!nonFinalMapWithAverage.containsKey(testResult.studentId)) {
PriorityQueueWithAverage tempPqWithAverage = new PriorityQueueWithAverage();
tempPqWithAverage.add(testResult.testScore);
nonFinalMapWithAverage.put(testResult.studentId,
tempPqWithAverage);
} else {
PriorityQueueWithAverage tempPqWithAverage = nonFinalMapWithAverage
.get(testResult.studentId);
tempPqWithAverage.add(testResult.testScore);
}
}
for (Iterator<Integer> iterator = nonFinalMapWithAverage.keySet()
.iterator(); iterator.hasNext();) {
int studentId = iterator.next();
finalScore
.put(studentId, nonFinalMapWithAverage.get(studentId).avg);
}
return finalScore;
}
}
public int removePathWithLessSum(TreeNode node, int sumRequired) {
int leftSum = 0, rightSum = 0;
if (node == null)
return 0;
if (node.getLeftNode() != null) {
leftSum = removePathWithLessSum(node.getLeftNode(), sumRequired
- node.getValue());
if ((leftSum + node.getValue()) < sumRequired)
node.setLeftNode(null);
}
if (node.getRightNode() != null) {
rightSum = removePathWithLessSum(node.getRightNode(), sumRequired
- node.getValue());
if ((rightSum + node.getValue()) < sumRequired)
node.setRightNode(null);
}
if (node.getRightNode() != null && node.getLeftNode() != null) {
return (Math.max(leftSum, rightSum) + node.getValue());
} else if (node.getRightNode() != null) {
return (rightSum + node.getValue());
} else if (node.getLeftNode() != null) {
return (leftSum + node.getValue());
} else {
if (node == this.getRootTreeNode() && node.getValue() < sumRequired) {
this.setRootTreeNode(null);
System.out.println(callCount);
return 0;
}
return node.getValue();
}
}
How about
- cyrus June 25, 2013