0

It's a test on hackerank that asks for the following program. The program takes input, stores it in the dictionary, and checks numerous inputs against this newly created dictionary.

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

int main()
{
    int create, notPresent;
    string key, value, name;
    map<string, string> phonebook;
    map<string, string>::iterator iter;

    cin >> create;
    for (int i = 0; i < create; ++i)
    {
        cin >> key;
        cin >> value;
        phonebook[key] = value;
    }

    while (cin >> name)
    {
        notPresent = 0;
        iter = phonebook.begin();

        while (iter != phonebook.end())
        {
            if (name == iter->first)
                cout << iter->first << "=" << iter->second << endl;
            else
                notPresent++;
            iter++;
        }

        if (notPresent == create)
        {
            cout << "Not found" << endl;
        }
    }

    return 0;
}
Abdul Muqeet
  • 21
  • 5
  • 1
    Well to begin with, if you find the entry in the map you don't have to loop any more. To continue perhaps the map doesn't have to be ordered so you can use an unordered map instead? And to continue some more, why not just use the `find` function of the map? – Some programmer dude Apr 13 '22 at 11:11
  • A note of warning: Sites like hackerrank are not teaching or learning resources. And while your code is pretty nice (maybe except that [`using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)) most beginners using such sites tend to learn the bad habits (and sometimes even non-standard or invalid code) used in the examples. The "correct" way to use such sites are as a kind of programmers puzzles or brain-teasers, and require intimate knowledge of the selected language and computer-science structures and algorithms. – Some programmer dude Apr 13 '22 at 11:40

2 Answers2

1

use map::find instead of manually looping over all entries of dictionary, as it has O(log(n)) complexity instead of O(n) complexity.

Ahmed AEK
  • 8,584
  • 2
  • 7
  • 23
  • 1
    This. If you have to implement yourself an algorithm, map::find is based on Red-Black tree if I remember correctly. – Vollfeiw Apr 13 '22 at 11:14
  • i am usually against implementing your own algorithms until you find that the standard/premade stuff is bad for a certain task and is causing the bottleneck. – Ahmed AEK Apr 13 '22 at 11:18
  • 1
    Depends on the goal. If your goal is to learn the logic behind algorithms, it's always a good start to check something that already work, trying to tweak it (ex : Bubble Sort, the classic one, can be lower than O(n²), and with simple logic) – Vollfeiw Apr 13 '22 at 11:23
  • 2
    @Vollfeiw The `std::map` implementation itself is usually in the form of a RB-tree. The `find` function just traverses this tree. – Some programmer dude Apr 13 '22 at 11:28
  • It worked! Posting the code below – Abdul Muqeet Apr 13 '22 at 11:33
0

Code upgraded!

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

int main()
{
    unsigned int create, notPresent = 0;
    string key, value, name;
    map<string, string> phonebook;
    cin >> create;

    for (int i = 0; i < create; ++i)
    {
        cin >> key;
        cin >> value;
        phonebook[key] = value;
    }

    while (cin >> name)
    {
        auto it = phonebook.find(name);
        if (it == phonebook.end())
            cout << "Not found\n";
        else
            cout << it->first << "=" << it->second << endl;
    }
    return 0;
}
Abdul Muqeet
  • 21
  • 5
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Cristik Apr 13 '22 at 12:56