我正对一家公司感到非常兴奋,在接受采访的过程中。该职位是针对C#应用程序的初级开发人员。我在现任职位上有一年的经验,在学校期间也有一年的合作社实习。我已经到了最后的面试。对于该过程的一部分,我必须根据以下要求提交程序:


请编写一个程序,该程序每次运行时都会以随机顺序生成10,000个数字的列表。列表中的每个数字都必须是唯一的,并且必须在1到10,000(含)之间。我提交的程序。

这是我提交的程序:

public static class Program
{
    private static Random random = new Random();

    /// <summary>
    /// Shuffles a list of generic objects randomly using the Fisher-Yates algorithm.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list"></param>
    public static void Randomize<T>(this IList<T> list)
    {
        int size = list.Count;
        while (size > 1)
        {                
            size--;
            int index = random.Next(size + 1);
            T value = list[index];
            list[index] = list[size];
            list[size] = value;
        }
    }

    /// <summary>
    /// Asserts uniqueness of a generic list.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list"></param>
    /// <returns></returns>
    public static bool TestUnique<T>(IList<T> list)
    {            
        return list.Distinct().Count() == list.Count();
    }

    /// <summary>
    /// Asserts that a generic list size equals an expected size.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="list"></param>
    /// <param name="count"></param>
    /// <returns></returns>
    public static bool TestCount<T>(IList<T> list, int count)
    {
        return list.Count == count;
    }

    /// <summary>
    /// Asserts that the original list is in a different order.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="original"></param>
    /// <param name="randomized"></param>
    /// <returns></returns>
    public static bool TestOrder<T>(IList<T> original, IList<T> randomized)
    {
        return original != randomized;
    }

    static void Main(string[] args)
    {
        // User starting sequence.
        Console.WriteLine("Welcome to Shuffle. This program is written to randomly shuffle a list.");
        Console.WriteLine("To test, lets shuffle some numbers. Please enter a range of integers you wish to shuffle (Example: 1 - 10000)");

        int min, max;
        bool proceed = true;
        string response;

        do
        {
            do
            {
                // Range is not valid.
                if (!proceed)
                {
                    Console.WriteLine("Invalid range. Please make sure the minimum integer is greater than the maximum integer.");
                }
                // Get the minimum range value.
                Console.Write("\nPlease enter the minimum integer: ");
                // Check if input is an integer.
                while (!int.TryParse(Console.ReadLine(), out min))
                {
                    Console.Write("Invalid input. We are only testing for integers at the moment. Please enter a valid minimum integer: ");
                }
                // Get the minimum range value.
                Console.Write("Please enter the maximum integer: ");
                // Check if input is an integer
                while (!int.TryParse(Console.ReadLine(), out max))
                {
                    Console.Write("Invalid input. We are only testing for integers at the moment. Please enter a valid maximum integer: ");
                }
                // Check if range is valid.        
                proceed = (min < max) ? true : false;
            } while (!proceed);

            Console.WriteLine("Testing shuffle for a range of {0} to {1}...\n", min, max);

            // Create a list.
            List<int> numbers = new List<int>(Enumerable.Range(min, max));

            // Assert list size.
            Debug.Assert(TestCount<int>(numbers, (max - min + 1)));

            // Assert uniqueness.
            Debug.Assert(TestUnique<int>(numbers));

    #if DEBUG
            // Copy original list of numbers only in debug mode.
            List<int> originalNumbers = new List<int>(numbers);
    #endif

            // Randomize the list.
            numbers.Randomize();

            // Re-assert uniqueness.
            Debug.Assert(TestUnique<int>(numbers));

            // Assert random order.
            Debug.Assert(TestOrder(originalNumbers, numbers));

            // Output the list.
            numbers.ForEach(num => Console.Write("[{0}], ", num));

            // User input to re-run test.
            Console.Write("\n\nWould you like to run another test? (y|n): ");

            response = Console.ReadLine();

            while(response.ToLower() != "y" && response.ToLower() != "n")
            {
                Console.Write("Invalid response. Please use 'y' or 'n'. Would you like to run another test? ");
                response = Console.ReadLine();
            }

        } while (response == "y");   

    }
}


我想知道是否有人可以批评我的程序并提出问题他们可能会问我。我不是在寻找答案,我只是想为他们可能问我的一些问题做好准备。

我能想到的一些事情是改善用户界面。与log4net之类的日志记录库集成。

谢谢您的宝贵时间,任何建议或意见将不胜感激。

评论

