Need help being assessed on basic programming questions

1. Jul 8, 2013

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.

2. Jul 9, 2013

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?

Code (Text):

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

vs.

Code (Text):

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.

3. Jul 9, 2013

Jamin2112

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.

4. Jul 9, 2013

Jamin2112

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

5. Jul 9, 2013

Jamin2112

Reverse a string:

Code (Text):

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

6. Jul 9, 2013

Jamin2112

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

Code (Text):

struct listElement {
int val;
listElement* next;
}

and suppose

Code (Text):

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

Code (Text):

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.

7. Jul 9, 2013

Jamin2112

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

8. Jul 9, 2013

rcgldr

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?

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.

9. Jul 9, 2013

jbunniii

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?

10. Jul 9, 2013

jbunniii

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.

11. Jul 9, 2013

jbunniii

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.

12. Jul 9, 2013

jbunniii

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:
Code (Text):

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

13. Jul 9, 2013

Jamin2112

Code (Text):

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

14. Jul 9, 2013

Jamin2112

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

15. Jul 9, 2013

rcgldr

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.

Last edited: Jul 9, 2013
16. Jul 9, 2013

Jamin2112

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.

Code (Text):

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

17. Jul 9, 2013

Jamin2112

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.

18. Jul 9, 2013

Jamin2112

In that case you could use the procedure I mentioned:

Code (Text):

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

19. Jul 9, 2013

Jamin2112

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

Code (Text):

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

20. Jul 9, 2013

rcgldr

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