Need help being assessed on basic programming questions

[jbunniii]

Admittedly, a lot of compilers are stuck in the 1989 standard, or before. They never moved up to C99, let alone to the newest version of the standard (2011). Case in point: The GNU compiler suite developers are doing their best to stay current or even ahead of the game with respect to C++. That is not the case with C.

I have been assuming that the OP is writing in C++ due to the use of "string", even if he is mostly speaking in a low-level dialect. If my assumption is incorrect then I retract my earlier suggestions to use references, iterators, etc. Jamin: which is it, C or C++?

P.S. I use Visual C++ at work. Its C compiler STILL doesn't support C99.

 

[rcgldr]

Normally? For which millennium are you normally writing code? For loops with declarations have been part of the C standard since 1999. Admittedly, a lot of compilers are stuck in the 1989 standard, or before.

Just wanted to be sure on this. I updated my prevoius post. Some compilers still use the C89 standard (visual studio 2005 for example). I don't know what the work interview will be expecting. In any case, it's not going to cause problems if all function variable declarations are put at the start of a program.

 

[jbunniii]

Just wanted to be sure on this. I updated my prevoius post. Some compilers still use the C89 standard (visual studio 2005 for example). I don't know what the work interview will be expecting. In any case, it's not going to cause problems if all function variable declarations are put at the start of a program.

I probably wouldn't penalize someone for doing that in an interview, but I would probably draw the line at pre-C89 function definitions. Remember these dark days?

int countOneBits(num)
unsigned long num;
{ 
    ...
}

(In fact, even "unsigned long" may not have been universally supported at the time...)

 

[Jamin2112]

You are calling str.length() *three* times every pass of the loop. Certainly you can do better than that!

I've noticed you aren't using pointer arithmetic very much. The C++ purists will say don't. Your interviewers will most likely say DO. They will want to know whether you understand why the following is the canonical form of a C-style string copy:

char * strcpy (char * target, char * source) {
   char* ret = target;
   while (*target++ = *source++);
   return ret;
}

Yea, I know, I should've just done unsigned in len = str.length() in the beginning of the function and then used that variable len throughout. I'll make a final draft of everything by the end of today.

In the code you posted, the function is taking two pointers to characters, then continuing to increment both pointers via pointer arithmetic and with each increment setting the dereferenced value at target equal to the dereferenced value at source. That while loop terminates as soon as source points to no value at all.

 

[Jamin2112]

Jamin: which is it, C or C++?

Oh, my 4-hr interview is Java, but I'm trying to rehash some C++ knowledge just in case they ask.

 

[Jamin2112]

6. (C++, easier) Let's write a simple complex number class, with various useful operators.

Ok. This is me going through it very fast. We'll see which simple mistakes I make.

#include <iostream>
#include <math.h>

class Imaginary { 
     public: 
     Imaginary(double, double);
     ~Imaginary();
     Imaginary operator + (Imaginary);
     Imaginary operator * (Imaginary);
     Imaginary operator ' (); // complex conjugate
     void print(); 
     double a, b;
     double abs(); 
} 


Imaginary::Imaginary(double newa, double newb) { 
    a = newb; 
    b = newb;
}

Imaginary::~Imaginary() { 
    delete *a, *b;
}

Imaginary Imaginary::operator + (Imaginary nextguy) { 
     Imaginary sumguy(a + nextguy.a, b + nextguy.b);
     return sumguy;
}

Imaginary Imaginary::operator + (Imaginary nextguy) { 
     Imaginary productguy(a * nextguy.a - b * nextguy.b , a * nextguy.b + b * nextguy.a);
     return productguy;
}

// complex conjugate
Imaginary::operator ' () { 
    b = -b; 
}

double abs() { 
    return sqrt(a*a + b*b);
}

void print() { 
    cout << a << " + " << b << " * i" << endl;
}

 

[jbunniii]

Ok. This is me going through it very fast. We'll see which simple mistakes I make.

