Thomson Reuters Interview Question Applications Developers
Country: United States
Interview Type: In-Person
Hey thanks. Your sol works fine till n=1000000 but if i put it 10000000 the program exits. Not sure y.
Memory issues really...
Just on the back of the napkin, you've got 1 billion integers, allow one byte per character to be output, just the ones column alone eats a gigabyte of memory. Then add n-1 commas, a little under 2 gigabytes total. That leaves you roughly 100 megabytes to put all the other characters in, due to the 2 gigabyte length limitation of System.String.
You can't cheat the system into trying to output n=1000000000, I dropped the output into a text file, and it comes out to 9.2 GB.
The only way to output the answer once the numbers get up there is to have access to the output stream. No ifs or buts about it.
How about this?
string convert(int n)
{
stringstream ss (stringstream::in | stringstream::out);
int i = 1;
while(i < n)
{
ss << i++ << ",";
}
ss << n;
return ss.str();
}
Not sure you paid attention to "minimize the creation of string objects" :)
The question is quite simple and the answer isn't too bad bad the arithmetic is almost impossible to get right on paper.
The solution: calculate how many characters will the final string occupy (count the 1, 2, 3... digit numbers + commas)
In a loop write the number directly into the pre-allocated char array (NOT using toCharArray or toString at all).
It takes quite a while to get it perfect but it's very interesting!
Isn't writing number to pre-allocated buffer same as writing number in stringbuf of stringstream? In stringstream case, the buffer resizing is handled automatically, which will not be as bad as creating string for each number.
Also, I think, string size can be computed as:
long count = 0;
int multiplier = 1;
int rem = 0;
int digits = 1;
while (n > 10)
{
rem += (n%10)*multiplier; // this will calculate the remaining highest digit numbers in range [1,n]
count += 9*multiplier*digits; // number of 'digits' digits number is 9*multiplier (1 digit -> 9, 2 digit -> 90, so on)
n = n/10;
multiplier *= 10;
digits++;
}
count += ((n-1)*multiplier + rem)*digits;
count += (n-1); // for commas
@gimli: i used stringbuilder so that i don't need to create string objects everytime in for loop. but the issue was in the return statement. when you will return the string for b= 1000000000. the string would be "1,2,3,4,5,......................,999999999,1000000000" so this very large string is i am not sure possible to return. And as far as i know, the object size could only be at max 2Gb in c#. So got confused how to do this.
package demoJavaProject;
import java.util.Scanner;
public class Demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Long n = sc.nextLong();
String result = convert(n);
System.out.println(result);
}
static String convert(Long n) {
StringBuilder sb = new StringBuilder();
for (Long i = (long)1; i <= n; i++) {
sb.append(i);
if (i != n)
sb.append(",");
}
return sb.toString();
}
}
package demoJavaProject;
import java.util.Scanner;
public class Demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Long n = sc.nextLong();
String result = convert(n);
System.out.println(result);
}
static String convert(Long n) {
StringBuilder sb = new StringBuilder();
for (Long i = (long)1; i <= n; i++) {
sb.append(i);
if (i != n)
sb.append(",");
}
return sb.toString();
}
}
package demoJavaProject;
import java.util.Scanner;
public class Demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Long n = sc.nextLong();
String result = convert(n);
System.out.println(result);
}
static String convert(Long n) {
StringBuilder sb = new StringBuilder();
for (Long i = (long)1; i <= n; i++) {
sb.append(i);
if (i != n)
sb.append(",");
}
return sb.toString();
}
}
As c# is tagged, here is a C# easy solution:
- Oni April 01, 2012string convert(int n) { return string.Join(",", Enumerable.Range(1, n)); }