为了接触体验微软实习生编程题目，上个月底报了微软探星秋令营活动。报名地址。其实我还是比较了解自己的实力，对于结果没有报太大的希望。不过在这次模拟测试的过程中积累了一小点经验，希望大家以后别犯同样的错误。

模拟测试考核方式

　　参加考核的前提条件是必须在上边贴出的网址中，申请相应的职位，填写自己的简历。2014“智在未来”暑期实习项目，“微软探星探星秋令营”非暑期实习生的网申截止期限均为2014年3月31日。MACH暑期实习生的网申截止期限为2014年4月18日。具体大家参考官网说明。我是在3月30日申请的职位，4月4日下午3点收到的通知邮件。邮件内容如下：

 

图1

　　接着进入模拟测试地址，注册登录即可。从上可以测试平台不限制语言，支持C、C++、C#和JAVA。

 

图2

　　接着点击微软编程一小时，查看编程须知，具体内容大家自己看吧。贴出来图片太大。那么怎么提交自己的代码呢？

 

图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.

样例输入

4901 / 1003 * 32 + 68 - -1

样例输出

2

题目2 : Longest Repeated Sequence

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

You are given a sequence of integers, A = a₁, a₂, ... a_n. A consecutive subsequence of A (say a_i, a_i+1 ... a_j) is called a "repeated sequence" if it appears more than once in A (there exists some positive k that a_i+k = a_i, a_i+k+1 = a_i+1, ... a_j+k = a_j) 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, a₁ a₂ ... a_n (0 <= a_i <= 100).

输出

The length of the longest repeated sequence.

样例输入

52 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
     
       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
     
       dic = new Dictionary
      
       ();                    foreach (string oStr in nos)                    {                        if (dic.ContainsKey(oStr))                        {                            dic[oStr]++;                        }                        else                        {                            dic[oStr] = 1;                        }                    }                    Dictionary
       
         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平台下的Mono。然后利用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。