CODEWITHSUNDEEP
stringc#-4.0
Naphstor
Naphstor

Reputation: 2496

return a string containing billion characters

Hi i have a function that takes an integer number n and returns a string that contains the numbers from 1 to n separated by ','. Now this number integer n could be any number as large as 1 billion. What could be the best solution for this. And how do i manage the memory related issues like if the RAM is just 2 Gb so what would happen if i return this big string in C#. The function signature is:

string convtostr (int n)
{}

so the input for e.g. could be n = 5, then output would be a string like this "1,2,3,4,5"

Upvotes: 0

Views: 1233

Answers (4)

kasavbere
kasavbere

Reputation: 6003

Let's look at the design limit:

n = 1 billion:

when n is one billion, then the commas "," alone eat your available space since char === 2 bytes; so that 2 bytes * 1 billion = 2 GB - 2 bytes (you actually have 2 billion - 1 commas). Hence, from this basic observation the idea must be to compress the result to fit in 2GB. String is an object and the size is restricted to 2GB.

Therefore the question is how do you encode messages between objects? I.e one object will call the function with n and expects a message from the called object. Notice that you were not asked to print the result, but rather to return a string. If the function signature you present is actually what the interviewer wrote on the board (as opposed to it being your interpretation of the question) then the answer from suddnly_me won't do, otherwise it is your answer.

Assuming that the signature is what the interviewer wrote, so how do you send the compressed message between the two objects? As facetious as it may sound, I would return n as a string.

 string convtostr (int n)
 {
  return n+"";
 }

Then depending on what the returned value will be used for, I would write decoders/parsers to decode the message. For example, if the call needs to write the string to a file, then a writer method/function would convert the string back to an int and the iterate from 1 to n while writing to the file.

I have gone on long enough. You get the idea.

Upvotes: 0

Seph
Seph

Reputation: 8703

If your method footprint must exactly match that which you show, then it cannot be done. Because you cannot inherit String and make a new better type that will work for >2GB

If your assumption about the maximum input value of n is incorrect then you can provide a working solution to match the footprint. Such as if the max value of n was 10000 or something very small.

However I think the IEnumerable<char> approach as suggested by @MikeSamuel is the only answer that would present a working solution that returns close to the stated requirements.

As you have tagged this c# 4.0 Most likely they were looking for a solution that used yield syntax such as:

static IEnumerable convtostr(int n)
{
    for (int i = 1; i < n; i++)
        yield return string.Format("{0}, ", i.ToString());
    yield return n.ToString();
}

you can then explain that you use it like the following

int input = 1000000000; // 1 billion.

foreach (var value in convtostr(input))
{
    Console.Write(value );
}

And that is likely what they were wanting you to answer with. As this will work with very little active RAM by not actually storing the whole final string in memory.

Edit: another answer similar to that suggested by @suddnely_me is to pass in an action for each number instead, such as:

static void convtostr(int n, Action<int> action)
{
    for (int i = 1; i <= n; i++)
        action(i);
}

This is then called using:

int input = 1000000000; // 1 billion.
convtostr(input, n =>
    {
        if (n < input) { Console.Write("{0}, ", n); }
        else { Console.Write(n); }
    });

Which will actually perform almost the same as using the yield syntax.

Upvotes: 0

Mark Byers
Mark Byers

Reputation: 838336

You can't create such a large string in .NET. 2GB is the maximum size of an object, regardless of how much memory you have.

Instead of returning a string, you could provide an object which allows you to iterate over the characters in the result but only calculates them on demand.

Upvotes: 2

iehrlich
iehrlich

Reputation: 3592

I guess the best solution for you is not to use this string at all :) You may wrap this string in a class, containing only the number n:

class LargeStringWithNumbers
{
  int upper_bound;
  public void Print()
  {
    for (int j = 0; j < upper_bound; j++ )
    {
      System.Console.Write("{0};", j);
    }
    System.Console.Write("\n");
  }
}

It will behave exactly like if you contained the string all the time, except you don't.

Upvotes: 2

Related Questions