27
\$\begingroup\$

I am in the middle of an interview process with a company I am very excited about. The position is for a Junior Developer for C# applications. I have a year of experience at my current position as well as a year of co-op placements while in school. I have made it to the final interview. For one part of the process I had to submit a program based on the following requirements:

Please write a program that generates a list of 10,000 numbers in random order each time it is run. Each number in the list must be unique and be between 1 and 10,000 (inclusive).

The HR manager let me know that in the final interview developers would be asking me questions related to the program that I submitted.

Here is the program I submitted:

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");   

    }
}

I was wondering if anyone could critique my program and submit questions that they may ask me in regards to it. I am not looking for the answers, I just want to be prepared for some questions they may ask me.

Some of the things I could think of would be to improve the user interface. Integrate with a logging library like log4net.

Thanks for your time and any suggestions or submissions would be greatly appreciated.

\$\endgroup\$
  • 3
    \$\begingroup\$ Random.next(Int32) returns a random number from 0 to max exclusive. If you're calling random.Next with size + 1, then for the first iteration, there is the remote possibility of retrieving value at list[10000]. This kind of bug is evil because it fails only once every so often. ;) \$\endgroup\$ – Neil Jun 5 '17 at 10:39
  • 5
    \$\begingroup\$ what you're looking for is a shuffle. it's one line of code in most languages. \$\endgroup\$ – Fattie Jun 5 '17 at 12:59
  • 4
    \$\begingroup\$ @BurnsBA: Never use a GUID for anything other than generating a unique identifier. Guids are not guaranteed to be random. Type 4 guids, which are random, are not guaranteed to be generated by a particularly good source of entropy. If you need randomness then use a tool specifically designed to generate randomness, not a tool designed to solve a completely different problem that you hope is random. You're hitting a nail with a wrench when you have a perfectly good hammer handy. \$\endgroup\$ – Eric Lippert Jun 5 '17 at 17:57
  • 2
    \$\begingroup\$ @BurnsBA: The given answer answers the question that was asked, which is "does a particular implementation use a particular implementation strategy?" and the answer is "yes". There already is a comment on the question: "The main issue here is your misappropriation of GUIDs for a purpose for which they are not fit." which is precisely what I am saying here, so there's no need for me to repeat it. \$\endgroup\$ – Eric Lippert Jun 5 '17 at 18:28
  • 2
    \$\begingroup\$ @BurnsBA: Summing up: guids are not in general guaranteed to be random. Random guids are not guaranteed to be not sequential; it is perfectly legal for a guid generator to generate ten "random" guids by picking one at random and then giving you the next nine sequentially. Random guids are not guaranteed to be drawn from a crypto strength randomness source. Guids are intended to be used to produce a unique value. Use tools designed to solve the problem that you have; if you need random strings then write a random string generator. \$\endgroup\$ – Eric Lippert Jun 5 '17 at 18:31
30
\$\begingroup\$

In general

First and foremost, you were asked to produce a program that generates a list of 10,000 numbers in random orders. You've added far too much complexity. There's no need for input or output (other than the final output). It's not a good immediate impression to heavily over-architect the program. I would be expecting a few lines of code (5-10), with some optional tests.

Some of the things I could think of would be to improve the user interface. Integrate with a logging library like log4net.

This would leave a very bad impression in my eyes. There's no interface required here, and there's no reason to include a logging library for such a simple application.

What I would be looking for would be something simple and to the point. Something like this would be sufficient:

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

Bugs

TestOrder isn't going to do what you expect. It's testing for reference equality. This will always pass in your code, since you're providing it two different lists. Further, two different lists with the same items in the same order will return true. A better implementation might be !order.SequenceEqual(randomized). However, testing for randomness is inherently flawed, it's entirely valid for a random sort to return the same input.

Bonus points

I wouldn't expect a junior developer (or even any developer new to C#) to know all the ins and outs of the language and libraries, but it would certainly be looked upon favourably if they did. The full implementation can be very succinct, for example:

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);
}
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Mathieu Guindon Jun 7 '17 at 11:09
  • 2
    \$\begingroup\$ that's annoying - some of the discussion here was useful \$\endgroup\$ – Alnitak Jun 7 '17 at 13:50
12
\$\begingroup\$

Docs and comments

This is my personal preference but for me a xml comments with no content are not necessary. For example <returns></returns> tells me virtually nothing about returning type or what is being returned etc.

As stated in other answer comments like this:

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

are not helpful in any way because of their little to no importance

Naming

You wrote this :

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

How about changing proceed to rangeIsValid and then you would not need any comment. Self documenting code is most precious one, after a few years of program life you sometimes might see depreciated comments because developers were lazy enough just to write comment but not think about names.

Code devision

In my opinion you should divide your code, it will improve readability and can make it more maintainable.

  • What I think you should do is put extension methods in another class or even namespace.
  • Divide logic. Get all your methods to another class (or even another project) - it is cleaner that way. The best way (in my opinion) would be to create three projects: 1. Main console application 2. Test project (not really needed when you do all your tests in first one) 3. Library project with main logic.

