Can someone pls provide me the corner case for which my code is giving wrong ans
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
int numberOfTestCase = Integer.parseInt(st.nextToken());
for (int i = 0; i < numberOfTestCase; i++) {
st = new StringTokenizer(br.readLine());
int noOfTables = Integer.parseInt(st.nextToken());
int noOfOrders = Integer.parseInt(st.nextToken());
List<Integer> orders = new ArrayList<Integer>();
st = new StringTokenizer(br.readLine());
int count = 0;
List<Integer> list = new ArrayList<Integer>();
while (st.hasMoreElements()) {
int orderNumber = Integer.parseInt(st.nextToken());
list.add(orderNumber);
}
for (int j = 0; j < noOfOrders; j++) {
if (orders.size() == noOfTables) {
if (!orders.contains(list.get(j))) {
int temp = 0;
int found = -1;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int o : orders) {
boolean present = false;
int count1 = 0;
for (int r = j+1 ; r < list.size(); r++) {
if (list.get(r) == o) {
present = true;
count1++;
map.put(count1, o);
}
}
if (!present) {
found = 0;
break;
}
temp++;
}
if (found != 0) {
Map<Integer, Integer> m = sortByKeys(map);
Object myKey = m.keySet().toArray()[0];
temp = orders.indexOf(m.get(myKey));
}
orders.set(temp, list.get(j));
count++;
}
} else {
if (!orders.contains(list.get(j))) {
orders.add(list.get(j));
count++;
}
}
}
log.write("" + count);
log.newLine();
log.flush();
}
}
@SuppressWarnings({ "rawtypes", "unchecked" })
public static <K extends Comparable, V extends Comparable> Map<K, V> sortByKeys(
Map<K, V> map) {
List<K> keys = new LinkedList<K>(map.keySet());
Collections.sort(keys);
// LinkedHashMap will keep the keys in the order they are inserted
// which is currently sorted on natural ordering
Map<K, V> sortedMap = new LinkedHashMap<K, V>();
for (K key : keys) {
sortedMap.put(key, map.get(key));
}
return sortedMap;
}
For all “Whats wrong with my approach” questions, here is a python script to generate input file
from sys import stdout
from random import randint
T = randint(1,100)
stdout.write(str(T)+"\n")
while T:
N = randint(1,200)
M = randint(1,400)
stdout.write(str(N)+" "+str(M)+"\n")
while M:
stdout.write(str(randint(1,400))+" ")
M = M-1
stdout.write("\n")
T = T-1
Take any successfull solution compile it. Compile your solution and compare output of both. And seriously, stop expecting people to debug your code for you. Very few people have the time and commitment for that. Learn to debug yourself.
You can tweak the parameters to generate smaller testcases that you can debug with pen and paper.
Ok, I deduced the “farthest of time” thing after I was doing something with frequency, but still I kept getting WA even when I used Deque for same implementation. Can I please get the test file or case for which my code fails, I am pretty sure it is correct. WA, CLETAB
I’ve added an answer that uses optimal page replacement algorithm.
I’ve commented it so that everyone can get the idea.
Do have a look if you are stuck.
The solution wont work because there may be a case where a person will order once more after 1 second, and another will order 10 more times all after 3,4,5… seconds. Your algo will kick out the first guy, then reinvite, then kick him out again. Thats 3 tasks instead of the optimal 1 task. I have posted the odd test case.
Shouldn’t it be “If no such customer is present who’ll NOT order in future, we’ll pick a customer who will order in future in farthest of time.”? Or did I not understand that statement correctly?
