about line pretest

Line_pretest.md

Q1 Where n is a positive integer, the function $ f(n)$ satisfies the following.

(1) Please create a program to find $ f(n)$ .(You can write in any language that you are good at.)

Here can using recursive to sloving this problem:

def fib(i):
    if i<2: return 1
    return fib(i-1)+fib(i-2)

But can reduce the time complexity by save the return value in list:

def fibonacci(n, fib=[0, 1]):
    if n >= len(fib):
        for i in range(len(fib), n+1):
            fib.append(fib[i-1]+fib[i-2])
    return fib[n]

or using DP:

class dpFib(object):
    def __init__(self):
        self.__result = {0: 0, 1: 1}

    def fib(self, x):
        if x in self.__result:
            return self.__result[x]

        r = self.fib(x-1) + self.fib(x-2)
        self.__result[x] = r
        return r

dpfib = dpFib()
print(dpfib.fib(x=8181))

(2) Use the program from (1) to find $ f(8181)$.

fibonacci(n=8181)

---

Q2 Please implement a program that lists the nodes of a random binary tree by nodes at the same depth.

Using BFS, code:

def bfs(graph, queue, visited=None):
    if visited is None:
        visited = set()
    if not queue:
        return
    start = queue.pop(0)
    yield start
    visited.add(start)
    queue += [vertex for vertex in graph[start] - set(queue) - visited]
    yield from bfs(graph, queue, visited=visited)


def bfs_paths(graph, queue, goal):
    if not queue:
        return
    (start, path) = queue.pop(0)
    if start == goal:
        yield path
    queue += [(vertex, path + [vertex]) for vertex in graph[start] - set(path)]
    yield from bfs_paths(graph, queue, goal)


graph = {
    'A': set(['B', 'C']),
    'B': set(['A', 'D', 'E']),
    'C': set(['A', 'F']),
    'D': set(['B']),
    'E': set(['B', 'F']),
    'F': set(['C', 'E']),
}

print(repr([vertex for vertex in bfs(graph, ['A'])]))
print(repr([path for path in bfs_paths(graph, [('A', ['A'])], 'F')]))

Output:

['A', 'C', 'B', 'F', 'D', 'E']
[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

---

Q3 (1) Imagine you are playing a board game. You roll a 6-faced dice and move forward the same number of spaces that you rolled. If the finishing point is “n” spaces away from the starting point, please implement a program that calculates how many possible ways are there to arrive exactly at the finishing point.

/* 
 * Description: solve dice combinations using dynamic programing
 * Complier: g++
 */
#include <iostream>
#include <string>
#include <cmath>
#include <vector>

using namespace std;

/****************************************************************
 * dice Combinations: using dynamic programming
 *
 * Basic idea:
 * dp[i][j] = sum(dp[i-1][j-k*coins[i-1]]) for k = 1,2,..., j/coins[i-1]
 * dp[0][j] = 1 for j = 0, 1, 2, ..., sum
 *
 * Output:
 * the number of combinations using dice construct sum
 *
 * Usage:
 * c[6] = {1, 2, 3, 4, 5, 6};
 * int result = diceCombinations(c, 6, 100);
 *
 ****************************************************************/
int diceCombinations(int coins[], int diceKinds, int sum)
{
    // 2-D array using vector: is equal to: dp[diceKinds+1][sum+1] = {0};
    vector<vector<int> > dp(diceKinds + 1);
    for (int i = 0; i <= diceKinds; ++i)
    {
        dp[i].resize(sum + 1);
    }
    for (int i = 0; i <= diceKinds; ++i)
    {
        for (int j = 0; j <= sum; ++j)
        {
            dp[i][j] = 0;
        }
    }

    //init: dp[i][0] = 1; i = 0, 1, 2 ..., diceKinds
    //Notice: dp[0][0] must be 1
    //using 0 kinds of dice construct 0 has one way. but it the foundation
    //of iteration. without it everything based on it goes wrong
    for (int i = 0; i <= diceKinds; ++i)
    {
        dp[i][0] = 1;
    }

    // iteration: dp[i][j] = sum(dp[i-1][j - k*coins[i-1]])
    // k = 0, 1, 2, ... , j / coins[i-1]
    for (int i = 1; i <= diceKinds; ++i)
    {
        for (int j = 1; j <= sum; ++j)
        {
            dp[i][j] = 0;
            for (int k = 0; k <= j / coins[i-1]; ++k)
            {
                dp[i][j] += dp[i-1][j - k * coins[i-1]];
            }
        }
    }

    return dp[diceKinds][sum];
}


int main()
{
    int coins[6] = {1, 2, 3, 4, 5, 6};
    int sum = 610;
    int result = diceCombinations(coins, 6, 610);
    cout << "using 6 kinds of dice construct 610, combinations are: " << endl;
    cout << result << endl;
    return 0;
}

def count(S, m, n):
    # We need n+1 rows as the table is consturcted in bottom up
    # manner using the base case 0 value case (n = 0)
    table = [[0 for x in range(m)] for x in range(n + 1)]

    # Fill the enteries for 0 value case (n = 0)
    for i in range(m):
        table[0][i] = 1

    # Fill rest of the table enteries in bottom up manner
    for i in range(1, n + 1):
        for j in range(m):
            # Count of solutions including S[j]
            x = table[i - S[j]][j] if i - S[j] >= 0 else 0

            # Count of solutions excluding S[j]
            y = table[i][j - 1] if j >= 1 else 0

            # total count
            table[i][j] = x + y

    return table[n][m - 1]

(2) If n=610, how many possible ways are there to arrive exactly at the finishing point?

output = 

---

Q4 Please tell us about the technologies you frequently use.

---

Q5 Please answer the questions below.

Thank you for your time!

---