[Hard] interview questions #2

[rygh4775]

[rygh4775]

Approach

• Shuffle the first n-1 elements
• Swap nth element with a random element in the array

Solution

/* Random number between lower and higher, inclusive */
int rand(int lower, int higher) {
  return lower + (int)(Math.random() * (higher - lower + 1))
}

int[] shuffleArrayRecursively(int[] cards, int i) {
  if (i==0) return cards;

  shffleArrayRecursively(cards, i - 1); // Shuffle earlier part
  int k = rand(0, i); // Pick random index to swap with

  /* Swap elemnt k and i */
  int temp = cards[k];
  cards[k] = cards[i];
  cards[i] = temp;

  /* Return shuffled array */
  return cards;
}

int[] shuffleArrayIteratively(int[] cards, int i) {
  for(int i = 0; i < cards.length; i ++) {
        int k = rand(0, i);
    int temp = cards[k];
        int cards[k] = cards[i];
    int cards[i] = temp;
  }
  return cards;
}