为了接触体验微软实习生编程题目，上个月底报了微软探星秋令营活动。报名地址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.
- 样例输入
4 901 / 100 3 * 3 2 + 6 8 - -1
样例输出
2
题目2 : Longest Repeated Sequence
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
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();
}
}
}
在VS中运行结果截图：
图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。
转载于:https://www.cnblogs.com/Jack-hui/p/3650827.html