#include <iostream>
#include <math.h>

class Imaginary { 
     public: 
     Imaginary(double, double);
     ~Imaginary();
     Imaginary operator + (Imaginary);
     Imaginary operator * (Imaginary);
     Imaginary operator ' (); // complex conjugate
     void print(); 
     double a, b;
     double abs(); 
}

First, a mathematical remark: "imaginary" means a number of the form $0+bi$, whereas "complex" has the more general form $a+bi$.

This class is a reasonable start and I probably wouldn't demand more operations in an interview, except I might ask you to implement a copy constructor and an assignment operator, and ask you under what circumstances each one would be called.

Obviously in a real implementation you would override additional operations such as /, -, +=, ==, etc., and also provide versions that allow you to do, for example, complex + real.

You should also have a default constructor, and you should also know why you should have a default constructor. (Hint: what happens if you want an array of complex numbers? Do you need a default constructor for that? Will the compiler create one if you don't provide one?)

a and b shouldn't be public. Better to provide real() and imag() to give access to these.

Imaginary::~Imaginary() { 
    delete *a, *b;
}

No, this is wrong. a and b are plain old data (POD). You didn't allocate them using new, so you shouldn't delete them. Additionally, a and b are not pointers, so *a and *b are syntax errors. Bottom line: you don't need a destructor for this class.

Imaginary Imaginary::operator + (Imaginary nextguy) { 
     Imaginary sumguy(a + nextguy.a, b + nextguy.b);
     return sumguy;
}

The right prototype for this is

Imaginary Imaginary::operator+(const Imaginary& nextguy)

(No need to make a copy of nextguy.)

// complex conjugate
Imaginary::operator ' () { 
    b = -b; 
}

There's no ' operator in C++, so you can't override it. You can implement this as conj() ,for example.

double abs() { 
    return sqrt(a*a + b*b);
}

This is OK. Its usage would be mag = z.abs(); You may also want to provide a static version so you can use the more natural idiom mag = abs(z); (But keep it within the class to avoid namespace pollution.)

 

[Jamin2112]

The right prototype for this is

Imaginary Imaginary::operator+(const Imaginary& nextguy)

(No need to make a copy of nextguy.)

Ok, I need to study operator overloading.

 

[Jamin2112]

8. Without using any standard library functions, how might you go about calculating pi to arbitrary precision?

Would this really be asked in an interview? lol. I'd have to remember some sequences that converge to pi.

 

[jbunniii]

Would this really be asked in an interview? lol. I'd have to remember some sequences that converge to pi.

Well, you can use a series expansion if you know any. Probably the easiest one to remember is
$$\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots$$
It doesn't converge very quickly, but it's good enough for an interview. If someone doesn't remember the expansion I usually just write it on the whiteboard and say, OK, use that.

An even better question is to compute $e$ (the natural logarithm base). This has three advantages over the $\pi$ question: (1) more people probably remember its Taylor series
$$\sum_{n=0}^{\infty} \frac{1}{n!}$$
(2) the Taylor series converges pretty rapidly, and (3) the interviewee has to do something intelligent to deal with the factorial.

 

[rcgldr]

Well, you can use a series expansion if you know any. Probably the easiest one to remember is
$$\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots$$

That's the series for arctan(1), I'll list a few of these here:

pi/4 = arctan(1)

pi/4 = arctan(1/2) + arctan(1/3)

pi/4 = 4 * arctan(1/5) - arctan(1/239)

pi/4 = 6 * arctan(1/8) + 2* arctan(1/57) + arctan(1/239)

{arctan}(x) = \frac{x}{1} - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} + \cdots

 

[Jamin2112]

I'm going to start my final answers to a few questions. Make sure these are right so far.


1. Neither is correct because str is of scope local to function and as such is destroyed after function is finished doing its business. The way to do this correctly is to new the string so it survives the function exit:

