Need help being assessed on basic programming questions

[Jamin2112]

Ok, so I'm going in for an interview on Thursday and the technical recruiter told me to just practice basic coding problems until I'm blue in the face. I know there are some experts here. I was wondering whether you could give me some questions and then assess my answers as you would if you were interviewing me.

For example, finish the following function that returns the mode (most frequent element) of an integer array.

int mode(unsigned int size, int* arr) {
// ...
}


Questions like that.

 

[jbunniii]

It looks like you are being tested in C, or maybe C++. Here are a few basic questions I have asked or been asked, from both sides of the interview.

1. Pointer to char vs. array of char

Which is correct, and why?

const char *GetString1(void)
{
    char *str = "Hello";
    return str;
}

vs.

const char *GetString2(void)
{
    char str[] = "Hello";
    return str;
}

2. The keyword "static" shows up in a lot of different contexts in C and C++. Give some examples of this, and explain what it means in each case.

3. Reversing things: e.g., write a function to reverse a string, or the digits (decimal or binary) of a given number. Write a function to reverse a linked list. Write a function to reverse a sentence: e.g., "write a function to reverse a sentence" becomes "sentence a reverse to function a write".

4. Write a function to sort an array of numbers in place. (Or an array of strings.)

5. Write a function to count how many "1" bits appear in the binary representation of the input number.

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

7. (C++, harder) Let's write a simple matrix class, with various useful operators. Need to manage memory because we want to support arbitrary sizes of matrices. Alternate: let's write a "big integer" class which can handle integers of arbitrary size.

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

9. Write a function to find the first N prime numbers, where N is specified by the user.

 

[Jamin2112]

It looks like you are being tested in C, or maybe C++. Here are a few basic questions I have asked or been asked, from both sides of the interview.

1. Pointer to char vs. array of char

Which is correct, and why?

const char *GetString1(void)
{
    char *str = "Hello";
    return str;
}

vs.

const char *GetString2(void)
{
    char str[] = "Hello";
    return str;
}

Both those are "legal" and they do the exact same thing, which is, they return a pointer to "H". But you'd want to use the second because it adds a null character as a sentinel to denote the end of the string.

 

[Jamin2112]

2. The keyword "static" shows up in a lot of different contexts in C and C++. Give some examples of this, and explain what it means in each case.

I'll have to brush up on this and then answer later.

 

[Jamin2112]

3. Reversing things: e.g., write a function to reverse a string, or the digits (decimal or binary) of a given number.

Reverse a string:

char* revString(string str) { 
    unsigned int len = str.length();
    char* newStr = new char[len+1]; 
    for (unsigned int i = 0; i < len; i++) { 
         newStr[i] = str[len - i - 1];
    }
    newStr[len] = '\0';
    return newStr;
}

 

[Jamin2112]

IWrite a function to reverse a linked list.

Without loss of generality, suppose it's a linked integer list created from the data structure

struct listElement { 
     int val;
     listElement* next;
}

and suppose

listElement* root

is the first element.

The procedure will first need to know how many elements are in the list. So we'll need a function like

unsigned int numElements(listElement* root) { 
   unsigned int count = 1;
   listElement* currentElementPtr = root;
    while (currentElementPtr->next != NULL) { 
         count++;
         currentElementPtr = currentElementPtr->next;
    }
   return count;
}

Fairly simple after that. Make another function that loops through all the elements and swaps their pointers with those on the opposite end.

 

[Jamin2112]

Will work on the others tomorrow morning. It's 1:05 a.m. right now. :zzz:

 

[rcgldr]

1. Pointer to char vs. array of char ... Which is correct, and why?

Both those are "legal" and they do the exact same thing, which is, they return a pointer to "H". But you'd want to use the second because it adds a null character as a sentinel to denote the end of the string.

What happens to "str" once the code exits the functions getstring1() or getstring2()? How does this affect what is returned by those functions?

The test program mentioned in the first post of this thread is a bit more lengthy than what I would expect for an inteview test. How much time do you have to write these test programs?

5. Write a function to count how many "1" bits appear in the binary representation of the input number.

Side note, this is an intrinsic function with some compilers, and an instruction for recent versions of the X86 processor. So don't cheat on this one by using the intrinsic function.

 

[jbunniii]

Both those are "legal" and they do the exact same thing, which is, they return a pointer to "H". But you'd want to use the second because it adds a null character as a sentinel to denote the end of the string.

No, both strings are null-terminated. That isn't the issue. The problem is more serious: in one of the functions, the memory containing "Hello" disappears after the function returns. Focus on the two initializers:

char *str = "Hello";

vs.

char str[] = "Hello";

Where is the string "Hello" stored in each case?

 

[jbunniii]

Reverse a string:

char* revString(string str) { 
    unsigned int len = str.length();
    char* newStr = new char[len+1]; 
    for (unsigned int i = 0; i < len; i++) { 
         newStr[i] = str[len - i - 1];
    }
    newStr[len] = '\0';
    return newStr;
}

