atoha-it / atoha-talents

RoR intern interview project
0 stars 1 forks source link

First round - Binh Nguyen #2

Closed phthhieu closed 8 years ago

phthhieu commented 8 years ago

Objectives

Deadline

Questions

Please solve these problems by any framework and your best programming language:

Step-by-step to complete this round

[Problem name]
[Your code]

Enjoy your tests!

kieutriet commented 8 years ago

Dear Mr. Hieu, Thank you for the test. I ran into some troubles with big numbers in problem No.3 . I tried another language already but I am not sure if I can handle it when you request me to modify my code. So I decided to deal with them in C and have a time-out problem as the following picture. image Could you suggest an idea to overcome this? Thank you very much. I've attached my code below.

/* Modifed Fibonacci */
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int M2 = 0;
int *square(int *a);
int *add(int *a, int *b);

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int i = 0, n, t1, t2, j;
    int x[100000], y[100000];
    int *accum;
    scanf("%d%d%d", &t1, &t2, &n);
    x[0] = t1; y[0] = t2;

    for (i=3;i<=n;i++) {
        accum = add(x,square(y));
        for (j=0;j<=M2;j++) {
            x[j] = y[j];
            y[j] = accum[j];
        }
    }
    for (i=M2;i>=0;i--) {
        printf("%d",accum[i]);
    }
    return 0;
}

int *square(int *a){
    static int r[100000];
    int b[100000];
    int i,j,temp,m = 0;
    for (i=0;i<100000;i++) {
        r[i] = 0;
    }
    for (i=0;i<=M2;i++) {
        b[i] = a[i];
    }
    for (j=0;j<=M2;j++) {
        for (i=0;i<=M2;i++) {
            m = i + j;
            temp = a[i]*b[j];
            while (temp > 0) {
                temp += r[m];
                r[m] = temp % 10;
                temp /= 10;
                m++;
            }
        }
    }
    M2 = m - 1;

    return r;
}

int *add(int *a, int *b) {
    static int s[100000];
    int i, carry=0;
    for (i=0;i<100000;i++) {
        s[i] = 0;
    }
    for (i=0;i<=(M2+1);i++) {
        s[i] = a[i] + b[i] + carry;
        carry = 0;
        while (s[i]>9) {
            s[i] %= 10;
            carry = 1;
        }
    }
    if (s[M2+1] != 0) {M2++;};
    return s;
}
kieutriet commented 8 years ago
/* Diagonal Difference */
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int n;
    int diff = 0;
    scanf("%d",&n);
    int a[n][n];
    for(int a_i = 0; a_i < n; a_i++){
       for(int a_j = 0; a_j < n; a_j++){
          scanf("%d",&a[a_i][a_j]);
          if (a_i == a_j) {
              diff += a[a_i][a_j];
          }
          if (a_i + a_j == n-1) {
              diff -= a[a_i][a_j];
          }
       }
    }
    diff = abs(diff);
    printf("%d", diff);
    return 0;
}
kieutriet commented 8 years ago
/* Missing Number */
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int n[10001];
    int x, i;

    for (i=0;i<10001;i++) {
        n[i] = 0;
    }

    scanf("%d", n);
    for (i=0;i<n[0];i++) {
        scanf("%d", &x);
        *(n + x) -= 1;
    }
    scanf("%d", n);
    for (i=0;i<n[0];i++) {
        scanf("%d", &x);
        *(n + x) += 1;
    }
    for (i=1;i<10001;i++) {
        if (*(n+i) != 0) {
            printf("%d ", i);
        }
    }
    return 0;
}
phthhieu commented 8 years ago

Hi Binh,

Fibonacci Modified

n! = 1 * 2 * 3 * 4 *....*(n-1) * n

so we calculate 1! , then 2! = 1! * 2, then we should save 1! & 2! to temporary variables for further calculation 3!, 4!,...

The is the clue to solve the timeout issue.

Btw could you explain what do M2 and accum use for?

And in this section:

for (i=3;i<=n;i++) {
        accum = add(x,square(y));
        for (j=0;j<=M2;j++) {
            x[j] = y[j];
            y[j] = accum[j];
        }
    }

Why does i start from 3, and why we have 2 nested loops? Is it necessary? I'm not saying it is incorrect, just confusing and need your explanation.

Diagonal Difference

Why this section help you solve the problem correctly, could you explain?

if (a_i == a_j) {
  diff += a[a_i][a_j];
}
if (a_i + a_j == n-1) {
  diff -= a[a_i][a_j];
}

Missing number

Could you explain why these libraries were included in your code?

#include <string.h>
#include <math.h>
#include <stdlib.h>
kieutriet commented 8 years ago

Dear Mr. Hieu,

