<p>Not so long ago I was in an interview, that required solving two very interesting problems. I'm curious how would you approach the solutions.</p>

<p>Problem 1 :</p>

<p><strong>Product of everything except current</strong>  </p>

<p>Write a function that takes as input two integer arrays of length len, input and index, and generates a third array, result, such that:
result[i] = product of everything in input except input[index[i]]</p>

<p>For instance, if the function is called with len=4, input={2,3,4,5}, and index={1,3,2,0}, then result will be set to {40,24,30,60}.</p>

<p>IMPORTANT: Your algorithm must run in linear time.</p>

<p>Problem 2 : ( the topic was in one of Jeff posts )</p>

<p><strong>Shuffle card deck evenly</strong></p>

<ol>
<li><p>Design (either in C++ or in C#) a class Deck to represent an ordered deck of cards, where a deck contains 52 cards, divided in 13 ranks (A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K) of the four suits: spades (?), hearts (?), diamonds (?) and clubs (?).</p></li>
<li><p>Based on this class, devise and implement an efficient algorithm to shuffle a deck of cards. The cards must be evenly shuffled, that is, every card in the original deck must have the same probability to end up in any possible position in the shuffled deck.
The algorithm should be implemented in a method shuffle() of the class Deck: 
void shuffle()</p></li>
<li><p>What is the complexity of your algorithm (as a function of the number n of cards in the deck)?</p></li>
<li><p>Explain how you would test that the cards are evenly shuffled by your method (black box testing).</p></li>
</ol>

<p>P.S. I had two hours to code the solutions</p>

[{'answer_id': 56225, 'author': 'Vaibhav', 'author_id': 380, 'author_profile': 'https://Stackoverflow.com/users/380', 'pm_score': 1, 'selected': False, 'text': '<p>For the first one, first calculate the product of entire contents of input, and then for every element of index, divide the calculated product by input[index[i]], to fill in your result array.</p>\n\n<p>Of course I have to assume that the input has no zeros.</p>\n'}, {'answer_id': 56236, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>Vaibhav, unfortunately we have to assume, that there could be a 0 in the input table.</p>\n'}, {'answer_id': 56270, 'author': 'Tnilsson', 'author_id': 4165, 'author_profile': 'https://Stackoverflow.com/users/4165', 'pm_score': 3, 'selected': False, 'text': '<p>First question: </p>\n\n<pre><code>int countZeroes (int[] vec) {\nint ret = 0;\nforeach(int i in vec) if (i == 0) ret++;\n\nreturn ret;\n}\n\nint[] mysticCalc(int[] values, int[] indexes) {\n    int zeroes = countZeroes(values); \n    int[] retval = new int[values.length];\n    int product = 1;\n\n    if (zeroes &gt;= 2) { // 2 or more zeroes, all results will be 0\n        for (int i = 0; i &gt; values.length; i++) {\n            retval[i] = 0;      \n        }\n        return retval;\n    }\n    foreach (int i in values) {\n        if (i != 0) product *= i; // we have at most 1 zero, dont include in product;\n    }\n    int indexcounter = 0;\n    foreach(int idx in indexes) {\n        if (zeroes == 1 &amp;&amp; values[idx] != 0) {  // One zero on other index. Our value will be 0\n            retval[indexcounter] = 0;\n        }\n        else if (zeroes == 1) { // One zero on this index. result is product\n            retval[indexcounter] = product;\n        }\n        else { // No zeros. Return product/value at index\n            retval[indexcounter] = product / values[idx];\n        }\n        indexcouter++;\n    }   \n    return retval;\n}\n</code></pre>\n\n<p>Worst case this program will step through 3 vectors once.</p>\n'}, {'answer_id': 56275, 'author': 'jfs', 'author_id': 4279, 'author_profile': 'https://Stackoverflow.com/users/4279', 'pm_score': 1, 'selected': False, 'text': '<h1>Product of everything except current in C</h1>\n\n<pre><code>void product_except_current(int input[], int index[], int out[], \n                            int len) {\n  int prod = 1, nzeros = 0, izero = -1;\n\n  for (int i = 0; i &lt; len; ++i) \n    if ((out[i] = input[index[i]]) != 0)\n      // compute product of non-zero elements \n      prod *= out[i]; // ignore possible overflow problem\n    else {\n      if (++nzeros == 2) \n         // if number of zeros greater than 1 then out[i] = 0 for all i\n         break; \n      izero = i; // save index of zero-valued element\n    }\n\n  //  \n  for (int i = 0; i &lt; len; ++i)  \n    out[i] = nzeros ? 0 : prod / out[i];                               \n\n  if (nzeros == 1)\n    out[izero] = prod; // the only non-zero-valued element\n}\n</code></pre>\n'}, {'answer_id': 56280, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 1, 'selected': False, 'text': "<p>Tnilsson, great solution ( because I've done it the exact same way :P ).</p>\n\n<p>I don't see any other way to do it in linear time. Does anybody ? Because the recruiting manager told me, that this solution was not strong enough.</p>\n\n<p>Are we missing some super complex, do everything in one return line, solution ?</p>\n"}, {'answer_id': 56291, 'author': 'Tnilsson', 'author_id': 4165, 'author_profile': 'https://Stackoverflow.com/users/4165', 'pm_score': 0, 'selected': False, 'text': '<p><strong>Second problem.</strong></p>\n\n<pre><code>    public static void shuffle (int[] array) \n    {\n        Random rng = new Random();   // i.e., java.util.Random.\n        int n = array.length;        // The number of items left to shuffle (loop invariant).\n        while (n &gt; 1) \n        {\n            int k = rng.nextInt(n);  // 0 &lt;= k &lt; n.\n            n--;                     // n is now the last pertinent index;\n            int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).\n            array[n] = array[k];\n            array[k] = temp;\n        }\n    }\n</code></pre>\n\n<p>This is a copy/paste from the wikipedia article about the <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle" rel="nofollow noreferrer">Fisher-Yates</a> shuffle. O(n) complexity</p>\n'}, {'answer_id': 56314, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': "<p>Tnilsson, I agree that YXJuLnphcnQ solution is arguably faster, but the idee is the same. I forgot to add, that the language is optional in the first problem, as well as int the second.</p>\n\n<p>You're right, that calculationg zeroes, and the product int the same loop is better. Maybe that was the thing.</p>\n"}, {'answer_id': 56323, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': "<p>Tnilsson, I've also uset the Fisher-Yates shuffle :). I'm very interested dough, about the testing part :)</p>\n"}, {'answer_id': 56379, 'author': 'jfs', 'author_id': 4279, 'author_profile': 'https://Stackoverflow.com/users/4279', 'pm_score': 0, 'selected': False, 'text': '<h1>Shuffle card deck evenly in C++</h1>\n\n<pre><code>#include &lt;algorithm&gt;\n\nclass Deck {\n  // each card is 8-bit: 4-bit for suit, 4-bit for value\n  // suits and values are extracted using bit-magic\n  char cards[52];\n  public:\n  // ...\n  void shuffle() {\n    std::random_shuffle(cards, cards + 52);\n  }\n  // ...\n};\n</code></pre>\n\n<p>Complexity: Linear in N. Exactly 51 swaps are performed. See <a href="http://www.sgi.com/tech/stl/random_shuffle.html" rel="nofollow noreferrer">http://www.sgi.com/tech/stl/random_shuffle.html</a></p>\n\n<p><strong>Testing</strong>:</p>\n\n<pre><code>  // ...\n  int main() {\n    typedef std::map&lt;std::pair&lt;size_t, Deck::value_type&gt;, size_t&gt; Map;\n    Map freqs;    \n    Deck d;\n    const size_t ntests = 100000;\n\n    // compute frequencies of events: card at position\n    for (size_t i = 0; i &lt; ntests; ++i) {\n      d.shuffle();\n      size_t pos = 0;\n      for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos) \n        ++freqs[std::make_pair(pos, *j)]; \n    }\n\n    // if Deck.shuffle() is correct then all frequencies must be similar\n    for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)\n      std::cout &lt;&lt; "pos=" &lt;&lt; j-&gt;first.first &lt;&lt; " card=" &lt;&lt; j-&gt;first.second \n                &lt;&lt; " freq=" &lt;&lt; j-&gt;second &lt;&lt; std::endl;    \n  }\n</code></pre>\n\n<p>As usual, one test is not sufficient.</p>\n'}, {'answer_id': 56482, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>Trilsson made a separate topic about the testing part of the question</p>\n\n<p><a href="https://stackoverflow.com/questions/56411/how-to-test-randomness-case-in-point-shuffling">How to test randomness (case in point - Shuffling)</a></p>\n\n<p>very good idea Trilsson:)</p>\n'}, {'answer_id': 56501, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': "<p>YXJuLnphcnQ, that's the way I did it too. It's the most obvious. </p>\n\n<p>But the fact is, that if you write an algorithm, that just shuffles all the cards in the collection one position to the right every time you call sort() it would pass the test, even though the output is not random.</p>\n"}, {'answer_id': 56549, 'author': 'ljs', 'author_id': 3394, 'author_profile': 'https://Stackoverflow.com/users/3394', 'pm_score': 1, 'selected': False, 'text': "<p>A linear-time solution in C#3 for the first problem is:-</p>\n\n<pre><code>IEnumerable&lt;int&gt; ProductExcept(List&lt;int&gt; l, List&lt;int&gt; indexes) {\n    if (l.Count(i =&gt; i == 0) == 1) {\n        int singleZeroProd = l.Aggregate(1, (x, y) =&gt; y != 0 ? x * y : x);\n        return from i in indexes select l[i] == 0 ? singleZeroProd : 0;\n    } else {\n        int prod = l.Aggregate(1, (x, y) =&gt; x * y);\n        return from i in indexes select prod == 0 ? 0 : prod / l[i];\n    }\n}\n</code></pre>\n\n<p><strong>Edit:</strong> Took into account a single zero!! My last solution took me 2 minutes while I was at work so I don't feel so bad :-)</p>\n"}, {'answer_id': 56940, 'author': 'ljs', 'author_id': 3394, 'author_profile': 'https://Stackoverflow.com/users/3394', 'pm_score': 1, 'selected': False, 'text': '<p>Here\'s the answer to the second one in C# with a test method. Shuffle looks O(n) to me.</p>\n\n<p><strong>Edit:</strong> Having looked at the Fisher-Yates shuffle, I discovered that I\'d re-invented that algorithm without knowing about it :-) it is obvious, however. I implemented the Durstenfeld approach which takes us from O(n^2) -> O(n), really clever!</p>\n\n<pre><code>public enum CardValue { A, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, J, Q, K }\npublic enum Suit { Spades, Hearts, Diamonds, Clubs }\n\npublic class Card {\n    public Card(CardValue value, Suit suit) {\n        Value = value;\n        Suit = suit;\n    }\n\n    public CardValue Value { get; private set; }\n    public Suit Suit { get; private set; }\n}\n\npublic class Deck : IEnumerable&lt;Card&gt; {\n    public Deck() {\n        initialiseDeck();\n        Shuffle();\n    }\n\n    private Card[] cards = new Card[52];\n\n    private void initialiseDeck() {\n        for (int i = 0; i &lt; 4; ++i) {\n            for (int j = 0; j &lt; 13; ++j) {\n                cards[i * 13 + j] = new Card((CardValue)j, (Suit)i);\n            }\n        }\n    }\n\n    public void Shuffle() {\n        Random random = new Random();\n\n        for (int i = 0; i &lt; 52; ++i) {\n            int j = random.Next(51 - i);\n            // Swap the cards.\n            Card temp = cards[51 - i];\n            cards[51 - i] = cards[j];\n            cards[j] = temp;\n        }\n    }\n\n    public IEnumerator&lt;Card&gt; GetEnumerator() {\n        foreach (Card c in cards) yield return c;\n    }\n\n    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {\n        foreach (Card c in cards) yield return c;\n    }\n}\n\nclass Program {\n    static void Main(string[] args) {\n        foreach (Card c in new Deck()) {\n            Console.WriteLine("{0} of {1}", c.Value, c.Suit);\n        }\n\n        Console.ReadKey(true);\n    }\n}\n</code></pre>\n'}, {'answer_id': 292078, 'author': 'Darius Bacon', 'author_id': 27024, 'author_profile': 'https://Stackoverflow.com/users/27024', 'pm_score': 1, 'selected': False, 'text': '<p>In Haskell:</p>\n\n<pre><code>import Array\n\nproblem1 input index = [(left!i) * (right!(i+1)) | i &lt;- index]\n  where left  = scanWith scanl\n        right = scanWith scanr\n        scanWith scan = listArray (0, length input) (scan (*) 1 input)\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/56215', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/-1/']