CareerCup

how about interval tree for the second problem?

since names can repeat, the hashCode obtained from using the names as key will cause a problem. imagine

HashMap<String, Integer> marks = new HashMap<String, Integer>();
		
		marks.put(new String("S1"), 10);
		marks.put(new String("S2"), 11);
		marks.put(new String("S1"), 12);

here 2 students have the name S1. hence, the hashmap would check if "S1".equals("S1").. since the string S1 will be allocated in the string pool, this check would return true and the value 10 (i.e. the marks initially stored) would be over-written with marks 12.

so using hashMap doesnt seem like the right data structure.

Comments from ExpertExchange:
http://www.experts-exchange.com/Programming/Languages/CPP/Q_21857806.html


I was thinking about an array of struct, linked list or a hashtable but there are trade-offs in each case. If I use a linked list, then I will need extra memory to store pointers, lookup will be O(n) but insetion and deletion will be more efficient compared to an array. Or I can use a hashtable but in a hashtable, there is more lookup overhead than in an array and sorting will be a problem in a hashtable. It will be easier to sort using linked list. In a binary tree, sorting, insertion and deletion will be fastest - O(logn).
Any suggestions?

Comments from ExpertExchange:
http://www.experts-exchange.com/Programming/Languages/CPP/Q_21857806.html


You can use a map (or dictionary) for quick access:

If there is only one mark for each student, you would have


#include <map>
#include <string>
using namespace std;

...


enum Mark { A, B, C, D, E, F };

...

map<string, Mark> mapStudents;
mapStudents["Joe"] = A;
mapStudents["Mary"] = E;
mapStudents["Bob"] = C;
mapStudents["Eve"] = B;
mapStudents["Dan"] = A;

You might iterate the (sorted) map by

map<string, Mark>::iterator it;
for (it = mapStudents.begin(); it != mapStudents.end(); ++it)
cout << it->first << " " << it->second << endl; // name mark


If there are more marks, you could use a vector<Mark> like that:

#include <vector>

... // same as above


enum Discipline { MATH, PHYS, CHEM, BIO, MAX_DISC };

... // same as above


map<string, vector<Mark> > mapStudents;

...

Mark m[MAX_DISC] = { A, C, B, A };
vector<Mark> marks( m[0], m[MAX_DISC] );
mapStudents["Joe"] = marks;
// or ...
vector<Mark>& marksEve = mapStudents["Eve"];
marksEve.resize(MAX_DISC);
marksEve[MATH] = B;
marksEve[PHYS] = A;
marksEve[CHEM] = A;
marksEve[BIO] = D;

btrees for storing the range of students

Couldnt get what is being asked in this question?

Any answers?? Need some help here..

Java - HashMap<String,Integer>