Random.next(Int32)返回一个从0到max Exclusive的随机数。如果要调用random.Next,大小为1,则对于第一次迭代,很可能在list [10000]处检索值。这种错误是邪恶的,因为它每隔几次便只会失败一次。 ;)

您正在寻找的是随机播放。这是大多数语言中的一行代码。

@BurnsBA:除生成唯一标识符外,请勿将GUID用于其他任何用途。指导不能保证是随机的。不能保证由特别好的熵源生成随机的4类向导。如果您需要随机性,请使用专门设计用于产生随机性的工具,而不是设计用于解决希望完全随机的完全不同的问题的工具。当您拥有一把非常好用的锤子时,就用扳手砸了钉子。

@BurnsBA:给出的答案回答了所提出的问题,即“特定实现是否使用特定实现策略?”答案是“是”。已经有一个关于该问题的评论:“这里的主要问题是您出于不适合其目的而滥用GUID。”这正是我在这里所说的,因此无需重复。

@BurnsBA:总结:guid通常不保证是随机的。不保证随机引导不是顺序的; Guid生成器通过随机选择一个,然后依次给您下一个九个,生成十个“随机” guid是完全合法的。不能保证随机指导是从加密强度随机性源中提取的。指南旨在用于产生独特的价值。使用旨在解决您所遇到问题的工具;如果您需要随机字符串,请编写一个随机字符串生成器。

#1 楼

一般而言,首先,最重要的是,要求您制作一个程序,该程序以随机​​顺序生成10,000个数字的列表。您增加了太多的复杂性。不需要输入或输出(最终输出除外)。对程序进行严重的过度架构并不是一个好的立即印象。我期望有几行代码(5-10),并带有一些可选测试。


我能想到的一些事情是改善用户界面。与log4net之类的日志记录库集成。


这会给我留下非常不好的印象。这里不需要接口,也没有理由为这样一个简单的应用程序包含日志记录库。

我想要的是简单明了的东西。像这样的东西就足够了:

private static List<int> CreateRandomList(int listSize)
{
    // ...
}
private static void PrintList(IList<int> lst) 
{
    // ...
}

public static void Main(string[] args) 
{
    const int listSize = 10000;
    var randomList = CreateRandomList(listSize);

    Debug.Assert(randomList.Length == listSize);
    Debug.Assert(randomList.Distinct().Count() == randomList.Count);

    PrintList(randomList);
}



TestOrder不会做您期望的事情。它正在测试参考相等性。这将始终传递您的代码,因为您要提供两个不同的列表。此外,以相同顺序具有相同项目的两个不同列表将返回true。更好的实现可能是!order.SequenceEqual(randomized)。但是,进行随机性测试本质上是有缺陷的,对于随机排序返回相同的输入完全有效。

加分点

