两道关于数据处理方面的面试题

无私分享两道百度作业帮的测试开发面试题！整理不易，请给赞~

【第一题】一共有二十五匹马，五个赛道，每个赛道每次只能跑一匹马。问：最少多少次能选出3匹最快的马？（不能记录每匹马跑完全程所用的时间，只能通过比较谁先到达终点来判断两匹马的孰快孰慢）

思路如下：

1、 前五次 ：25匹马，分成5组，每组赛1次，共赛5次——这样就能得出5匹马（各组的第一）;

2、 第六次 ：让这五匹马赛一次，取前3，淘汰这五匹第一马中的第四和第五（假设是第四组第一和第五族第一），比这两匹马慢的也都淘汰，共淘汰10匹马（第四组和第五组所有马）。

3、剩下的15匹马（第一组、第二组、第三组），因为取前3，所以淘汰每一组中的第四和第五，共淘汰6匹马。

4、现在还剩下9匹马，他们是：

因为第六次比赛的时候已经得出了各组第一马的快慢顺序。假设马的速度——第一组第一>第二组第一>第三组第一。则第一组第一是最快的，所以这匹马无需再比，它就是 第一快的 。

剩下的八匹马中：

第二组第一、第一组第二，他们俩需要比一次，看看谁是 第二快的 。

第三组第三、第二组第二、第三组第一，他们仨需要比一次，看看谁是 第三快的 。

这五匹马正好占五个赛道，比一次，也就是 第七次 。

所以得出答案：至少需七次比赛，才能选出最快的三匹马。

【第二题】假设一小时内接口共返回500万条数据，数据假设为{id='xxx' info='xxx' kk='xxx' target='' dd='xxx'}这种格式，不同的字段名和字段值间用空格隔开。问：怎么得出target字段返回次数最多的值。

我的思路：先按空格切割字符串，把范围锁定在target字段的值域，把值域存到数组中。然后对数组进行一次去重和计数并保存到一个数据结构中，最后从这个数据结构中找出计数最多的分类，也就是target字段返回次数最多的值。

我的解法如下，分别用了三种方法（正常法、非线程安全集合的并发法、线程安全集合的并发法）：

 using System; using System.Collections; using System.Collections.Concurrent; using System.Collections.Generic; using System.Linq; using System.Threading.Tasks;  namespace FuckThatPussy {     class Program     {         public static string data;         public static List<string> dataSource = new List<string>();          public static List<string> results = new List<string>();         public static Hashtable dataHst = new Hashtable();         public static int maxCount;         public static Object obj = new Object();         public static string theLock = "I'm a lock";         public static DateTime startTime;         public static DateTime endTime;         //Use the concurrent collection to store results.         public static ConcurrentDictionary<string, int> dataDic = new ConcurrentDictionary<string, int>();          static void Main(string[] args)         {             CreateData();             SolveData("Solve the data normally:", SolveDataNormally, FindResultsFromHst);             SolveData("Solve the data concurrently:", SolveDataParallel, FindResultsFromHst);             SolveData("Solve the data using concurrent collection:", SolveDataConcurrently, FindResultsFromDic);             Console.Read();         }          private static void SolveData(string v, Action solveDataMethod, Func<List<string>> findResults)         {             Console.WriteLine(v);             startTime = DateTime.Now;             solveDataMethod.Invoke();             endTime = DateTime.Now;             foreach (var result in findResults.Invoke())             {                 Console.WriteLine(result + " " + maxCount);             }             Console.WriteLine("Time use: " + (endTime - startTime).ToString());         }          private static List<string> FindResultsFromHst()         {             //Find the results from dataHst.              maxCount = 0;             results.Clear();             Parallel.ForEach(dataHst.Values.Cast<int>(), value =>              {                  lock (obj)                  {                      if (value > maxCount)                      {                          maxCount = value;                      }                  }              });             //foreach (int value in dataHst.Values)             //{             //    if (value > maxCount)             //    {             //        maxCount = value;             //    }             //}             IDictionaryEnumerator item = dataHst.GetEnumerator();             while (item.MoveNext())             {                 if (int.Parse(item.Value.ToString()) == maxCount)                 {                     results.Add(item.Key.ToString());                 }             }             return results;         }          private static List<string> FindResultsFromDic()         {             //Find the results from dataDic.              maxCount = 0;             results.Clear();             Parallel.ForEach(dataDic.Values.Cast<int>(), value =>             {                 lock (obj)                 {                     if (value > maxCount)                     {                         maxCount = value;                     }                 }             });             foreach (var data in dataDic)             {                 if (data.Value == maxCount)                 {                     results.Add(data.Key);                 }             }             return results;         }          private static void CreateData()         {             Random ran = new Random();             Parallel.For(0, 5000000, i =>             {                 lock (dataSource)                 {                     data = "{ id = 'xxx' info = 'xxx' kk = 'xxx' target = '" + ran.Next(1, 200) + "' dd = 'xxx'}";                     dataSource.Add(data);                 }             });             Console.WriteLine(dataSource.Count + " data has been created.");         }          public static void SolveDataNormally()         {             dataHst.Clear();             int num;             foreach (string data in dataSource)             {                   if (!dataHst.Contains(data.Split()[12]))                 {                     dataHst.Add(data.Split()[12], 1);                 }                 else                 {                     num = int.Parse(dataHst[data.Split()[12]].ToString());                     num += 1;                     dataHst[data.Split()[12]] = num;                 }             }         }          public static void SolveDataParallel()         {             dataHst.Clear();             int num;             Parallel.ForEach(dataSource, data =>             {                 lock (dataHst)                 {                     if (!dataHst.Contains(data.Split()[12]))                     {                         dataHst.Add(data.Split()[12], 1);                     }                     else                     {                         num = int.Parse(dataHst[data.Split()[12]].ToString());                         num += 1;                         dataHst[data.Split()[12]] = num;                     }                 }             });         }          private static void SolveDataConcurrently()         {             dataDic.Clear();             Parallel.ForEach(dataSource, data =>             {                 lock (obj)                 {                     if (!dataDic.ContainsKey(data.Split()[12]))                     {                         dataDic.TryAdd(data.Split()[12], 1);                     }                     else                     {                         dataDic[data.Split()[12]]++;                     }                 }             });         }     } } 

运行结果如下：

可以看出用C#的线程安全集合是最快的，自己手动加lock做并发的时间比普通的foreach还要慢。因为并发的时候会有判断，判断集合中是否会有相应的元素，如果没有则进行初始化，这里如果不加lock的话将会有并发初始化的事情发生，这样得到的结果值就会比预期结果低。下面是初始化部分的代码：

 if (!dataHst.Contains(data.Split()[12])) {       dataHst.Add(data.Split()[12], 1); } 

目前我没想到什么好的办法可以摘掉锁，因为摘到锁就做不到线程安全了，据我测试线程安全集合类 ConcurrentDictionary <TKey, TValue> 的TryAdd方法在并发的情况下是不安全的，如果并发字典中不存在我们TryAdd的数据，此时如果并发多个TryAdd方法，TryAdd的返回值均为true，所以还是会导致并发初始化的发生，是不安全的。如果可以摘掉这层锁，时间可以提升一倍，处理500万条数据仅需7秒左右。

各位前辈、大神如果有好的思路和解法，欢迎贴出来代码让我们也一起学习。