Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need help being assessed on basic programming questions

  1. Jul 8, 2013 #1
    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. jcsd
  3. Jul 9, 2013 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Jul 9, 2013 #3
    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.
     
  5. Jul 9, 2013 #4
    I'll have to brush up on this and then answer later. :frown:
     
  6. Jul 9, 2013 #5
    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;
    }
     
  7. Jul 9, 2013 #6
    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.
     
  8. Jul 9, 2013 #7
    Will work on the others tomorrow morning. It's 1:05 a.m. right now. :zzz:
     
  9. Jul 9, 2013 #8

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  10. Jul 9, 2013 #9

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
     
  11. Jul 9, 2013 #10

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  12. Jul 9, 2013 #11

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The devil is in the details. :biggrin: 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.
     
  13. Jul 9, 2013 #12

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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)
    {
        // ...
    }
     
     
  14. Jul 9, 2013 #13
    Critique my answer:

    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;
    }
     
     
  15. Jul 9, 2013 #14
    I'm gonna admit that I don't know the difference. Can you explain this one to me?
     
  16. Jul 9, 2013 #15

    rcgldr

    User Avatar
    Homework Helper

    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
  17. Jul 9, 2013 #16
    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;
    }
     
     
  18. Jul 9, 2013 #17
    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.
     
  19. Jul 9, 2013 #18
    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;
    }
     
     
  20. Jul 9, 2013 #19
    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;
    }
     
     
  21. Jul 9, 2013 #20

    rcgldr

    User Avatar
    Homework Helper

    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";
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Need help being assessed on basic programming questions
Loading...