Author |
Topic: Recent interview questions (Read 2417 times) |
|
Obeye
Guest
|
I got asked these questions at the interview for a big .com
I goofed up (partially) on all of them. I didn't get the job. 
I was asked to write all these programs in C or C++.
1.Write a function to check if a string is a palindrome. Exclude any spaces or puncutation in the string. Analyze the runtime.
2. Write a function to convert a decimal number to a string of characters. Analyze the runtime.
3. Write a function to convert a number to its equivalent roman numeral value. You have to convert only numbers < 1000. Analyze the runtime. (This was really hard, and I fluffed my way through it.)
4. Assume that you are the owner of a network television channel that's webcasting all of its shows. Your schedule may look as follows:
8AM-9AM Friends (300 kbps)
9AM-10AM Nature (900 kbps)
8AM-11:12AM The Return of the King (2 mbps)
And so on...
How would you store this data? Tell me [the interviewer] an algorithm to determine the maximum bandwidth at any point in time. Analyze the runtime. (The interviewer really paid attention to details, so my "algorithm" fell through on deeper analysis; I again ended up fluffing)
 I really failed when it came to runtime analysis.
It'll at least be enlightening to see the solutions proposed by the many technically accomplished people on this forum.  Might help me next time if I get asked similar questions. 
|
|
 IP Logged |
|
|
|
Obeye
Guest
|
 |
Re: Recent interview questions
« Reply #1 on: Mar 18th, 2004, 7:37am » |
 Quote  Modify
 Remove
|
One more thing: I mentioned "analyze the runtime", but I meant both space analysis and time analysis.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Recent interview questions
« Reply #2 on: Mar 18th, 2004, 8:00am » |
Quote Modify
|
I don't think I would do well on these kinds of questions.. I'd start with asking more clarification on most of them..
Like #1, must we look at case, must we also ignore tabs and newline etc, what about numbers, accented characters, what about special characters like null or escape, do we know the length (must be the case if null is allowed in the string) etc.
If I know the length and only have to look at alphanumeric characters (ignoring case) it'd end up something like
f(char *str, int strlength)
{
i=0; j = strlength -1;
while (i < j)
{
if (!is_alpha(str[i]))
i++;
else if (!is_alpha[j])
j--;
else if (tolower(str[i]) == tolower(str[j]))
i++,j--;
else break;
}
return i >= j;
}
|
| « Last Edit: Mar 18th, 2004, 8:02am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Recent interview questions
« Reply #3 on: Mar 18th, 2004, 8:07am » |
Quote Modify
|
hmm..
#2 doesn't seem to specify what characters the decimal number should be converted to..
so this should work I think 
string f(int i)
{
return string(&i, 0, sizeof(i));
}
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Recent interview questions
« Reply #4 on: Mar 18th, 2004, 12:00pm » |
Quote Modify
|
IMHO, in #2 it was asked more than towr's solution, i.e. it is needed to implement the string() function itself. Here's a possible solution (assuming n positive):
Code:
char* u2str(unsigned n)
{
static char* dec_digits = "0123456789";
static char buf[11]; // 2^32 has 10 digits
int cnt = 10;
buf[10] = 0; // string terminator
do
{
buf[ --cnt ] = dec_digits[ n % 10 ];
n =/ 10;
} while (n);
return buf + cnt;
}
|
|
Because "modulo" operation is linear in number of bits of n, the run time of this code is log(n)2.
#3 may be implemented in similar manner:
Code:
char* u2roman(unsigned n)
{
static char* roman_digits[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
static char* roman_tenths[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
static char* roman_hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
static char buf[13]; // Max length is 12 symbols
int cnt;
if (n >= 1000) return 0;
cnt = sprintf(buf, "%s", roman_hundreds[ n / 100 ]);
cnt += sprintf(buf + cnt, "%s", roman_tenths[ n / 10 ]);
sprintf(buf + cnt, "%s", roman_digits[ n % 10 ]);
return buf;
}
|
|
For arbitrary n, the run time is again log(n)2, and the space is log(n).
Hope this helps.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Recent interview questions
« Reply #5 on: Mar 18th, 2004, 12:52pm » |
Quote Modify
|
on Mar 18th, 2004, 12:00pm, Barukh wrote:| IMHO, in #2 it was asked more than towr's solution, i.e. it is needed to implement the string() function itself. |
|
I didn't use a string function..
I just initialized a string-object, with the first sizeof(int) characters from adress of the integer
I suppose I might have needed to do a cast to char * first..
How do you get O(log(n)^2) btw? it seems to me it's O(log(n))
% is just one operation to the CPU, independent of the value of the integer..
and you can safe some space by using '0' + n%10, instead of indexing an array
|
| « Last Edit: Mar 18th, 2004, 12:54pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Recent interview questions
« Reply #6 on: Mar 18th, 2004, 11:21pm » |
Quote Modify
|
on Mar 18th, 2004, 12:52pm, towr wrote:I didn't use a string function..
I just initialized a string-object, with the first sizeof(int) characters from adress of the integer
I suppose I might have needed to do a cast to char * first.. |
|
Sorry, I misunderstood your intention... 
Quote:| How do you get O(log(n)^2) btw? it seems to me it's O(log(n)) % is just one operation to the CPU, independent of the value of the integer.. |
|
That's correct if n is bounded by the machine word. For an arbitrary n, however, % will take log(n) operations. The C implementation of this needs to be changed, of course.
Quote:| and you can safe some space by using '0' + n%10, instead of indexing an array |
|
Of course, you are right!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Recent interview questions
« Reply #7 on: Mar 19th, 2004, 12:28am » |
Quote Modify
|
on Mar 18th, 2004, 11:21pm, Barukh wrote:| That's correct if n is bounded by the machine word. For an arbitrary n, however, % will take log(n) operations. The C implementation of this needs to be changed, of course. |
|
Seeing as you call the function with an unsigned int, it has to be bounded by a machine word though.
|
| « Last Edit: Mar 19th, 2004, 12:41am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print