我不希望初级开发人员(或即使是任何刚接触C#的开发人员也可以了解该语言和库的所有细节,但是如果这样做的话,肯定会受到青睐。完整的实现可能非常简洁,例如:

void Main()
{
    const int listSize = 10000;
    var rnd = new Random();
    var randomList = Enumerable.Range(1, listSize).OrderBy(e => rnd.Next()).ToList();

    // These are not needed, we can be confident the core libraries are not broken
    Debug.Assert(randomList.Count == listSize);                      
    Debug.Assert(randomList.Distinct().Count() == randomList.Count);

    var listOutput = string.Join(", ", randomList);
    Console.WriteLine(listOutput);
}


评论


\ $ \ begingroup \ $
评论不用于扩展讨论;此对话已移至聊天。
\ $ \ endgroup \ $
– Mathieu Guindon♦
17年7月7日在11:09

\ $ \ begingroup \ $
令人讨厌-这里的一些讨论很有用
\ $ \ endgroup \ $
– Alnitak
17年6月7日13:50

#2 楼

文档和注释

这是我的个人喜好,但对我而言,没有内容的xml注释是不必要的。例如,<returns></returns>几乎不告诉我有关返回类型或正在返回的内容等的信息。

如其他答案注释中所述:

// Get the minimum range value.
Console.Write("\nPlease enter the minimum integer: ");


由于它们几乎没有意义而没有任何帮助

命名

您写的是这样的:

// Range is not valid.
if (!proceed)


如何将proceed更改为rangeIsValid,然后就不需要任何注释了。自我记录代码是最宝贵的代码,在使用了几年程序后,您有时可能会看到贬值的注释,因为开发人员懒得只写注释但不考虑名称。

代码划分

我认为您应该对代码进行划分,这将提高可读性并使其更易于维护。


我认为您应该做的是将扩展方法放在另一个类甚至命名空间中。
划分逻辑。将所有方法都带到另一个类(甚至另一个项目)中-这样更干净。最好的方法(我认为)是创建三个项目:1.主控制台应用程序2.测试项目(在第一个测试中进行所有测试时并不需要)3.具有主逻辑的库项目。

有人可能会说这是一个矫kill过正,但是,即使涉及到如此小的应用程序,我也确实将关注点分离了。

规格

我我还想尽可能地指定泛型,因此您不在算法中使用IList,那么为什么在测试方法中使用它呢?我不知道是否有任何C#约定,但这可以帮助其他开发人员理解代码。

评论


\ $ \ begingroup \ $
与您的“文档和注释”部分相关,看来注释已经与代码不同步:获取最大值的注释具有错误的注释。我同意这个答案:尽可能使用自记录代码,这样您就不必写不可避免地与这样不同步的注释。
\ $ \ endgroup \ $
– theosza
17年5月5日在9:28

#3 楼

由于这是用于讨论的面试代码,因此我将把答案作为一组开放式讨论问题。
“您如何将其整合到更大的程序中?”
这很简单-大多数程序的代码位于测试工具中,您应该能够提取Randomize()并将其在其他地方使用。您可能需要谈论如何记录前置条件和后置条件(例如,讨论就地改组和返回改组后的副本之间的区别)。
“很小的范围会发生什么?”
测试程序时,应始终关注边缘情况。因此,考虑仅用一个元素对列表进行混洗,并跟踪发生了什么。如果您的TestOrder()按照广告宣传工作,那么它将拒绝唯一有效的随机播放。
您需要更改输入验证还是输出验证?为什么? (回答此问题将需要您考虑如何调用代码)。
“真正的大范围呢?”
您将要讨论性能如何随元素数量而扩展增加,并且可能涉及不同的接口(您可以考虑将一个元素一次接口作为存储整个列表的替代方法-您将如何实现?)。
“您将如何再现特定的随机播放?”
假设我正在调试一些使用此随机混洗的代码。有时,我的代码产生错误的输出,并且我怀疑它与改组有关。我是否可以播种随机混洗,以便一旦发现有问题的混洗,就可以一次又一次地使用相同的混洗,直到诊断出问题为止?需要进行哪些更改?
“为什么要创建通用方法?”
该要求要求对10000个小整数进行改组。通用方法可能有用,但是您还能谈谈它的缺点吗?软件是一门工程学科,这是一个讨论您如何在工作中做出成本/收益决策的机会。

最后
您在寻求面试中的要求时已寻求帮助。这种准备工作可能对您的面试官很明显(您应该对自己的准备工作诚实)。讨论一些代码的部分目的是要看您是如何“当场”推理的,因此不要指望一切。
如果您准备不足,那么好的面试官可能会停止讨论此代码,然后切换到您可能没有准备的不相关的编程问题。这不仅是为了给您增加困难,还在于让您有机会展示自己的思想和沟通方式。

#4 楼

我看到了精心制作的代码和对细节的关注。
我认为您在良好的轨道上,请继续努力。

程序组织

会更好将实现划分为多个类,例如:根据问题描述,一个类将成为主要的可执行文件:随机生成10,000个数字的列表。我将其设为控制台应用程序,最大数量作为命令行参数,默认情况下为10000。
用于实现主要任务的实用程序类,将由主要可执行文件使用
将测试实现为适当的NUnit测试

我在规范中没有提到将交互式命令行界面作为您实现的界面。
您添加了它很好,但是我认为奖金。
我会添加为另一个命令行应用程序。

删除琐碎的注释

这些注释没有用,因为它们仅说明已经很明显的内容:


// Get the minimum range value.
Console.Write("\nPlease enter the minimum integer: ");
// Check if input is an integer.
while (!int.TryParse(Console.ReadLine(), out min))
{
    Console.Write("Invalid input. We are only testing for integers at the moment. Please enter a valid minimum integer: ");
}
// Get the minimum range value.
Console.Write("Please enter the maximum integer: ");



我还没有阅读所有评论,但我敢保证大多数评论都是相似的。
避免这样的评论。

直接使用布尔表达式

不需要此三进制:


proceed = (min < max) ? true : false;



您可以直接分配布尔表达式:

proceed = min < max;


#5 楼

我会从字面上考虑这个问题,这意味着如果它只是说


编写一个程序,该程序生成10,000个数字的列表


不要麻烦编写控制台或Winforms或WPF应用程序。您应该编写一个程序,而库也是一个程序。编写完整的应用程序只会浪费您的时间,而且您做错了我的事情。

而是只专注于实际算法并验证其结果。编写一个解决问题的类,并进行一些测试以证明其有效。就这样。

你知道KISS原则吗?不要做没有被要求做的事情,除非您对正在做的事情有足够的信心,并且想要展示更多然后被问到的事情。

评论


\ $ \ begingroup \ $
您对时间的花费是正确的,并且可能会增加复杂性,最终可能会花费您大量的时间,但是对于程序的定义,我会小心谨慎。通常,库不被视为程序,它是一个元素。也许最好将算法设计为一个库,然后构建一个实现该库的简单控制台或GUI程序,从而覆盖您的所有基础。
\ $ \ endgroup \ $
– Flatlyn
17年5月5日在1:37

\ $ \ begingroup \ $
@theJamesKrawczyk根据免费词典:1.计算机程序-(计算机科学)计算机可以解释和执行的一系列指令;这就是为什么它被称为“编程而不是应用程序”或其他原因,因为您编写的程序是计算机可以解释和执行的任何程序,例如脚本,函数,库或单元测试;-)
\ $ \ endgroup \ $
–t3chb0t
17-6-5在6:45