Here is my explanation for your questions:

Fibonacci Modified

Btw could you explain what do M2 and accum use for?

In this problem, the value of some terms may exceed the range of an integer and C can't handle such large numbers. So I relocated every term into arrays and used the calculation algorithms taught at schools. M2is a global variable indicating the maximum index of the array containing the current term. For example, the current term is 8574 then M2is 3. It helps me control the loop while using the calculation algorithms. accumis a temporary variable containing the value of the current term, which is computed using the two latest term (I called them xand y). After that, xis assigned the value of yand yis assigned the value of accum. The loop goes on until we get the desired term.

Why does i start from 3, and why we have 2 nested loops? Is it necessary?

We had the first two terms already, t1and t2. So the loop starts withi = 3 to compute the third term and continues until the n term. It can start with any number, I just want to make it easy: from 3 to n. The second loop is used to assign x, y the values of y, accum, respectively. Since x, y and accumare relocated in arrays, I used the second loop to copy each element's value. For the reason that I didn't store every term of the Fibs, I had to use a second loop to shift the value at once, before conducting a new loop to compute a new term.

Diagonal Difference

Why this section help you solve the problem correctly, could you explain?

Entries on the primary diagonal have an attribute that is: column index = row index. Entries on the secondary diagonal have an attribute that is: column index + row index = the size of matrix - 1. diffis a variable containing the difference between the two sum of the diagonals. There is only one loop and a variable diffcontaining the difference so I have to add the numbers on two diagonals to the diffwith opposite signs. It is (a+b)-(c+d) = a+b-c-d. Finally, I take the absolute value of diffand get the result.

Missing Number

Could you explain why these libraries were included in your code?

Actually these libraries were available at the beginning of the test. I wrote the code without paying attention to them.

If you need any additional explanation, or require me to make any improvement, please comment below. About time-out problem, I will check again and try to optimize it. Thank you for your advice.

phthhieu commented 8 years ago

Okay, here is the summary:

  1. Fibonacci Modified: Try with my suggestion or any better solution you may figure out. Then explain why your solution/improvement work.
  2. Diagonal Difference: Okay
  3. Missing Number: Okay
phthhieu commented 8 years ago

@kieutriet How is it going? You have several hours to make your improvements, I'm just kindly reminding you the deadline

kieutriet commented 8 years ago

Dear Mr. Hieu, Thank you for reminding me. I used the elements of the arrays to store a range of 0-9999 instead of 0-9 as before to save memory. Besides, the amount of operations was also reduced. The timeout error was gone, I'm now dealing with another problem regarding Segmentation Fault. This is my latest code for the problem # 3.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int M2 = 0;
int *square(int *a);
int *add(int *a, int *b);

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int i = 0, n, t1, t2, j;
    int x[20000], y[20000];
    int *accum;
    scanf("%d%d%d", &t1, &t2, &n);
    x[0] = t1; y[0] = t2;

    for (i=3;i<=n;i++) {
        accum = add(x,square(y));
        for (j=0;j<=M2;j++) {
            x[j] = y[j];
            y[j] = accum[j];
        }
    }
    printf("%d",accum[M2]);
    for (i=M2-1;i>=0;i--) {
        printf("%.4d",accum[i]);
    }
    return 0;
}

int *square(int *a){
    static int r[20000];
    int b[20000];
    int i,j,temp,m = 0;
    for (i=0;i<20000;i++) {
        r[i] = 0;
    }
    for (i=0;i<=M2;i++) {
        b[i] = a[i];
    }
    for (j=0;j<=M2;j++) {
        for (i=0;i<=M2;i++) {
            m = i + j;
            temp = a[i]*b[j];
            while (temp > 0) {
                temp += r[m];
                r[m] = temp % 10000;
                temp /= 10000;
                m++;
            }
        }
    }
    M2 = m - 1;

    return r;
}

int *add(int *a, int *b) {
    static int s[20000];
    int i, carry=0;
    for (i=0;i<20000;i++) {
        s[i] = 0;
    }
    for (i=0;i<=(M2+1);i++) {
        s[i] = a[i] + b[i] + carry;
        carry = 0;
        while (s[i]>9999) {
            s[i] %= 10000;
            carry = 1;
        }
    }
    if (s[M2+1] != 0) {M2++;};
    return s;
}
phthhieu commented 8 years ago

@kieutriet Your failed test cases were test 2, 3 and 6 previously, now you just solved the test 2. Do you accept your latest change is the final submission? Or need more time to continue working on this?

kieutriet commented 8 years ago

That is my final submission. I will continue to work on this later. Thank you.

phthhieu commented 8 years ago

Ok, thank for your effort, I will evaluate & send you back the result before this Friday 29-July