I don't want the function to allocate memory. Please reverse the string "in place". Also, your function uses a std::string for input and returns a C-style string for output. Please pick one and stick with it.

 

[jbunniii]

Without loss of generality, suppose it's a linked integer list created from the data structure

struct listElement { 
     int val;
     listElement* next;
}

and suppose

listElement* root

is the first element.

The procedure will first need to know how many elements are in the list. So we'll need a function like

unsigned int numElements(listElement* root) { 
   unsigned int count = 1;
   listElement* currentElementPtr = root;
    while (currentElementPtr->next != NULL) { 
         count++;
         currentElementPtr = currentElementPtr->next;
    }
   return count;
}

Fairly simple after that. Make another function that loops through all the elements and swaps their pointers with those on the opposite end.

The devil is in the details. Also, it's not necessary to count the elements. Suppose my list contains a billion elements. We don't want to have to make two passes through the list, one for counting and one for reversing.

 

[jbunniii]

Side note, this is an intrinsic function with some compilers, and an instruction for recent versions of the X86 processor. So don't cheat on this one by using the intrinsic function.

Indeed, please make the function as portable as possible. Don't make any assumptions about the target platform's integer size. For definiteness, assume the input is an unsigned long:

unsigned int NumberOfOneBits(unsigned long inputVal)
{
    // ...
}

 

[Jamin2112]

5. Write a function to count how many "1" bits appear in the binary representation of the input number.

Critique my answer:

unsigned int countOneBits(int num) { 
   unsigned int count;
   for (unsigned int i = 0; i < sizeof(int) * 8; i++) { 
         count += (num % 2 == 1 ? 1 : 0);
         num = num /= 2;
   } 
   return count;
}

 

[Jamin2112]

No, both strings are null-terminated. That isn't the issue. The problem is more serious: in one of the functions, the memory containing "Hello" disappears after the function returns. Focus on the two initializers:

char *str = "Hello";

vs.

char str[] = "Hello";

Where is the string "Hello" stored in each case?

I'm going to admit that I don't know the difference. Can you explain this one to me?

 

[rcgldr]

Critique my answer

Try compiling the program and check the results with varius numbers. For example, try the number 0x88888888, which should return 8.

Some of these programs have "clever" alternative methods that can be used. For this program, note that num &= num-1; clears the least significant 1 bit from num.

 

[Jamin2112]

I don't want the function to allocate memory. Please reverse the string "in place". Also, your function uses a std::string for input and returns a C-style string for output. Please pick one and stick with it.

First of all, thanks for the help so far! Keep critiquing me as harshly as possible.

I think I will need some additional memory to do this because I need a temporary placeholder for a character.

string revString(string str) { 
    char temp; 
    for (unsigned int i = 0; i < str.length(); i++) { 
        temp = str[i];
        str[i] = str[str.length() - i - 1];
        str[str.length() - i - 1] = temp;
    }
    return str;
}

 

[Jamin2112]

Some of these programs have "clever" alternative methods that can be used. For this program, note that num &= num-1; clears the least significant 1 bit from num.

Dammit. My electrical engineer buddy is good at doing this fancy logic with bits. Me, not so much. I'll think about this a little later.

 

[Jamin2112]

Indeed, please make the function as portable as possible. Don't make any assumptions about the target platform's integer size. For definiteness, assume the input is an unsigned long:

unsigned int NumberOfOneBits(unsigned long inputVal)
{
    // ...
}

In that case you could use the procedure I mentioned:

unsigned int NumberOfOneBits(unsigned long inputVal) {
     unsigned int count = 0;
     for (unsigned int i = 0; i < sizeof(unsigned long) * 8; i++) { 
         count += inputVal % 2 ? 1 : 0;  
         inputVal /= 2;
     }
     return count;
}

 

[Jamin2112]

4. Write a function to sort an array of numbers in place. (Or an array of strings.)

Just to be clear: So I should take an array of unique numbers and rearrange them from least to greatest?

double* SortNumbers(double* arr, unsigned int size) { 
   // move around stuff in arr
   return arr; 
}

 

[rcgldr]

No, both strings are null-terminated. That isn't the issue. The problem is more serious: in one of the functions, the memory containing "Hello" disappears after the function returns. Focus on the two initializers:

char *str = "Hello";

vs.

char str[] = "Hello";

Where is the string "Hello" stored in each case?

I'm going to admit that I don't know the difference. Can you explain this one to me?

You may be unaware that the C standard states that literal strings like "Hello" have static duration (they exist from the tiime the program starts until the program ends), and that the string is constant. For the second case, char str[] = "Hello"; , I'm not sure if the compiler creates a static literal string and copies it to str[], or just initializes str[] to "Hello" without creating a static literal string. The problem is that str[] goes away in the second case. In the first case, the function returns a pointer to the static literal string "Hello", and although str no longer exists, the pointer returned is still valid because "Hello" is a static literal string. The proper syntax would be