\ $ \ begingroup \ $
关于“这就是为什么被称为”的问题:不。在任何人谈论库或应用程序的十年前,它就被称为编程。因此,不将其称为库或应用程序不是故意的选择。自从出现语义漂移的72年以来。
\ $ \ endgroup \ $
– Peter Taylor
17年5月5日在9:53

\ $ \ begingroup \ $
@ t3chb0t您对程序的字典定义是正确的,但是当雇主或客户要求“编写程序”时,上下文用法通常会被接受来产生它们可以运行和使用的东西,而不是可以合并到他们可以运行和使用的东西中的代码块,需要进一步开发。如果他们只想要建立一个程序库,而不是开始时略有错误,则可能只建立一个库,而不是建立一个程序所需要的程序,最终会损失更多的分数。正如我所说的,最好同时做这两个工作-一个带有逻辑库的程序。
\ $ \ endgroup \ $
– Flatlyn
17年5月5日在10:44

\ $ \ begingroup \ $
@JamesKrawczyk,我要说的是,除非接受采访时明确要求您提供某种GUI,否则单元测试将比您想出的任何控制台应用程序更好地“销售”您。
\ $ \ endgroup \ $
– Nikita B
17-6-5在10:54



#6 楼

[复杂度]
尽管显示了一些长期思考,但复杂性可能对于任务来说太高。
从长远来看,提供一些灵活性(用变量代替硬编码可能很有用)数字)。
我很喜欢使用模板参数和扩展方法的长期思路。

[如果需要测试]
因为“ TestCount <>()”只能从一个位置调用,您可以将其删除并使用

Debug.Assert(numbers.Count.Equals((max - min) + 1));


内联发布测试。某些测试代码可以分为一个测试项目。
这将告诉您如何使用Test Suite并消除代码中的混乱情况。
还可以在不影响原始代码的情况下对测试进行更改。
这可能还需要您将代码分隔开以使其可以独立测试。

[关注点分离]
正如其他人提到的那样,将“引擎” /算法与用户界面分开将使您能够重用那个阿尔戈里其他类型的程序。可以将其放在单独的DLL中,并使用其他.NET兼容语言从项目中调用。
不允许生成数字的例程显示。

[初始化所有变量]
我使用多种语言编写代码,并出于以下几个原因对所有变量进行了初始化:
1)我不想记住特定的语言默认值。
2)它最大程度地减少了意外和副作用(即使在调试过程中也是如此)。

这是一种将算法与接口分离的技术。
确保数字在返回之前被用尽。
/>类似的东西可以用来允许开发人员在不绑定到控制台的情况下使用其他项目类型的代码。
//非线程化

using System;
using System.Collections.Generic;
using System.Linq;

namespace GenRandom
{
   class Program
   {
      /// <summary>
      /// This method fills a list of integers with unique random numbers based
      /// on the intDepth variable.
      /// </summary>
      /// <param name="intDepth">How many numbers to generate</param>
      /// <param name="lst_intOutput">List of integers as output</param>
      public static void GenerateNumbers(int intDepth, List<int> lst_intOutput)
      {
         Dictionary<int, bool> map_int2blnSource =
            Enumerable.Range(0, intDepth).Select(i => new KeyValuePair<int, bool>(i, false))
            .ToDictionary(k => k.Key, v => v.Value);

         Random ran = new Random();
         while (map_int2blnSource.Any(kvp => !kvp.Value))
         {
            // generate random and ensure uniqueness before returning.
            int intCurrent = ran.Next(0, intDepth);
            if (!map_int2blnSource[intCurrent])
            {
               lst_intOutput.Add((intCurrent + 1));
               map_int2blnSource[intCurrent] = true;
            }
         }
      }

