Fibonacci C code

Discussion in 'C Programming' started by kishan123, Aug 4, 2018.

  1. kishan123

    kishan123

    Joined:
    Aug 4, 2018
    Messages:
    1
    Likes Received:
    0
    I was given this question in my interview but couldn't crack it.
    Please go through it and help me out.

    As we know in Fibonacci series every number after the first two is the sum of the two preceding ones.
    Instead of adding two preceding numbers, multiply them and print the result modulo 10^9+7.
    Since this is easy, let’'s make it bit difficult. Let'’s say there are K numbers to begin with.
    You have to find nth number, where nth number will be product of k previous numbers modulo 10^9+7.

    Constraints
    1<=t<=10
    1<=n<=10^6
    1<=k<=10
    1<=k<=100

    Input Format
    First line contains T number of test case,
    In each test case
    First line contains two integers n, k delimited by space
    Second line contains k integers delimited by space

    Output
    T lines, each line contains modified Fibonacci number modulo 109+7

    Explanation
    Example 1
    Input
    1
    10 3
    1 2 3

    Output
    845114970

    Explanation
    4th , 5th , 6th modified Fibonacci numbers are 6 , 36 , 648 respectively
    Similarly 10th modified Fibonacci number will be 845114970

    My Solution:

    Code (C):
    #include<stdio.h>
    #define Modulo 1000000007
    long long int Num2Mod(long long int A,long long int B);
    main()
    {
        int K[10],n,k,i,j,t,first,second =1;
        long long int product,list[1000000];
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d %d",&n,&k);
            for(i=0;i<k;i++)
            {
                scanf("%d",&K);
                list=K;
            }
            for(i=0;i<n-2;i++)
            {
                product = 1;
                for(j=0;j<k;j++)
                    product = Num2Mod(product,list[i+j]);
                list[i+k] = product;
            }
            printf("%lld\n",list[n-1]);
        }
    }
    long long int Num2Mod(long long int A,long long int B)
    {
        return ((A%Modulo*B%Modulo)%Modulo);
    }
    Help me out here please.
    Thank You.
     
    Last edited by a moderator: Aug 5, 2018
    kishan123, Aug 4, 2018
    #1
    1. Advertisements

  2. kishan123

    JasKinasis

    Joined:
    Jun 27, 2018
    Messages:
    11
    Likes Received:
    4
    Location:
    /dev/null
    OK, there are a number of problems there that I can instantly see that would be bad from an interviewers point of view:

    1. You have two unused variables in your code called "first" and "second".
    Leaving unused variables in code is a little bit sloppy and definitely NOT what you want to be doing in an interview situation!

    2. No prompts for the user.
    As your code stands, your program will just hang there waiting for input.
    A user will not know what kind of input is expected without some kind of prompt. Your interviewers may have wanted to see instructional prompts in your program.

    3. Some of the variables are badly named.
    Single letter variable names are not very helpful. By using clear, concise variable names, your code will be more readable and understandable.
    So for example your variable 't' could have been called something like 'numTests', or 'numberOfTests', or 'testsToPerform'. Likewise with some of your other variables. Giving variables descriptive names instantly makes the code more meaningful.

    4. No comments in the code
    Comments are extremely valuable and can help interviewers to gauge a candidates level of understanding of a problem. That way even if the code/logic is slightly wrong - the comments can help to make programmers intentions/understanding clear to the interviewers (or others viewing the code).

    5. No bounds checks:
    There are no bounds checks on any of the user-input values. User input should NEVER be trusted and should always be checked.
    e.g.
    - You haven't checked the value of t (the number of tests) to ensure it is between 1 and 10. The user could set the program to run for any number of tests. It was clearly specified that the number should be between 1 and 10, so you should check it!
    - You haven't checked the value of k (the number of existing numbers) to ensure it is between 1 and 10 (or 1 and 100) - not sure why you have two limits there?! But either way, neither of the limits have been enforced.
    - You haven't checked the value of n (the number of numbers to calculate up to).

    And even if you didn't have time to add bounds checks - you could at least put a comment in the code.
    e.g.
    Code (C):

    /* TODO - Bounds check n - ensure 1 < n < x */
     
    That shows interviewers that you understand that this would normally need to be bounds checked.
    But without a bounds check OR some kind of comment to indicate that you know a bounds-check is appropriate - the interviewer will assume that you hadn't considered bounds checking, which would imply to the interviewer that you are either a sloppy programmer, or you didn't know any better!

    6. Allocating extremely large items on the stack
    The biggest problem that I can see in your code is in this line, which immediately set off alarm bells in my head:
    Code (Text):

    long long int product,list[1000000];
     
    The declaration of the array variable called 'list' - where you are trying to create an array on the stack, to hold up to one million long long int's. This would almost certainly require more memory than the stack would ever be allocated and would probably cause your program to crash as soon as you tried to run it. That is a pretty fatal mistake if you ask me. That alone may have been enough to blow the entire interview!

    The stack size can vary from platform to platform and although it may be possible to use compiler options to customise/increase the stack size for a program - allocating such a large item on the stack is not a good idea! Anything that large should be declared dynamically, on the heap NOT on the stack.

    Instead of declaring 'list' as a huge array of long long int, it would be better and much more efficient to use a long long int pointer instead. In the declaration at the top of the scope - you should initialise the pointer to NULL, then later on - after you have read the value for n (the number of numbers to find/calculate), you can use malloc to allocate an appropriately sized block of memory on the heap and assign the returned pointer to list.
    e.g.
    Code (C):

    //.... variable declarations at the top of the scope ....
    long long int* list='\0'; // list initialised to null

    // ....
    // .... More code ....
    // ....

    //...after reading the value of n...
    // Allocate memory
    list = malloc(n*sizeof(long long int));
    // Check the pointer is valid:
    if(!list)
    {
        printf("Failed to allocate space for list - exiting\n");
        return EXIT_FAILURE;
    }
    // ....
    // .... More code ....
    // ....

    // Don't forget to free the memory when it has been finished with:
    if(list)
    {
        free(list);
        list='\0'; // Explicitly reset the pointer to NULL to avoid having a dangling pointer.
    }
     
    That approach is much more efficient. You will only be allocating the memory that you require for the list of values.
    And more importantly there is no chance that you will exceed the stack-size and cause a crash.

    Besides - there is no point allocating space for a million values if the user only wants to calculate up to the 10th.
    So for extremely large items, or items where the size could vary at run-time - it is much better to find out how much space you need first and then dynamically allocate memory for it on the heap.

    And once 'list' is pointing to the start of a block of memory - I'd leave it pointing there. Don't use pointer arithmetic to iterate through the array. Because if you aren't careful - you might lose track of where the start of the block is and could be unable to deallocate the memory properly. So to dereference each number in the array, you could simply use array notation (as you are already doing with your stack-smashing statically allocated array).
    e.g.
    Code (C):
    list[index]=someValue;
    So for this problem, I think your interviewers would have expected you to have demonstrated some knowledge of memory management and would have been expecting your list to be a dynamically allocated object.

    -- This next point is to do with posting here:
    Finally, for future reference - when posting here - please use code-tags as it preserves the formatting of your code.
    Because you failed to use code-blocks in your original post - I'm assuming that this hideously broken code:
    Code (C):

            for(i=0;i<k;i++)
            {
                scanf("%d",&K);
                list=K;
            }
     
    Is actually supposed to be like this:
    Code (C):

            for(i=0;i<k;i++)
            {
                scanf("%d",&K[i]);
                list[i]=K[i];
            }
     
    To explain what has happened:
    When you posted your code as plain-text, all instances of [i] would have been interpreted by the editor here as markup code for italics. So everything in your original post would have been italicised from the first instance of [i] and all instances of [i] would have disappeared from your post. And this made your code look like it had extra bugs in it.

    Obviously whoever updated your post to use code-tags didn't realise that this was a problem and didn't re-add the missing instances of [i]. But then they might not know C well enough to know that this could be an issue. So please - always use code-tags!

    There a couple of things about the above section of code too:
    8. The array 'K' has been hard-coded to a size of 10. But because you haven't range-checked the value of the variable 'k', it is possible that a user could enter a value for 'k' that exceeds 10. Which would mean that when entering values into 'K' - the bounds of the array could be exceeded. Which is another fairly major, yet preventable bug. Yet another mistake that your interviewers would hold against you and yet another reason for you to range-check user-entered values!

    9. The array called 'K' is completely redundant anyway, you don't need it.
    You could just populate the 'list' array directly:
    Code (C):

            for(i=0;i<k;i++)
            {
                scanf("%lld", &list[i]);
            }
     
    And on a personal note:
    I'd explicitly declare Modulo as a const long long int, rather than using a macro.
    e.g.
    Code (C):

    const long long int Modulo=1000000007;
     
    Because you are using 'long long int' everywhere else and because the value of 'Modulo' is a constant value that you will be using - it makes sense to explicitly declare it as such, rather than using #define - where it will be defined as an int by the pre-processor. But that's just a stylistic thing and my personal preference!

    Other than that, the rest of the algorithm/logic looks good..... I think! I haven't completely desk-checked the numbers, or the algorithm you're using for the final calculations - but from reading your description and from taking a quick look at this bit - off the top of my head - I think the rest of the logic is more or less OK and should yield the expected answers.

    But although your program looks like it should be able to produce the correct results - I'd guess that most of the problems that I have pointed out in your code are probably the main reasons that you failed the question.

    The biggest one will be the problem with the massive array of long long ints on the stack. If your interviewers tried compiling and running your program, I'm pretty certain it would crash straight away! But once you have fixed that issue - your program probably will correctly solve the problem. But again, only as long as the user doesn't enter values that exploit any of the other bugs I have mentioned in your program.

    So you have a few things to work on. Hopefully this provides some insight for you!
     
    JasKinasis, Aug 9, 2018
    #2
    Ian likes this.
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.