Adobe Interview Question
MTSsCountry: India
Interview Type: In-Person
Main problem is with delete is ith entry is being deleted then (i+1)th should become the ith entry for nthentry(i);
How are you making sure this?
heap can be implemented to solve ordering problem and node of the heap would be structure .
We can use a map or multimap depending upon if the key is unique or not.
I guess it should solve the problem
We can use a doublylinked list in association with hash map. The map will have key as name i.e "abc","def" etc and the value field will be pointer to the doubly link list node which contains the numerical value. Whenever we delete the the entry will be removed both from the map as well as the doubly linked list. Becoz of the doubly linked list the order will be maintained. All operation can be done in O(1).
Hashmaps should work I guess.
By using 2 maps...1st for (name,age) pairs and 2nd for (index,name) pairs should solve the problem.
#include <iostream.h>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <cctype>
using namespace std;
void work() {
map<string, int> name_age;
map<int,string> index_name;
name_age["abc"] = 12;
name_age["pqr"] = 1;
name_age["stu"] = 13;
index_name[0] = "abc";
index_name[1] = "pqr";
index_name[2] = "stu";
cout << name_age["abc"] << endl;
cout << index_name[1];
name_age.erase("abc");
cout << "Entry deleted";
cout << name_age["nishant"];
}
Please replace last statement cout << name_age["nishant"]; with
cout << name_age["abc"];
I hope this way we can implement .
Point me if anything seems wrong.
#include <iostream.h>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <cctype>
using namespace std;
void work() {
map<string, int> name_age;
map<int,string> index_name;
map<int,string> index_name_temp;
std::map< int, string >::iterator it;
string temp = "abc";
name_age["abc"] = 12;
name_age["pqr"] = 1;
name_age["stu"] = 13;
index_name[0] = "abc";
index_name[1] = "pqr";
index_name[2] = "stu";
name_age.erase("abc");
cout << endl;
for ( it = index_name.begin(); it != index_name.end(); ++it )
{
string str = (*it).second;
if(str.compare(temp) == 0) {
it->second = " ";
}
cout << (*it).first << " " << (*it).second << endl;
}
}
int main() {
cout << "hi";
work();
return 0;
}
In this code we are maintining 2 tables we will delete the entry from first table but from the next table we will simply make the value as empty, we can't delete the entry from second table as nthentry() we have to maintain, so whenerever we will be returning the value from nthentry() we will see if value is not empty its means the entry is not deleted from frst one else its deleted go for n+1 entry.
Hope its clear.
We can maintain one map for name, valueIndex and one for index, value and one integer variable for maxIndex. By valueIndex i mean it will hold both value and the index.
- Naveen Reddy Mandadi October 20, 2012maxIndex will be -1 initially.
For insert we add an entry to name valueIndex map and an entry to index, value map using the maxIndex and incrementing the maxIndex after that.
search(name) is nothing but get from name value map.
nthentry is nothing but get from index value map using n as the key.
delete is getting the entry from name, valueIndex map, deleting the corresponding entry in index, value map and then deleting the name, valueIndex map entry.
Assuming delete(2) what is mentioned in the question is zero based and not 1 based.