微軟程式設計一小時--微軟2014實習生招募程式設計模拟測試感想

　　為了接觸體驗微軟實習生程式設計題目，上個月底報了微軟探星秋令營活動。報名位址http://campus.chinahr.com/2014/pages/msfte/ch/RecruitingEvent.asp。其實我還是比較了解自己的實力，對于結果沒有報太大的希望。不過在這次模拟測試的過程中積累了一小點經驗，希望大家以後别犯同樣的錯誤。

模拟測試考核方式

　　參加考核的前提條件是必須在上邊貼出的網址中，申請相應的職位，填寫自己的履歷。2014“智在未來”暑期實習項目，“微軟探星探星秋令營”非暑期實習生的網申截止期限均為2014年3月31日。MACH暑期實習生的網申截止期限為2014年4月18日。具體大家參考官網說明。我是在3月30日申請的職位，4月4日下午3點收到的通知郵件。郵件内容如下：

圖1

　　接着進入模拟測試位址，注冊登入即可。從上可以測試平台不限制語言，支援C、C++、C#和JAVA。

圖2

　　接着點選微軟程式設計一小時，檢視程式設計須知，具體内容大家自己看吧。貼出來圖檔太大http://hihocoder.com/coder-help.html。那麼怎麼送出自己的代碼呢？http://hihocoder.com/problemset/problem/1000

圖3

　　為了提高自己的寫代碼速度，我當然用效率第一的IDE VS2010來寫代碼，最後粘貼到這裡，再送出。

模拟測試題目

題目1 : Arithmetic Expression

時間限制:2000ms

單點時限:200ms

記憶體限制:256MB

描述

Given N arithmetic expressions, can you tell whose result is closest to 9?

輸入

Line 1: N (1 <= N <= 50000).

Line 2..N+1: Each line contains an expression in the format of "a op b" where a, b are integers (-10000 <= a, b <= 10000) and op is one of addition (+), subtraction (-), multiplication (*) and division (/). There is no "divided by zero" expression.

輸出

The index of expression whose result is closest to 9. If there are more than one such expressions, output the smallest index.

樣例輸入

樣例輸出

題目2 : Longest Repeated Sequence

時間限制:10000ms

單點時限:1000ms

You are given a sequence of integers, A = a1, a2, ... an. A consecutive subsequence of A (say ai, ai+1 ... aj) is called a "repeated sequence" if it appears more than once in A (there exists some positive k that ai+k = ai, ai+k+1 = ai+1, ... aj+k = aj) and its appearances are not intersected (i + k > j).

Can you find the longest repeated sequence in A?

Line 1: n (1 <= n <= 300), the length of A.

Line 2: the sequence, a1 a2 ... an (0 <= ai <= 100).

The length of the longest repeated sequence.

5
2 3 2 3 2

我的解答

題目一解決方案

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

namespace LHQ
{
    class Program
    {
        static void Main(string[] args)
        {

            Console.WriteLine("請輸入一個非零的正整數:");
            string strIn = Console.ReadLine();


            int inNo = 0;
            bool res = int.TryParse(strIn, out inNo);
            double[] array = new double[inNo];
            int min = 1;
            if (res&&0<inNo)
            {

                string[] strs = new string[inNo];

                for (int i = 0; i < inNo; i++)
                {
                    strs[i] = Console.ReadLine();

                    string[] strRes = strs[i].Split(' ');
                    if (3 == strRes.Length)
                    {

                        int x = 0;
                        int y = 0;

                        int.TryParse(strRes[0], out x);
                        int.TryParse(strRes[2], out y);
                        array[i] = oper(x, strRes[1], y);
                    }
                    else
                    {
                        Console.WriteLine("您輸入的算術表達式格式不合法！");
                    }
                }

                int near = 9;
                double ab = Math.Abs(array[0] - 9);
                for (int i = 0; i < inNo; i++)
                {
                    if (ab > Math.Abs(array[i] - near))
                    {
                        ab = Math.Abs(array[i] - near);
                        min = i + 1;
                        if (0 == ab)
                            break;
                    }
                }

                Console.WriteLine(min);//輸出最接近結果的 行數
            }
            else
            {
                Console.WriteLine("您輸入的不是正整數");
            }

            Console.ReadKey();
        }

