[Show all top banners]
Back to: Kurakani General Refresh page to view new replies
 need help for assignment please!!!!!!!
Keywords associated with this thread

computer science programming c++ data structure hash
[VIEWED 3485 TIMES]
SAVE! for ease of future access.
Posted on 12-10-09 11:06 PM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

 

As the IT lead for this project, you are programming the software that will be used access employee data for a particular company.  The company wants to use this info for various things like company-wide email, Human Resources applications, submission to government authorities, etc.

After a series of discussions, you have come up with the following class design:

 Employee Node class

This class will hold info for an employee.

Employee’s id (a string)

Employee’s name

Access level (an int)

Terminated

 


 

 

Requirements

1) Implement a hash function (as a function, not a method.) The function must accept a string as a key and an int as the array size, and will return an int as the index hashed to. The return value MUST be in the range of 0 through (the second argument - 1).

2) Write the routine to populate the hash map (does not have to be a function). The hash map for the employees is backed by an array of some arbitrary size. To obtain the correct index to populate, you must use the hash function created in step 1, passing the employee id and the array size to the function. The array of employee pointers will be the ‘database’ from which the hash map will be populated.  You must use the getDirectory() code below to get a list of employees.  Note the getDirectory() function must not be changed (except to change the name of the Employee class, or perhaps the order of the data.)  Allowed changes will be discussed in class.

3) Implement a function (not a method) called getEmployee() that will accept an employee id string to look up in the hashmap. The function will access the appropriate index in the hashmap and if the employee is found the function returns a pointer to that employee, otherwise, NULL is returned. Hint: The solution is NOT to walk the hashmap array looking for a match to the employee id! That would be O(N) performance. The whole point of using hashmaps is to get very close to O(1).

The hash map can be made global for simplicity.

Notes

If you grasp the concept of hashing, pointers, and processing collections as we have done since day one, you realize this is an easy assignment. Do NOT make it harder than it is.

To keep this exercise easy, all class members may be made public.

Note, again for simplicity, when inserting employees into the hash map, more than one employee may hash to the same index, even though they contain different key values. For this exercise, if this occurs, the latter value should replace the previous one (do NOT delete the employee from memory for this exercise). Include comments in the function in requirement 3 to note this short coming and also include what should occur if this were a real life hash map.  Note that this explanation IS REQUIRED.

As always, we will be discussing the requirements and code, but you should know enough already to complete this exercise.

Walking the vector returned from getDirectory() may seem difficult at first, but review what you know about pointers and the problem is easily solved.  Another way (BIG hint), look up the at() method on vectors.

Note that if we found that the array size in our hashmap is not adequate, we could easily increase (or reduce) the size of the map by changing the MAPSIZE variable.


-----------------------------
 Starter code and database