Some might say that it is an overkill but I really do separation of concerns if it comes to even so small applications.

Specifications

I also like to specify generics as much as I can, you do not use IList in your algorithm then why do you use it in your test methods then? I have no idea if there is any C# convention about it but this is something that helps another developers to understeand the code.

\$\endgroup\$
  • \$\begingroup\$ Related to your section on Docs and Comments, it looks like the comments are already out of sync with the code: the comment for getting the maximum value has the wrong comment. I agree with this answer: use self-documenting code as much possible so you don't have to write comments that inevitably go out of sync like this. \$\endgroup\$ – theosza Jun 5 '17 at 9:28
12
\$\begingroup\$

As this is interview code for discussion, I'll frame my answer as a set of open-ended discussion questions.

"How would you incorporate this into a bigger program?"

This one's fairly easy - most of your program is in the test harness, and you should be able to extract Randomize() and use it elsewhere. You'll probably want to talk about how you document the pre- and post- conditions (e.g. talk about the difference between shuffling in-place and returning a shuffled copy).

"What happens with very small ranges?"

When we test our programs, we should always look at the edge cases. So consider a shuffle of a list with just one element, and trace what happens. If your TestOrder() worked as advertised, then it would reject the only valid shuffle.

Do you need to change your input validation, or your output validation? Why? (Answering this question will require you to think about how your code will be called).

"What about really big ranges?"

You'll want to talk about how the performance scales as the number of elements increases, and perhaps about different interfaces (you could consider an element-at-a-time interface as an alternative to storing the entire list - how would you implement that?).

"How would you reproduce specific shuffles?"

Suppose I was debugging some code that used this random shuffle. Sometimes, my code produces wrong output, and I suspect it's related to the shuffle. Would I be able to seed the random shuffle so that once I've found a problematic shuffle, I can use the same one again and again until I've diagnosed the problem? What changes would need to be made?

"Why did you make a generic method?"

The requirement asked for a shuffle of 10000 small integers. A generic method might be useful, but can you talk about its drawbacks too? Software is an engineering discipline, and this is an opportunity to talk about how you make cost/benefit decisions in your work.


Finally

You've asked for help in anticipating what you'll be asked in interview. This kind of preparation will likely be evident to your interviewer (and you should be honest about your preparation). Part of the point of having some code to discuss is to see how you reason about it "on the spot", so don't expect to anticipate everything.

If you're over-prepared, a good interviewer may well stop discussing this code, and switch to an unrelated programming problem you can't possibly have prepared for. That isn't intended simply to make it difficult for you - it's to give you an opportunity to show how you think and communicate.

\$\endgroup\$
11
\$\begingroup\$

I see carefully crafted code and attention to detail. I think you're on a good track, keep it up.

Program organization

It would be better to split the implementation to multiple classes, for example:

  • A class to be the main executable as per the problem description: generate a list of 10,000 numbers in random order. I would make this a console application, with the maximum number as command line argument, or 10000 by default.
  • A utility class to implement the main task, that will be used by the main executable
  • A class to implement tests as proper NUnit tests

I don't see in the specification mention about an interactive command line interface as the one you implemented. It's nice that you added that, but I consider it a bonus. I would have added as another command line application.

Remove trivial comments

These comments are not useful, as they only state what's already obvious:

// 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: ");

I haven't read all the comments, I bet that most of them are similar. Avoid such comments.

Use boolean expressions directly

No need for this ternary:

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

You can assign the boolean expression directly:

proceed = min < max;
\$\endgroup\$
8
\$\begingroup\$

I'd take the question literally this means if it just says

write a program that generates a list of 10,000 numbers

don't bother writing a console or winforms or a wpf application. You should write a program and a library is also a program. Writing a full blown application just costs you time and you my do things wrong.

Instead concentrate just on the actual algorithm and validating its results. Write a class that solves the questions and a few tests to show that it works. That's all.

Do you know the KISS principle? Don't do things you weren't asked to do unless you feel quite confident about what you're doing and want to show more then asked.