        static double oper(int x, string op ,int y)
        {
            double lastResult = 0.0;
            switch (op)
            {
                case "+":
                    lastResult = x + y;
                    return lastResult;
                case "-":
                    lastResult = x - y;
                    return lastResult;
                case "*":
                    lastResult = x * y;
                    return lastResult;
                case "/":
                    if (0 == y)
                    {
                        Console.WriteLine("分母不能為0");
                        return lastResult;
                    }
                    else
                    {
                        lastResult = x * 1.0 / y;
                        return lastResult;
                    }
                  
                default:
                    Console.WriteLine("不正确的運算符！");
                    return lastResult;
            }
        }
    }
}

在VS中運作結果截圖：

圖4

題目二解決方案

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

namespace LHQ
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("請輸入一個非零的正整數:");
            string strIn = Console.ReadLine();


            int inNo = 0;
            bool res = int.TryParse(strIn, out inNo);
            double[] array = new double[inNo];

            if (res && 0 < inNo)
            {
                string str = Console.ReadLine();

                string[] nos = str.Split(' ');
                if (0 == nos.Length)
                {
                    Console.WriteLine("您輸入的數字之間必須用空格隔開");
                    
                }
                else
                {
                    Dictionary<string, int> dic = new Dictionary<string, int>();

                    foreach (string oStr in nos)
                    {
                        if (dic.ContainsKey(oStr))
                        {
                            dic[oStr]++;
                        }
                        else
                        {
                            dic[oStr] = 1;
                        }
                    }

                    Dictionary<string, int> result = dic.OrderByDescending(r => r.Value).ToDictionary(r => r.Key, r => r.Value);//這個不太熟 google了一下

                    Console.WriteLine(result.First().Key);
                }
            }
            else
            {
                Console.WriteLine("您輸入的不是正整數");
            }

            Console.ReadKey();
        }
    }
}

圖5

一切萬事大吉了嗎？

　　我抓緊最後的幾分鐘将我VS中的代碼送出，等待結果。然而傳回的結果是Compile Error(CE) 編譯錯誤。我一下暈了，這時候時間到了，不能修改了。很明顯在我的VS中編譯運作都正常。它這裡怎麼報錯了呢？然後我就又仔細看了看程式設計須知和提供的C#執行個體：

圖6

圖7

圖8

　　然後我仔細看我送出的代碼：

圖9

　　都是眼淚啊。Ctrl C Ctrl V 粗心造成的後果。為了和測試平台編譯器一緻，我特意下載下傳了Windows平台下的Monohttp://www.go-mono.com/mono-downloads/download.html。然後利用mono指令行編譯我的程式，結果如下：完全正确。

圖10

　　要是像我送出的代碼中注釋第一行using System;

圖11

有沒有其它解法呢？

　　對于第一題，是我目前想到的唯一解法。計算接近程度是否有更好的算法呢？希望大家分享一下自己的思路。

　　對于第二題，我的基本思想就是周遊字元串數組，利用Dictionary存儲關鍵字出現的次數。最後偷懶利用我不熟悉的Linq取出了出現次數最多的key。

　　我又有以下2種想法：

　　1、用數組來統計每個數字的出現次數

　　2、利用已知條件的數字的大小在0和100之間，設定一個int[101]的數組，巧妙将輸入的數字和數組索引對應，直接統計輸入數字的次數，直接取第一個最大值對應的索引即為出現次數最多的數字。

第一種想法實作：

using System;