/* A function that will obtain all employees in the company.
No 2 employees will ever share the same employee ID.
*/
vector<Employee*>* getDirectory()
{
 vector<Employee *> *employeeDatabase = new vector<Employee*>;
  
 employeeDatabase->push_back(new Employee("00729N", "William", 6, false));
 employeeDatabase->push_back(new Employee("10360F", "Karen", 3, false));
 employeeDatabase->push_back(new Employee("19789B", "Chang", 2, false));
 employeeDatabase->push_back(new Employee("11111G", "Vijay", 3, true));
 employeeDatabase->push_back(new Employee("21002F", "Carlos", 4, false));
 employeeDatabase->push_back(new Employee("00021X", "Mickey", 5, false));
 employeeDatabase->push_back(new Employee("19089B", "Woody", 3, true));
 employeeDatabase->push_back(new Employee("19783C", "Fredrick", 1, false));
 employeeDatabase->push_back(new Employee("00010A", "Henrietta", 6, false));
 employeeDatabase->push_back(new Employee("09980C", "Murtle", 4, true));
 employeeDatabase->push_back(new Employee("10360G", "Pat", 6, false));
 employeeDatabase->push_back(new Employee("00361G", "Irving", 9, false));
 employeeDatabase->push_back(new Employee("92323G", "Niles", 6, false));
 employeeDatabase->push_back(new Employee("92323R", "Lee", 5, false));
 employeeDatabase->push_back(new Employee("92324R", "Bernie", 7, false));
 employeeDatabase->push_back(new Employee("92325R", "Melvin", 4, true));
 employeeDatabase->push_back(new Employee("92326G", "Ruby-Joe", 1, false));
 employeeDatabase->push_back(new Employee("92327Y", "Petey", 1, false));
 employeeDatabase->push_back(new Employee("01320B", "Billie-Jean", 3, true));
 employeeDatabase->push_back(new Employee("51120A", "Ellen", 7, true));
 employeeDatabase->push_back(new Employee("77072D", "Dalton", 3, false));
 employeeDatabase->push_back(new Employee("44766D", "D'Jean", 6, false));
 employeeDatabase->push_back(new Employee("66498X", "Arnold", 2, false));
 employeeDatabase->push_back(new Employee("34565D", "Eddy", 1, false));
 employeeDatabase->push_back(new Employee("67762D", "Gerard", 9, false));
 employeeDatabase->push_back(new Employee("45542J", "Todd", 1, true));
 employeeDatabase->push_back(new Employee("00904A", "Olive", 2, false));
 employeeDatabase->push_back(new Employee("22981S", "Gloria", 3, false));
 employeeDatabase->push_back(new Employee("08159E", "Joan", 3, false));
 employeeDatabase->push_back(new Employee("20376S", "Alice", 3, false));
 employeeDatabase->push_back(new Employee("88159E", "Joan", 3, false));
 employeeDatabase->push_back(new Employee("08159E", "Yolanda", 3, false));
 employeeDatabase->push_back(new Employee("58159E", "Xiang-Lu", 3, false));
 employeeDatabase->push_back(new Employee("55156F", "Vera-Lee", 4, false));
 employeeDatabase->push_back(new Employee("89812G", "Shaune", 4, true));
 employeeDatabase->push_back(new Employee("05016F", "Marilyn", 5, false));
 employeeDatabase->push_back(new Employee("55157G", "Armand", 2, false));
 employeeDatabase->push_back(new Employee("55188B", "Don", 4, false));
 employeeDatabase->push_back(new Employee("55999Z", "Gertrude", 4, false));
 employeeDatabase->push_back(new Employee("78787F", "Samuel", 4, false));
 return employeeDatabase;
}
 //Declare the global hash map
 Employee** hashMap = NULL;
/*************
Put the functions here.
****************/

void main()
{
int MAP_SIZE = 29;  //The size of the hashmap
 
 //instantiate and initialize the hash map
 hashMap = new Employee*[MAP_SIZE];
 for(int a=0;a<MAP_SIZE;a++)
  hashMap[a] = NULL;
 //Get the Employee database.
 //The return is a pointer to a vector of Employee pointers
//This is NOT the hash map!
//You must walk this array to populate the hash map.
 vector<Employee*>* employeeDatabase= getDirectory();
//Populate the hashmap

//test the lookup with several sample id's

/*
Self study.  What code would you include here (after a lookup) to report whether the employee exists and whether he or she has been terminated? 
*/


 


Please Log in! to be able to reply! If you don't have a login, please register here.

YOU CAN ALSO



IN ORDER TO POST!




Within last 60 days
Recommended Popular Threads Controvertial Threads
What are your first memories of when Nepal Television Began?
निगुरो थाहा छ ??
Basnet or Basnyat ??
Sajha has turned into MAGATs nest
NRN card pros and cons?
Will MAGA really start shooting people?
मन भित्र को पत्रै पत्र!
Top 10 Anti-vaxxers Who Got Owned by COVID
TPS Work Permit/How long your took?
काेराेना सङ्क्रमणबाट बच्न Immunity बढाउन के के खाने ?How to increase immunity against COVID - 19?
Breathe in. Breathe out.
3 most corrupt politicians in the world
चितवनको होस्टलमा १३ वर्षीया शालिन पोखरेल झुण्डिएको अवस्था - बलात्कार पछि हत्याको शंका - होस्टेलहरु असुरक्षित
शीर्षक जे पनि हुन सक्छ।
Disinformation for profit - scammers cash in on conspiracy theories
someone please tell me TPS is here to stay :(
Nepali doctors future black or white usa ?
Doctors dying suddenly or unexpectedly since the rollout of COVID-19 vaccines
BREAKING: THE LEFT HAS LOST THE SUPREME COURT!
Another Song Playing In My Mind
Nas and The Bokas: Coming to a Night Club near you
NOTE: The opinions here represent the opinions of the individual posters, and not of Sajha.com. It is not possible for sajha.com to monitor all the postings, since sajha.com merely seeks to provide a cyber location for discussing ideas and concerns related to Nepal and the Nepalis. Please send an email to admin@sajha.com using a valid email address if you want any posting to be considered for deletion. Your request will be handled on a one to one basis. Sajha.com is a service please don't abuse it. - Thanks.

Sajha.com Privacy Policy

Like us in Facebook!

↑ Back to Top
free counters