0

So I had a job interview two days ago and they used coderPad.io for it, which is pretty common for job interviews. As a matter of fact, I have another job interview coming up that uses coderPad as well, so I really need to ask this question.

Essentially what happened was that my algorithm was written correctly. My interviewer told me so. However, the hash map was not working and we started debugging until the interviewer got tired and ended the interview right there. I then received a rejection email a day later. The interviewer did however narrow it down to the insert function on the hash map. We tried different ways of inserting and it still did now work.

I had to write an algorithm that needed for me to find the frequency for every integer element in a vector. However, when I had print the contents of the hash map, the frequency is always 1 for each element when it is not supposed to be 1 for each element. This had cost me the interview process to continue. I have recreated the algorithm on coderPad just now and the same issue is occurring. Here is the code:

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

// To execute C++, please define "int main()"


class hashMapTester {

  public:


  hashMapTester() {

  }

  unordered_map<int, int> collectMap(vector<int>& arr) {

    unordered_map<int, int> map;

    for (long unsigned int i = 0; i < arr.size(); i++) {

        if (map.find(arr[i]) != map.end()) {

          auto freq = map.find(arr[i])->second;

          freq++;

          map.insert(pair<int, int> (arr[i], freq));

        } else {

          map.insert(pair<int, int>(arr[i], 1));

        }


      
    }

    return map;

  }

  void printMap(unordered_map<int, int> map, vector<int>& arr) {

    for (const auto& iter : map) {

      cout << iter.second << endl;

    }

  }


};

int main() {
  
  vector<int> arr = {1, 2, 2, 3 , 4 , 4, 4};

  hashMapTester hM;

  unordered_map<int, int> map = hM.collectMap(arr);

  hM.printMap(map, arr);
  
  return 0;
}

Why is the frequency portion of the map always outputting 1 when it is not supposed to ? I am stuck on this and I really need to understand why. When I use this algorithm on LeetCode or on another compiler, it works, but not on CoderPad. Can anyone please help me out ? What do I need to do to make it work on CoderPad ?

Makyen
  • 31,849
  • 12
  • 86
  • 121
Saturnsbelt
  • 35
  • 5
  • 3
    `insert` doesn't insert anything if the key already exists. So the only time something gets inserted into the map is when the initial value of 1 gets inserted. Then the key exists, and your valiant attempts to insert 2, 3, and so on, always fails. 1 remains in the map. Furthermore, none of the shown convoluted code is even necessary in the first place. A simple `map[arr[i]]++;`, will replace all the twisted logic in the for-loop, due to how maps work. And it will be several orders of magnitude more efficient then laboriously checking if the key exists, etc... – Sam Varshavchik Nov 04 '22 at 14:14
  • Hello, thank you , that worked. I just don't know why my original solution works in other compilers and in Leetcode. So weird.. – Saturnsbelt Nov 04 '22 at 14:16
  • 1
    I'd be curious to know if the interviewer really didn't immediately see the error, or if the interviewer was just letting you debug your code, and observing your debugging skills... P.S. The original solution should not work in "Leetcode" or anywhere else. If it does, Leetcode's compiler is broken. Actually, Leetcode in its entirety is broken, and you will never learn anything valuable from their useless coding puzzles. – Sam Varshavchik Nov 04 '22 at 14:16
  • @SamVarshavchik, Leetcode is not completely useless. I certainly agree that Leetcode "expert" => good programmer is false (and good programmer => Leetcode expert is false). – MarkB Nov 04 '22 at 14:23
  • 1
    In addition to what @SamVarshavchik mentioned, you've made things overly complicated. You also pass things by value when it should be by `const&` and you have non-`static` member functions that doesn't use any member variables. In fact, the whole class is pointless. It should have been a namespace instead. The `using namespace std;` part is also questionable. You also pass `arr` to `printMap` but don't use it. Example fixes: https://godbolt.org/z/v1qfYdKz5 – Ted Lyngmo Nov 04 '22 at 14:24
  • @NeilButterworth Unfortunately, a lot of these job interviews are rough and you HAVE TO use Leetcode and Hackerrank to practice and to pass the first rounds of these interviews. I don't like it and I personally think coding interviews are completely broken, but it is what it is...(unfortunately) – Saturnsbelt Nov 04 '22 at 14:34
  • @TedLyngmo Thank you for sharing your solution. What I don't understand about C++ and expert programmers is why do you all use std::vector... or use std::unordered_map all the time ? Why don't you all ever just use "using namespace std" and never do the std:: thing ever again ? – Saturnsbelt Nov 04 '22 at 14:38
  • 1
    @Saturnsbelt Good reading: [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Ted Lyngmo Nov 04 '22 at 14:39
  • unordered_map and vector have different semantics, performance and uses. and i can assure you that expert c++ programmers don't do "using namespace std" except maybe in trivial code such as answers here. – Neil Butterworth Nov 04 '22 at 14:43
  • @NeilButterworth I made a typo originally and I meant to ask "why do expert programmers not use using namespace std". My bad. I have done some reading and I understand why now. – Saturnsbelt Nov 04 '22 at 15:20

2 Answers2

1

Per https://en.cppreference.com/w/cpp/container/unordered_map/insert, the insert method "inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key."

The call to insert in the following section won't actually change the contents of the unordered_map.

if (map.find(arr[i]) != map.end()) {
    auto freq = map.find(arr[i])->second;
    freq++;
    map.insert(pair<int, int> (arr[i], freq)); // <<-- here
}

Option 1: Make freq a reference

if (map.find(arr[i]) != map.end()) {
    auto& freq = map.find(arr[i])->second;
    freq++;
}

Option 2: Simplify the algorithm,

unordered_map<int, int> collectMap(const vector<int>& arr) {
     unordered_map<int, int> map;
     for (int val : arr) {
         ++map[val];
     }
     return map;
}
MarkB
  • 672
  • 2
  • 9
  • Thank you ! I did the first solution and it worked. Pass by reference ! I'm an idiot, thanks. I really prefer Java for coding interviews :( – Saturnsbelt Nov 04 '22 at 14:29
  • 1
    @Saturnsbelt The first option shouldn't get you passed the first interview i.m.o. If `find` is used, the returned iterator should be saved and used instead of making _two_ lookups for the same thing. The idiomatic approach for frequency counting is of course the second option - but in general: When using `find` and you feel the urge to `find` again - use the iterator returned by the first `find`. – Ted Lyngmo Nov 04 '22 at 14:37
  • @TedLyngmo, I completely agree if the position is not entry level. I would not fail a student for not knowing the performance impact of that code. Universities do not (and aren't supposed to) teach professional C++. I included option 1 for a minimal change to the OP's code. – MarkB Nov 04 '22 at 20:08
0

To quote cppreference:

Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.

You should probably use operator[] instead.

Nelfeal
  • 12,593
  • 1
  • 20
  • 39