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

【第一题】一共有二十五匹马，五个赛道，每个赛道每次只能跑一匹马。问：最少多少次能选出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;
        static List<string> dataSource = new List<string>(); 
        string> results = string>();
        static Hashtable dataHst = new Hashtable();
        int maxCount;
        static Object obj = new Object();
        string theLock = "I'm a lock";
        static DateTime startTime;
        static DateTime endTime;
        //Use the concurrent collection to store results.
        static ConcurrentDictionary<string,int> dataDic = new ConcurrentDictionary<int>();

        void Main(string[] args)
        {
            CreateData();
            SolveData(Solve the data normally:",SolveDataNormally,FindResultsFromHst);
            SolveData(Solve the data concurrently:Solve the data using concurrent collection:private 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());
        }

        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;
        }

        string> FindResultsFromDic()
        {
            Find the results from dataDic. 
            maxCount = 0;
            results.Clear();
            Parallel.ForEach(dataDic.Values.Cast<
            {
                lock (obj)
                {
                    if (value > maxCount)
                    {
                        maxCount = value;
                    }
                }
            });
            var data in dataDic)
            {
                if (data.Value == maxCount)
                {
                    results.Add(data.Key);
                }
            }
            void CreateData()
        {
            Random ran = new Random();
            Parallel.For(0,5000000,i =>
            {
                lock (dataSource)
                {
                    data = { id = 'xxx' info = 'xxx' kk = 'xxx' target = '" + ran.Next(1,128); line-height:1.5!important">200) + ' dd = 'xxx'}";
                    dataSource.Add(data);
                }
            });
            Console.WriteLine(dataSource.Count +  data has been created.");
        }

        void SolveDataNormally()
        {
            dataHst.Clear();
            int num;
            string data in dataSource)
            {  
                if (!dataHst.Contains(data.Split()[12]))
                {
                    dataHst.Add(data.Split()[12],128); line-height:1.5!important">1);
                }
                else
                {
                    num = int.Parse(dataHst[data.Split()[12]].ToString());
                    num += 1;
                    dataHst[data.Split()[12]] = num;
                }
            }
        }

        void SolveDataParallel()
        {
            dataHst.Clear();
            int num;
            Parallel.ForEach(dataSource,data =>
            {
                lock (dataHst)
                {
                    12]))
                    {
                        dataHst.Add(data.Split()[1);
                    }
                    else
                    {
                        num = 12]].ToString());
                        num += 1;
                        dataHst[data.Split()[12]] = num;
                    }
                }
            });
        }

        void SolveDataConcurrently()
        {
            dataDic.Clear();
            Parallel.ForEach(dataSource,255); line-height:1.5!important">if (!dataDic.ContainsKey(data.Split()[12]))
                    {
                        dataDic.TryAdd(data.Split()[else
                    {
                        dataDic[data.Split()[12]]++;
                    }
                }
            });
        }
    }
}

运行结果如下：

?

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

12]))
{
      dataHst.Add(data.Split()[1);
}

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

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