## Adobe Interview Question for MTSs

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.
maxIndex 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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

Comment hidden because of low score. Click to expand.
0
of 0 votes

heap can be implemented to solve ordering problem and node of the heap would be structure .

Comment hidden because of low score. Click to expand.
0
of 0 votes

deletion will take again logn order in case of heap

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hash Table ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use a map or multimap depending upon if the key is unique or not.
I guess it should solve the problem

Comment hidden because of low score. Click to expand.
0
of 0 votes

With maps we can't maintain the order of elements. If you keep incremental count before inserting word, deleting a word would invalidate such a counter.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 votes

How do you implement nthentry(n) on this stuff that takes a constant time?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Initially he asked me only insert search and getnth to implement in O(1). using two hash map I answered but again he asked to delete also in O(1) and order should be maintained.
I was not able to answer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hashmaps should work I guess.
By using 2 maps...1st for (name,age) pairs and 2nd for (index,name) pairs should solve the problem.

Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem is with delete. after deleting ith entry (i+1)th entry should become ith entry. How is it being ensured?

Comment hidden because of low score. Click to expand.
0
of 0 vote

It is not possible theoretically. look at the discussion here:

cs.stackexchange.com/questions/1970/data-structure-with-search-insert-and-delete-in-amortised-time-o1

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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"];

}

Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

here std:map means you are using tree. So, rearrangement to maintain order will take o(log n) time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Treemap I guess

Comment hidden because of low score. Click to expand.
0
of 0 votes

Treemap insert and search are not O(1), they are O(logn)

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More