Check if array B is a permutation of A

by

The question is theoretical but you can do it in O(n) time and o(1) space. Allocate an array of 232 counters and set them all to zero. This is O(1) step because the array has constant size. Then iterate through the two arrays. For array A, increment the counters corresponding to the integers read. For array B, decrement them. If you run into a negative counter value during iteration of array B, stop — the arrays are not permutations of each others. Otherwise at the end (assuming A and B have the same size, a prerequisite) the counter array is all zero and the two arrays are permutations of each other.

This is O(1) space and O(n) time solution. However it is not practical, but would easily pass as a solution to the interview question. At least it should.

More obscure solutions

  • Using a nondeterministic model of computation, checking that the two arrays are not permutations of each others can be done in O(1) space, O(n) time by guessing an element that has differing count on the two arrays, and then counting the instances of that element on both of the arrays.

  • In randomized model of computation, construct a random commutative hash function and calculate the hash values for the two arrays. If the hash values differ, the arrays are not permutations of each others. Otherwise they might be. Repeat many times to bring the probability of error below desired threshold. Also on O(1) space O(n) time approach, but randomized.

  • In parallel computation model, let ‘n’ be the size of the input array. Allocate ‘n’ threads. Every thread i = 1 .. n reads the ith number from the first array; let that be x. Then the same thread counts the number of occurrences of x in the first array, and then check for the same count on the second array. Every single thread uses O(1) space and O(n) time.

  • Interpret an integer array [ a1, …, an ] as polynomial xa1 + xa2 + … + xan where x is a free variable and the check numerically for the equivalence of the two polynomials obtained. Use floating point arithmetics for O(1) space and O(n) time operation. Not an exact method because of rounding errors and because numerical checking for equivalence is probabilistic. Alternatively, interpret the polynomial over integers modulo a prime number, and perform the same probabilistic check.

More Related Contents:

  1. Algorithm to generate all possible permutations of a list?
  2. Fast permutation -> number -> permutation mapping algorithms
  3. Generate all binary strings of length n with k bits set
  4. Shuffle list, ensuring that no item remains in same position
  5. Algorithm for finding numerical permutation given lexicographic index
  6. Find the index of a given permutation in the sorted list of the permutations of a given string
  7. Algorithm to list unique permutations of string with duplicate letters
  8. Calculating permutations in F#
  9. Permute all unique enumerations of a vector in R
  10. Algorithm for permutations of operators and operands
  11. Algorithm to list all unique permutations of numbers contain duplicates
  12. What is tail call optimization?
  13. How does the Google “Did you mean?” Algorithm work? [closed]
  14. Algorithm for Determining Tic Tac Toe Game Over
  15. How to find all combinations of coins when given some dollar value [closed]
  16. How to make rounded percentages add up to 100%
  17. Merge Sort a Linked List
  18. How do you like your primary keys? [closed]
  19. How do I efficiently determine if a polygon is convex, non-convex or complex?
  20. Generating permutations lazily
  21. Compute the minimal number of swaps to order a sequence
  22. Find the missing and duplicate elements in an array in linear time and constant space
  23. Function for creating color wheels [closed]
  24. How do I check if a directed graph is acyclic?
  25. How to find the smallest number with just 0 and 1 which is divided by a given number?
  26. Count the number of set bits in a 32-bit integer
  27. YouTube URL algorithm?
  28. Why is my recursive function so slow in R?
  29. counting combinations and permutations efficiently
  30. What is the difference between Linear search and Binary search?

Leave a Comment