isPalindrome(int n) – Leetcode question 9

So I was doing a few leetcode questions today. Honestly, I just found this one and it seemed interesting because it was easy, and it had multiple solutions to the problem. You could take multiple jabs at it from different angles. For example, you could simply do math operations on it and get the modulo of 10 of the number which would give you the last digit, or you could do string manipulation.

You could also create a stack and a queue of each value and do the modulo of 10 for each number and then compare the stack and queue values because of the FIFO/LIFO rules of these data structures. However, this is not only inefficient in time complexity, but also in space because we are creating two unnecessary data structures.

We could also just convert the number to a string and then compare each value from the ends, for example:

bool isPalindrome(int x) {
        string s = to_string(x);
        int len = s.size() - 1;
        int n = 0;
        while(n < len)
            if (s[n] != s[len])
                return false;
        return true;

However, this solution is not very good either because we are converting the integer to a string, which I believe is an O(N) time complexity, because each character has to be individually converted to a number.

So I found another solution which basically takes advantage of how math works.

bool isPalindrome(int n)
    int original = n;
    int reversed = 0;
    while(n > 0)
        reversed = reversed * 10 + n % 10;
        n /= 10;
    if (original == reversed)
        return true;
        return false;

This may not even be the most efficient solution as I may be ignorant on other mathematical concepts and how they work. However, given this, the math is simple. We know that n % 10 will give us the last digit in the number. So for example: 123 % 10 would give us 3.

Because we know this, we can simply loop through n, and say, while n is not 0, the reversed version of the number will be itself times 10 + the remainder (n % 10).

So given reversed = 0 for the first iteration of our loop, the math would be:
0 = 0 * 10 + 3

Obviously, this is assuming that n is 123. So after the first iteration, reversed will equate to 3. On the second iteration, after we divide x by 10, it would be:

3 = 3 * 10 + 2, which is 32, so reversed is now 32, which is obviously the first two digits in reverse of 123, it’s 32. If we do it again we will get the one. Let’s do it.

If we do n % 10 again, we get a remainder of 1, or our last digit. So then we take 32 = 32 * 10 + 1 which is 321. And there we go, we have the numbers in reverse. The last thing to do is to essentially check if the original value of n, is equal to this newly reversed value of n.

Return true if they are equal, return false otherwise.

Anyways, hopefully this helps other people who are trying to practice algorithms!

What is the build order of a C program? (Interview Questions)

Today I had an interview and I incorrectly answered a question. It was silly because I remember reading about this a long time ago honestly in a C++ book written by IBM from the 1990s. It’s one of the first books I read growing up when learning to code. My mother bought it for me from Salvation Army. It had a yellowish-orange and red cover. Anyways, just as a personal note and so that I don’t forget this again.

The order is as follows:

  • Preprocessing – this is essentially the stage where the preprocessor parses the source files and looks for macros. This one is the one I’m most familiar with due to my heavy usage of Unreal Engine. Unreal Engine uses a lot of macros, and conditional compilation instructions.

Just as an example, in unreal engine there’s tons of conditional compilation instructions like this:



There’s more information about the visual studio C++ preprocessor here:

The preprocessor is really amazing honestly. There’s some token-pasting operations using the ## tag in a macro. I found this example on here:

#define paster( n ) printf_s( "token" #n " = %d", token##n )
int token10 = 15;

So essentially, if we call paster(10). It will essentially put token10 as the last parameter and it will fill in 15 where #n is at. So this will cause the console to print out “token10 = 15” There are other examples of preprocessor usage but those can be looked at on the reference I linked above.

  • Compilation – This is basically where the compiler goes over the code again (after it has been filled in with proper pre-processor changes) and then it begins to generate assembly source code.
  • Assembly – Takes assembly source code and builds an object file.
  • Linking – Takes libraries and object files to create the executable file.