namespace LHQ
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("請輸入一個非零的正整數:");
            string strIn = Console.ReadLine();


            int inNo = 0;
            bool res = int.TryParse(strIn, out inNo);
            double[] array = new double[inNo];

            if (res && 0 < inNo)
            {
                string str = Console.ReadLine();

                string[] nos = str.Split(' ');
                int length = nos.Length;
                if (0 == length)
                {
                    Console.WriteLine("您輸入的數字之間必須用空格隔開");

                }
                else
                {
                    int[] temp = new int[101];//題目中限制了每個輸入數字的大小 最大為100

                    //直接統計每個數字出現的次數 o(n)
                    for (int i = 0; i < length; i++)
                    {
                        int no = int.Parse(nos[i]);
                        temp[no]++;
                    }

                   //比較法直接取出現次數最多的數
                    int max = 0;
                    int maxNo = 0;
                    for (int i = 1; i < 101; i++)
                    {

                        if (temp[i] > max)
                        {
                            max = temp[i];
                            maxNo = i;
                        }
                    }

                    Console.WriteLine(maxNo);

                }
            }
            else
            {
                Console.WriteLine("您輸入的不是正整數");
            }

            Console.ReadKey();
        }
    }
}

第二種想法實作：

using System;

namespace LHQ
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("請輸入一個非零的正整數:");
            string strIn = Console.ReadLine();


            int inNo = 0;
            bool res = int.TryParse(strIn, out inNo);
            double[] array = new double[inNo];

            if (res && 0 < inNo)
            {
                string str = Console.ReadLine();

                string[] nos = str.Split(' ');
                int length = nos.Length;
                if (0 == length)
                {
                    Console.WriteLine("您輸入的數字之間必須用空格隔開");

                }
                else
                {
                    int[] temp = new int[length];

                    //比較法統計每個數字出現的次數 o(n^2)
                    for (int i = 0; i < length; i++)
                    {
                        for (int j = i; j < length; j++)
                            if (nos[i] == nos[j])
                            {
                                temp[j] = temp[j] + 1;
                            }
                    }

                    //比較擷取出現次數最多的數字對應的索引
                    int maxIndex = 0;
                    for (int i = 0; i < length; i++)
                    {
                        if (temp[maxIndex] < temp[i])
                        {
                            maxIndex = i;
                        }
                    }

                    Console.WriteLine(nos[maxIndex]);

                }
            }
            else
            {
                Console.WriteLine("您輸入的不是正整數");
            }

            Console.ReadKey();
        }
    }
}

　　對比我的原始實作，還有現在的兩種新的實作，可以發現。其實原始實作是利用了強大的“存儲結構”Dictionary以及友善的查詢Linq。Dictionary相對于數組占用空間大，畢竟存儲的是Key-Value鍵值對。如果不能google，自己又對Linq不熟的話，怎麼寫出程式呢。其實可以看出針對實習生微軟考的就是基本的資料結構與算法。可見資料結構和算法的重要性。

　　另外若題目限制時間複雜度，可以用原始實作（殺雞用了宰牛刀啊）或者上邊的第二種想法（推薦）。如果限制空間複雜度的話，最好用上邊的兩種想法實作。最後再想想可以不可以先排序再統計呢？用什麼資料結構存儲呢？時間複雜度應該是介于o(n^2)和o(n)之間吧，但是編碼會稍複雜些。

今天的講解就到此，謝謝您的閱讀，下次再見。

如果您覺得這篇部落格對您有所啟發，不妨點選一下右下角的【推薦】按鈕。

如果您對本部落格内容感興趣，請繼續關注我，我是Bull Li。

微軟程式設計一小時--微軟2014實習生招募程式設計模拟測試感想

題目1 : Arithmetic Expression

描述

輸入

輸出

題目2 : Longest Repeated Sequence

繼續閱讀

快速排序非遞歸實作

2015騰訊線上筆試的一道程式設計題

程式設計将二進制IP位址轉換成十進制

嵌入式軟體工程師筆試面試指南-問題答疑（持續更新中）

Java集合面試總結 Java集合面試總結

String類中的compareTo方法總結String類的定義：

排列組合總結組合全排列：

華為筆試題:括号的排列組合

C/Python實作的一道筆試題

校招hr面試必備

面試：atoi() 與 itoa()函數的内部實作

合并兩個已排序的數組為同一個數組

結構體位元組對齊詳解為什麼要對齊？記憶體對齊的三條重要原則

關于IO流的筆試面試題

【leetcode】高頻題目整理_設計篇( High Frequency Problems, Design )相關/參考連結

Java筆試題庫（03期）