const char * str = "Hello";

 

[jbunniii]

Critique my answer:

unsigned int countOneBits(int num) { 
   unsigned int count;
   for (unsigned int i = 0; i < sizeof(int) * 8; i++) { 
         count += (num % 2 == 1 ? 1 : 0);
         num = num /= 2;
   } 
   return count;
}

Several problems here:

1. You didn't initialize count to anything, so its value is unpredictable. You have to initialize it to zero.

2. sizeof(int) * 8 assumes that the architecture uses 8-bit bytes. Believe it or not, there are architectures (such as specialized DSP processors) where this is not true.

3. Your num parameter is a signed integer. Your calculation may not work if num is negative, because the behavior of the % operator with a negative operand is implementation-defined. The input should be an unsigned int or unsigned long.

 

[jbunniii]

I think I will need some additional memory to do this because I need a temporary placeholder for a character.

Yes, it's no problem to use temporary local variables. But don't create stuff using new or malloc unless you verify that it's OK with the interviewer. This is not an arbitrary restriction: on some platforms (e.g. if you're writing a low level application for a cell phone) you aren't allowed to use new/malloc at all. And even where it's acceptable, it is a resource leak waiting to happen if not done carefully.

string revString(string str) { 
    char temp; 
    for (unsigned int i = 0; i < str.length(); i++) { 
        temp = str[i];
        str[i] = str[str.length() - i - 1];
        str[str.length() - i - 1] = temp;
    }
    return str;
}

This doesn't work because your loop iterates across the entire string. Think about this - you will exchange the first and last character TWICE, so they will end up where they started.

Aside from that, here are some critiques:

1. You are unnecessarily making two copies of str: once when it is passed to you as an argument, and once when you return it. You can avoid both of these copies by changing the function so it accepts a reference to the string:

void revString(string &str)

2. "temp" can be defined inside the "for" loop since it is not used outside the loop. It's good practice to define local variables to have the smallest scope possible.

3. You can use iterators instead of the integer index. This makes it less likely that you will get the indexing wrong and write outside the array.

 

[Jamin2112]

Several problems here:

1. You didn't initialize count to anything, so its value is unpredictable. You have to initialize it to zero.

2. sizeof(int) * 8 assumes that the architecture uses 8-bit bytes. Believe it or not, there are architectures (such as specialized DSP processors) where this is not true.

3. Your num parameter is a signed integer. Your calculation may not work if num is negative, because the behavior of the % operator with a negative operand is implementation-defined. The input should be an unsigned int or unsigned long.

1. Sorry. I knew that.

2. True, true.

3. Yea, I redid it later in this thread to correct for the problem you mention.

 

[jbunniii]

Just to be clear: So I should take an array of unique numbers and rearrange them from least to greatest?

double* SortNumbers(double* arr, unsigned int size) { 
   // move around stuff in arr
   return arr; 
}

Right, but they don't necessarily need to be unique. Also, you don't need to return the pointer. You can do it like this, again modifying "arr" in place:

void SortNumbers(double* arr, unsigned int size)

 

[Jamin2112]

This doesn't work because your loop iterates across the entire string. Think about this - you will exchange the first and last character TWICE, so they will end up where they started.

Wow. I'm an idiot. But I think I know an easy fix. I just change it the condition of the for loop to str.length() / 2.

1. You are unnecessarily making two copies of str: once when it is passed to you as an argument, and once when you return it. You can avoid both of these copies by changing the function so it accepts a reference to the string:

void revString(string &str)

Yes. I'll redo this.

2. "temp" can be defined inside the "for" loop since it is not used outside the loop. It's good practice to define local variables to have the smallest scope possible.

Thanks for the tip. I'll make sure to do this.

3. You can use iterators instead of the integer index. This makes it less likely that you will get the indexing wrong and write outside the array.

I'll do this too.

 

[Jamin2112]

Ok, here's the string reversal:

#include <iostream>


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



int main() { 

string s = "Jamin"; 
cout << s << endl;
ReverseString(s);
cout << s;

return 0;
}

Output:

Jamin
nimaJ

 

[jbunniii]

Output:

Jamin
nimaJ

Looks good to me.

 

[D H]

Ok, here's the string reversal:

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

 

[rcgldr]

count 1 bits ..

This isn't allowed in some older version of C (ones still using C89 standard).

   for (unsigned int i = 0; ...

Instead you need to delcare variables (and optionally initialize them) at the start of a function:

   int i;
   for (i = 0; ...

Alternative method for counting 1 bits:

int countOneBits(unsigned long num)
{ 
int count = 0;

    while(num){
        count += 1;
        num &= num-1;
    }
    return(count);
}

 

[D H]

This normally isn't allowed in C:

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