(From the C++ standard string class http://www.cplusplus.com/reference/string/string/)

cost string* GetString(void) { 
    string* str = new string("Hello");
    return str;
}

3. FINAL ANSWER for reversing a string:

void ReverseString(string &str) { 
     unsigned int length = str.length();
     for (unsigned int i = 0; i < length / 2; i++) { 
        char temp = str[i];
        str[i] = str[length - i - 1]; 
        str[length - i - 1] = temp;
     } 
}

 

[Jamin2112]

An even better question is to compute $e$ (the natural logarithm base). This has three advantages over the $\pi$ question: (1) more people probably remember its Taylor series
$$\sum_{n=0}^{\infty} \frac{1}{n!}$$
(2) the Taylor series converges pretty rapidly, and (3) the interviewee has to do something intelligent to deal with the factorial.

Obviously you create a factorial function that uses a recursive algorithm:

unsigned int factorial(unsigned int n) { 
    int product;
    if (n <= 1) return 1;
    product = n * factorial(n - 1);
    return product;
}

And then an extremely elegant but inefficient way of calculating e would be:

unsigned long double sum = 0; 
unsigned long int n = 0; 
while (sum + 1/factorial(n) > sum) {  
    // while condition tests whether 1/factorial(n) is bigger than machine epsilon
    sum += 1/factorial(n); 
    n++;
}

But the efficient way of doing the entire procedure is just:

unsigned long double sum = 1;
unsigned long int n = 1;
unsigned long double product = 1;
while (sum + 1/(product * n) > sum) { 
    sum += 1/(product * n); 
    n++; 
    product *= n;
}
const unsigned long double EulersNumber = sum;

 

[rcgldr]

1. Neither is correct because str is of scope local to function and as such is destroyed after function is finished doing its business.

Note that string literals such as "Hello" are supposed to be static. In the first example, although str is destroyed, the returned pointer to the static literal string "Hello" should still be valid.

 

[jbunniii]

But the efficient way of doing the entire procedure is just:

unsigned long double sum = 1;
unsigned long int n = 1;
unsigned long double product = 1;
while (sum + 1/(product * n) > sum) { 
    sum += 1/(product * n); 
    n++; 
    product *= n;
}
const unsigned long double EulersNumber = sum;

I don't think you want both (product * n) and product *= n in the loop. Think about the second iteration of the loop. At the start of the loop, product = 2 and n = 2, so you just want 1/product, not 1/(product * n).

The rest is OK, except there is no "unsigned long double" type, just "long double". And you might get into trouble with the exit condition for the loop. You will stay in the loop until the sum doesn't change anymore, but that might be longer than you want to wait. Maybe better to compare 1/product to some epsilon.

 

[jbunniii]

Note that string literals such as "Hello" are supposed to be static. In the first example, although str is destroyed, the returned pointer to the static literal string "Hello" should still be valid.

This is correct. The initializer

const char *str = "Hello";

will create a local pointer called str, and that pointer will point to an address somewhere in static memory where "Hello" is stored by the compiler-generated startup code, which is executed before main() is called. There is no problem returning str in this case. The variable str itself disappears when the function returns, but the function returns a copy of it, and the address it contained is still valid, and "Hello" still resides at that address.

So the original GetString1() function is the correct one.

Neither is correct because str is of scope local to function and as such is destroyed after function is finished doing its business. The way to do this correctly is to new the string so it survives the function exit

const string* GetString(void) { 
    string* str = new string("Hello");
    return str;
}

This solution will work, but it wasn't one of the options. One problem is that "string" doesn't exist in C, so this only works in C++. The other problem is that this function allocates new memory, and now it becomes someone else's responsibility to delete that memory when the string is no longer needed. This is usually a really bad practice, because it invites memory leaks. If you must create and return a new string, then do it this way:

string GetString() {
    string str("Hello");
    return str;
}

This will return a copy of the local variable str. The local variable disappears at the end of the function. The copy (return value) will be valid until it goes out of scope, at which point its destructor will automatically free any memory associated with it.