鴻揚科技有限公司於 104 應徵軟體開發工程師之面試題目

Interview_algorithm.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            Stopwatch s = new Stopwatch();

            s.Start();
            int ans1 = Test1();
            s.Stop();
            Console.WriteLine(ans1);
            Console.WriteLine(string.Format("Ans1 Totally spend {0} seconds", s.Elapsed.TotalSeconds));

            s.Reset();
            s.Start();
            int ans2 = Test2();
            s.Stop();
            Console.WriteLine(ans2);
            Console.WriteLine(string.Format("Ans2 Totally spend {0} seconds", s.Elapsed.TotalSeconds));

            Console.ReadLine();
        }

        /* 題目一：
         * 將 1 ~ 24 共 24 個正整數平均分成三組，每組 8 個數字，且 8 個數字合為 100。請問有幾種分法
         * 答案 1025113
         * 同時計算出需花多少時間(需小於 1 分鐘；最佳化可達 1 秒
         */

        private static int Test1()
        {
            int ans = 0;
            List<int[]> hjwu1 = new List<int[]>();
            int i1 = 1;
            for (int i2 = i1 + 1; i2 <= 11; i2++)
                for (int i3 = i2 + 1; i3 <= (100 - i1 - i2) / 6 - 2; i3++)
                    for (int i4 = i3 + 1; i4 <= (100 - i1 - i2 - i3) / 5 - 2; i4++)
                        for (int i5 = i4 + 1; i5 <= (100 - i1 - i2 - i3 - i4) / 4 - 1; i5++)
                            for (int i6 = i5 + 1; i6 <= (100 - i1 - i2 - i3 - i4 - i5) / 3 - 1; i6++)
                                for (int i7 = i6 + 1; i7 <= (100 - i1 - i2 - i3 - i4 - i5 - i6) / 2; i7++)
                                {
                                    int i8 = 100 - (i1 + i2 + i3 + i4 + i5 + i6 + i7);
                                    if (i8 < 25 && i8 > i7)
                                        hjwu1.Add(new int[] { i1, i2, i3, i4, i5, i6, i7, i8 });
                                }

            for (int j0 = 0; j0 < hjwu1.Count; j0++)
            {
                var r0 = hjwu1[j0];
                var r1 = Enumerable.Range(1, 24).Except(r0).ToArray();
                int j1 = 0;

                for (int j2 = j1 + 1; j2 < 16; j2++)
                    for (int j3 = j2 + 1; j3 < 16; j3++)
                        for (int j4 = j3 + 1; j4 < 16; j4++)
                            for (int j5 = j4 + 1; j5 < 16; j5++)
                                for (int j6 = j5 + 1; j6 < 16; j6++)
                                    for (int j7 = j6 + 1; j7 < 16; j7++)
                                        for (int j8 = j7 + 1; j8 < 16; j8++)
                                        {
                                            if (r1[j1] + r1[j2] + r1[j3] + r1[j4] + r1[j5] + r1[j6] + r1[j7] + r1[j8] == 100)
                                            {
                                                ans++;
                                                break;
                                            }
                                        }
            }
            return ans;
        }

        /* 題目二：
         * Find the number of possible partitions of a natural number 40
         * Answer 37338
         */

        private static int Test2()
        {
            int r = 40;
            Dictionary<int, List<string>> hjwu2 = new Dictionary<int, List<string>>();
            for (int i = 1; i <= r; i++)
            {
                List<string> tmp = new List<string>() { string.Format("{0},", i) };
                for (int j = i - 1; j >= 1; j--)
                {
                    if (j > 0)
                    {
                        var tmp2 = hjwu2[i - j];
                        foreach (var t in tmp2)
                        {
                            int k = int.Parse(t.Split(',')[0]);
                            if (k <= j) tmp.Add(j.ToString() + "," + t);
                        }
                    }
                }

                hjwu2.Add(i, tmp);
            }
            return hjwu2[r].Count;
        }
    }
}

補充一下 Partition 的意義。

另外題目原網址為：http://m.104.com.tw/job/3c2kh 然後他第二題答案給錯了 XD