\$\endgroup\$
  • 5
    \$\begingroup\$ You're right about the costing of time and possibly adding complexities that could end up costing you marks, however I would be careful with the definition of a program. A library generally isn't regarded as a program, it's an element that is incorporated into one. Maybe it would be better to design the algorithm as a library but then build a simple console or GUI program that implements that library thereby covering all your bases. \$\endgroup\$ – jskrwyk Jun 5 '17 at 1:37
  • \$\begingroup\$ @JamesKrawczyk according to thefreedictionary: 1. computer program - (computer science) a sequence of instructions that a computer can interpret and execute; that's why it's called programming a not applicationing or something else because you write programs which is anything that a computer can interpret and execute like a script, a function, a library or a unit test ;-) \$\endgroup\$ – t3chb0t Jun 5 '17 at 6:45
  • \$\begingroup\$ Re "that's why it's called": no. It was called programming a decade before anyone talked about libraries or applications, so the terminology wasn't a deliberate choice not to call it librarying or applicationing. And in the 72 years since there's been time for semantic drift. \$\endgroup\$ – Peter Taylor Jun 5 '17 at 9:53
  • \$\begingroup\$ @t3chb0t You're right about the dictionary definition of a program but the contextual usage when asked by a employer or client to "write a program" would generally be accept to produce them something they can run and use, not a block of code that can be incorporated into something they can run and use that would need further developed. You'll likely risk end up losing more marks by building just a library than needs built into an program if they wanted a program than building the program slightly wrong to begin with. As I said probably best to do both – a program with a library for the logic. \$\endgroup\$ – jskrwyk Jun 5 '17 at 10:44
  • \$\begingroup\$ @JamesKrawczyk, I'd say that unless an interview specifically asks you to provide some sort of GUI, unit-test(s) will "sell" you better than any console app you can come up with. \$\endgroup\$ – Nikita B Jun 5 '17 at 10:54
3
\$\begingroup\$

[Complexity] The complexity may be too high for the task although it shows some long-term thinking. For the long term, it may be useful to provide for some flexibility (variables instead of hard-coding numbers). I do like the long-term-thinking of using Template Parameters and extension methods.

[If testing is required] Since "TestCount<>()" is only called from one spot, you could remove it and issue the test inline with a

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

Some of the test code could be separated into a test project. This would show you know how to use a Test Suite and remove some clutter from the code. It would also allow you to make changes to the test without disturbing the original code. It may also require you to compartmentalize the code to allow it to be independently testable.

[Separation of concerns] As mentioned by others, separating the "engine"/algorithm from the user interface will allow you to reuse that algorithm in other types of programs. It could be put in a separate DLL and called from projects using other .NET compatible languages. I would not allow the routine that generates the numbers to display.

[Initialize all variables] I write code in multiple languages and I initialize all variables (where possible) for a couple of reasons: 1) I don't want it to be necessary to remember specific language default values. 2) It minimizes surprises and side-effects (even during debugging).

Here is a technique that separates the algorithm from the interface. It ensures the numbers are exhausted before returning. Something like this could be used to allow the developer to use the code in other project types without being bound to the console. //not threaded

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));
      }
   }
}
\$\endgroup\$
1
\$\begingroup\$

The solution in the OP seems a bit over the top for a (seemingly?) simple problem. As t3chb0t already pointed out, keep it simple if possible. Taking into account the comment by @JamesK it seems likely that this problem is just a screening test to weed out people who have never written a program before. In this case a simple and succinct solution should be enough to pass.

The straight forward approach would be to fill an unordered set with random numbers satisfying the given criteria until the appropriate amount is reached.

Here is some C++ code showcasing the above approach.

#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)));
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ @tinstaafl The C++ snipper is more like a proof of concept of the approach outlined in the answer. The main point here is that this problem can be solved with significantly less code than presented in the OP. I was simply wondering why. \$\endgroup\$ – yuri Jun 4 '17 at 23:22
  • 4
    \$\begingroup\$ <iostream> includes more than you need (like statically constructed stream objects). std::size_t simply needs <cstddef>. Don't use rand() (see: rand considered harmful). You define max but use its value in the loop condition. Finally, as you insert more values in the range, the likelihood of generating a unique value decreases. Instead, generate the full range of values first then shuffle. \$\endgroup\$ – Snowhawk Jun 5 '17 at 0:41
  • 3
    \$\begingroup\$ Also, your use of std::unordered_set throws away the "random" order you insert with. \$\endgroup\$ – Snowhawk Jun 5 '17 at 0:50
  • 4
    \$\begingroup\$ While I agree that the task's solution can be made much simpler than that provided by the OP, unfortunately this answer doesn't come close to meeting the requirements of the OP as the resulting list is not in a random order but in an order defined by the implementation of unordered_set. \$\endgroup\$ – theosza Jun 5 '17 at 9:36
  • 3
    \$\begingroup\$ @yuri There are perfectly reasonable implementations of a hash table, where the output order depends on the hash of the values, not their insertion order. Since the identity function is a fine hash for integers, that'd mean a pretty sorted output. Just because the implementation(s) you tested don't exhibit that behavior, doesn't mean that there aren't other, standard conformant implementations that do. So this answer relies on implementation details that might differ between different implementations of the standard library or even different versions of the same library. \$\endgroup\$ – CodesInChaos Jun 5 '17 at 22:18
0
\$\begingroup\$

You don't need to shuffle position 0
Same can be a valid shuffle - it is a likely as any shuffle

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;
        }
    }
}
\$\endgroup\$
-5
\$\begingroup\$

Just create a list of integers with 10000 numbers, then shuffle it :)

You could even store the list. That way the folowing executions would just do the shuffle instead of the generate list and shuffle.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution (actually the same solution), but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$ – Toby Speight Jun 6 '17 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.