為了接觸體驗微軟實習生程式設計題目,上個月底報了微軟探星秋令營活動。報名位址http://campus.chinahr.com/2014/pages/msfte/ch/RecruitingEvent.asp。其實我還是比較了解自己的實力,對于結果沒有報太大的希望。不過在這次模拟測試的過程中積累了一小點經驗,希望大家以後别犯同樣的錯誤。
模拟測試考核方式
參加考核的前提條件是必須在上邊貼出的網址中,申請相應的職位,填寫自己的履歷。2014“智在未來”暑期實習項目,“微軟探星探星秋令營”非暑期實習生的網申截止期限均為2014年3月31日。MACH暑期實習生的網申截止期限為2014年4月18日。具體大家參考官網說明。我是在3月30日申請的職位,4月4日下午3點收到的通知郵件。郵件内容如下:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiInBnauADOygzMwQjN1UTM5EDOw8CX0ADNxAjMvwlM1UTMwQzLcd2bsJ2Lc12bj5ycn9Gbi52YuAzcldWYtl2Lc9CX6MHc0RHaiojIsJye.jpg)
圖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.
- 樣例輸入
4
901 / 100
3 * 3
2 + 6
8 - -1
樣例輸出
2
題目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
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。