      /// <summary>
      /// Only shown for explanation
      /// This could be any .NET compatible language calling the algorithm.
      /// </summary>
      /// <param name="args">First/only param is the high number.</param>
      static void Main(string[] args)
      {
         int intDepth = 0;
         if (!int.TryParse(args.FirstOrDefault(), out intDepth))
         {
            Console.WriteLine("GenRandom n\r\nwhere n is the top number.");
            return;
         }

         Console.WriteLine("Generating...");
         List<int> lst_intResult = new List<int>(intDepth);
         GenerateNumbers(intDepth, lst_intResult);

         Console.WriteLine(string.Join(Environment.NewLine, lst_intResult));
      }
   }
}


#7 楼

OP中的解决方案似乎对于一个(似乎是?)简单问题有点过头。正如t3chb0t已经指出的那样,请尽可能使其简单。考虑到@JamesK的评论,这个问题似乎只是筛选测试,目的是淘汰以前从未编写过程序的人。在这种情况下,一个简单而简洁的解决方案应该足以通过。

直接方法是用满足给定条件的随机数填充无序集合,直到达到适当的数量。 >
以下是一些C ++代码,展示了上述方法。

#include <iostream>
#include <unordered_set>

int main()
{
    const size_t min = 1;
    const size_t max = 10000;

    std::unordered_set<size_t> set;

    while (set.size() < 10000)
    {
        set.emplace(min + (rand() % static_cast<int>(max - min + 1)));
    }
}


评论


\ $ \ begingroup \ $
@tinstaafl C ++侦听器更像答案中概述的方法的概念证明。这里的重点是可以用比OP中显示的代码少得多的代码来解决此问题。我只是想知道为什么。
\ $ \ endgroup \ $
– yuri
17-6-4在23:22



\ $ \ begingroup \ $
包含的内容超出了您的需要(例如静态构造的流对象)。 std :: size_t仅需要。不要使用rand()(请参阅:兰德被认为是有害的)。您定义最大值,但在循环条件中使用其值。最后,当您在该范围内插入更多值时,生成唯一值的可能性降低。而是先生成完整的值范围,然后再随机播放。
\ $ \ endgroup \ $
–雪鹰
17-6-5在0:41



\ $ \ begingroup \ $
另外,您对std :: unordered_set的使用会丢弃插入的“随机”顺序。
\ $ \ endgroup \ $
–雪鹰
17年6月5日在0:50



\ $ \ begingroup \ $
虽然我同意可以使任务的解决方案比OP提供的解决方案简单得多,但不幸的是,这个答案与OP的要求并不相符,因为结果列表不是随机排列的,而是由unordered_set的实现定义的订单。
\ $ \ endgroup \ $
– theosza
17年5月5日在9:36

\ $ \ begingroup \ $
@yuri哈希表有完全合理的实现,其中输出顺序取决于值的哈希,而不是值的插入顺序。由于标识函数是整数的很好的哈希,这意味着要有一个很好的排序输出。仅仅因为您测试的实现没有表现出这种行为,并不意味着就没有其他符合标准的实现。因此,此答案依赖于实现细节,这些细节在标准库的不同实现甚至同一库的不同版本之间可能有所不同。
\ $ \ endgroup \ $
– CodesInChaos
17年5月5日在22:18

#8 楼

您不需要将位置0随机播放
同样可以是有效的随机播放-可能像任何随机播放一样随机播放

private static Random randFY = new Random();
public static void FisherYatesShuffle(ref List<int> Deck)
{
    //FishYate in place shuffle
    int swap;
    int temp;
    for (int i = Deck.Count - 1; i > 0; i--)
    {
        swap = randFY.Next(i + 1);  //.net rand is not inclusive
        if (swap != i)
        {
            temp = Deck[i];
            Deck[i] = Deck[swap];
            Deck[swap] = temp;
        }
    }
}


#9 楼

只需创建具有10000个数字的整数列表,然后将其洗牌即可:)

甚至可以存储该列表。这样,下面的执行将只进行混洗而不是生成列表和混洗。

评论


\ $ \ begingroup \ $
欢迎使用代码审查!您提出了一个替代解决方案(实际上是相同的解决方案),但是还没有审查代码。请说明您的推理(您的解决方案如何工作以及如何对原始解决方案进行改进),以便作者可以从您的思考过程中学习。
\ $ \ endgroup \ $
– Toby Speight
17年6月6日在15:24