0

So I have been working with leetcode for the past few months preparing for job interviews. An interesting phenomenon I came across was when I used a helper function after the main function it happened to be faster.

This took 4 ms according to leetcode

class Solution {
public:


int countSubstrings(string s) {
    int n = s.length();
    int ans = 0;
    for(int i=0;i<n;i++){
        int l1 = expandCenter(i,i,s);
        int l2 = expandCenter(i,i+1,s);
        ans+=(((l1+1)/2)+(l2/2));
    }
    return ans;
}
      int expandCenter(int l,int r,string s){
    int n = s.length();
    while(l>=0 && r<n){
        if(s[l]==s[r])
            l--,r++;
        else
            break;
    }
    return r-l-1;
}

};

This took 8 ms according to leetcode

    class Solution {
public:
     int expandCenter(int l,int r,string s){
        int n = s.length();
        while(l>=0 && r<n){
            if(s[l]==s[r])
                l--,r++;
            else
                break;
        }
        return r-l-1;
    }
    int countSubstrings(string s) {
        int n = s.length();
        int ans = 0;
        for(int i=0;i<n;i++){
            int l1 = expandCenter(i,i,s);
            int l2 = expandCenter(i,i+1,s);
            ans+=(((l1+1)/2)+(l2/2));
        }
        return ans;
    }
};

Why does this happen?

Yunnosch
  • 26,130
  • 9
  • 42
  • 54
Vigneswaran S
  • 21
  • 3
  • Did you try repeating the experiment a few times? – lukeg Jul 03 '21 at 09:44
  • 2
    OT: `if(s[l]==s[r]) l--,r++;` is nasty, please dont do this, write `if(s[l]==s[r]) { l--;r++; }` instead – 463035818_is_not_an_ai Jul 03 '21 at 09:44
  • Yes i did try this multiple times. – Vigneswaran S Jul 03 '21 at 09:47
  • why is if(s[l]==s[r]) l--,r++; considered nasty. I am relatively new and i thought using the comma didn't have any major effect to the efficiency or logic of the program – Vigneswaran S Jul 03 '21 at 09:48
  • 3
    1) Do you know what leetcode is measuring and how the measurement is performed? Or are you trying to reason about something that you (and not only you) don't understand? 2) If you write `int n = s.length();` in a coding interview, you are likely to be rejected. If that's what leetcode is teaching, avoid it by all means. – Evg Jul 03 '21 at 10:02
  • 2
    see here https://stackoverflow.com/questions/68199237/whats-the-difference-between-start-i-end-j-and-start-i-end-j. It is nasty because it makes use of the comma operator for no good reason. It is surprising code, its too easy to turn it into wrong code by changing a single character. Now I am curious, did you see this `if(s[l]==s[r]) l--,r++;` pattern somewhere? Strange coincidence to see it twice, because it really is uncommon – 463035818_is_not_an_ai Jul 03 '21 at 10:11
  • Have you tried timing when passing those strings as `const &`? – Bob__ Jul 03 '21 at 10:25
  • What is the data you are using to test this? Since it's taking 4ms at least, I would think you must be using sizable. Is that difference consistent i.e. how many iterations you did? Did you try to measure it on your computer? –  Jul 03 '21 at 10:54
  • @VigneswaranS -- "it's nasty" sometimes means "folks who haven't seen it before can misunderstand it, and there are more common ways of doing it". In other words, it's about style, not substance. I've worked with code bases where this was not unusual (Dinkumware C++ library) without problems. But we weren't beginners and didn't feel a need to cater to beginners. – Pete Becker Jul 03 '21 at 12:39
  • @Evg What is wrong about `int n = s.length()`? – lukeg Jul 03 '21 at 20:30
  • @lukeg Type mismatch: different signed-ness and different size on 64-bit platforms. You'll get compiler warning and potential overflow problems. – Evg Jul 04 '21 at 06:28
  • 1
    The two posted pieces are exactly the same. – n. m. could be an AI Jul 04 '21 at 08:35
  • @n.1.8e9-where's-my-sharem. Apart from one irrelevan whitespace. the two codes are identical since the most recent edit by not-the-OP. I hence undid it. – Yunnosch Jul 04 '21 at 09:33
  • @김선달 It seems your edit caused harm by making the two shown code practically identical. I undid it. Please review and let me know whether I missed something of a reason for your edit. – Yunnosch Jul 04 '21 at 09:36
  • @Yunnosch Oops, sorry everybody. Tried to reorder functions but accidentally pasted them. – 김선달 Jul 04 '21 at 12:51
  • And nobody noticed when aprroving the edit..... Sigh. Could make a great audit.... – Yunnosch Jul 04 '21 at 12:52

1 Answers1

0

In order to make a good benchmark, you should run the code multiple times on a computer that you know what priority you get on it.

I have transformed your code so you can run it on your own machine: here

Compiler Explorer lets you see the compiled code, and is useful for understanding changes within a code. You can check your own code compilation using it (for example, like that).

I must say that even there (on compiler explorer), the results varied (up to 50-80% difference from one run to another), sometimes solution1 was better, and sometimes solution2 was better. Sometimes they got the same results.

Anyhow, the lesson you should learn here is that leetcode servers are not good for bench-marking a solution.

Kerek
  • 1,106
  • 1
  • 8
  • 18