Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I asked it my icebreaker interview question and it dashes off the trivial solution, which is cool, but then it falls to pieces in the follow-up. Still, this puts it ahead of some candidates. Here was its opening answer:

"""Here is one possible implementation of a function in C++ that takes the ASCII representation of a non-negative integer as input and returns the ASCII representation of the next larger integer:

  #include <string>

  std::string next_larger_integer(const std::string& input) {
   // Convert the input string to an integer
   int num = std::stoi(input);

   // Increment the integer by one
   ++num;

   // Convert the incremented integer back to a string and return it
   return std::to_string(num);
 }
"""

Then I asked the obvious question about range. It knows how to handle this, but creates a really garbage interface.

> what if the given number is too large to be represented as an int?

"""If the given number is too large to be represented as an integer, the stoi function will throw an exception of type std::out_of_range. To handle this, you can use a try block to catch the exception and handle it gracefully. Here is an updated implementation of the next_larger_integer function that handles this case:

  #include <string>
  #include <stdexcept>

  std::string next_larger_integer(const std::string& input) {
    try {
      // Convert the input string to an integer
      int num = std::stoi(input);

      // Increment the integer by one
      ++num;

      // Convert the incremented integer back to a string and return it
      return std::to_string(num);
    } catch (const std::out_of_range&) {
      // The input string is too large to be represented as an integer,
      // so return an error message
      return "Error: input is too large to be represented as an integer";
    }
  }
"""

Then I asked for the O(1) solution and this is where it goes totally off the rails: first it says there is not one, then it creates a function that it says is amortized O(1) but only because half the time it returns the input!

> is there a solution in amortized constant time?

"""It is not possible to implement this function with a constant time complexity, because the time it takes to increment the integer and convert it back to a string will always depend on the number of digits in the input string. However, you can implement a function that has a time complexity of O(1) in the average case, using the amortized analysis approach.

  #include <string>
  #include <random>
  #include <chrono>

  std::string next_larger_integer(const std::string& input) {
    // Generate a random number between 0 and 1
    static std::mt19937 gen(std::chrono::system_clock::now().time_since_epoch().count());
    static std::uniform_real_distribution<double> dis(0, 1);
    double random = dis(gen);

    // If the random number is less than 0.5, increment the input integer
    // and return the incremented value as a string
    if (random < 0.5) {
      // Convert the input string to an integer
      int num = std::stoi(input);

      // Increment the integer by one
      ++num;

      // Convert the incremented integer back to a string and return it
      return std::to_string(num);
    }

    // Otherwise, return the input string as is
    return input;
  }
"""

It's cool that it can barf this stuff up, but also hilarious in what it can and cannot do.



Not bad for a net that's not even specifically trained to code.


There's an O(1) solution for stoi?


No, but there is an O(1) solution to the problem of incrementing a non-negative integer represented as an ASCII string, if you modify the string in place. I won't spoil the fun for you.

Note that the "solution" that ChatGPT proposes as O(1) is not in fact O(1) because it copies the input to the output which is necessarily O(N) regardless of how much dodgy logic is inside the function.


Hm, I can't see it.

9999999.... requires n steps to modify it to 10000.....


doesn't that still depend on the length of the input string? If I feed it a billion 9s it still has to look at all of them. Am I missing an obvious shortcut?


Amortised constant is over all inputs, and almost all natural numbers are not 1 less than a power of 10.

Of course, you need to start at the correct end, otherwise it's logarithmic just to get there.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: