Thomson Reuters Interview Question Applications Developers


Country: United States
Interview Type: In-Person


Comment hidden because of low score. Click to expand.
1
of 1 vote

As c# is tagged, here is a C# easy solution:

string convert(int n)
{
    return string.Join(",", Enumerable.Range(1, n));
}

- Oni on April 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey thanks. Your sol works fine till n=1000000 but if i put it 10000000 the program exits. Not sure y.

- naphstor on April 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Christopher.R.Klein on June 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- gimli on March 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- Adam on March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 on March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- naphstor on March 30, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More