Shuffle String Introduction
Shuffle String Introduction
The Shuffle String problem asks us to take an input string and shuffle it where each character is just as likely to be in any position. This problem requires us to compare the shuffled string with the original string and calculate a metric called the "Hamming distance". The Hamming distance measures the number of positions at which the shuffled string differs from the original string.
Shuffle String Problem
Shuffle String Problem
-
Write a function that takes a string as an input and returns a shuffled version of that string (i.e. a version where each character is just as likely to be in any given position)
-
Write a function that analyzes how well your previous function randomly shuffles the string
Shuffle String Solutions
Shuffle String Solutions
To solve this, we use the random.shuffle function from the random module to shuffle the characters in the input string. We convert the string to a list of characters, shuffle the list, and then convert it back to a string using the join method. The resulting string will have the same characters as the input string but in a shuffled order.
To analyze how well the our function randomly shuffles a string, we can compare the shuffled string with the original string and calculate a metric called the "Hamming distance". The Hamming distance measures the number of positions at which the shuffled string differs from the original string. We iterate over the corresponding characters of the original string and shuffled string using the zip function. We compare each pair of characters and count the number of positions where they differ using a generator expression and the sum function. Finally, we divide the hamming distance by the length of the strings to obtain the shuffle quality as a ratio between 0 and 1 as our output. A shuffle quality closer to 1 indicates a better shuffle, while a value closer to 0 means that the shuffled string is similar to the original string.
import random
def shuffle_string(string):
chars = list(string)
random.shuffle(chars)
shuffled_string = ''.join(chars)
return shuffled_string
def analyze_shuffle_quality(original_string, shuffled_string):
hamming_distance = sum(c1 != c2 for c1, c2 in zip(original_string, shuffled_string))
shuffle_quality = hamming_distance / len(original_string)
return shuffle_quality
# Test Case
original_string = "abcdefg"
shuffled_string = shuffle_string(original_string)
quality = analyze_shuffle_quality(original_string, shuffled_string)
print(f"Shuffled string: {original_string}")
print(f"Shuffled string: {shuffled_string}")
print(f"Shuffle quality: {quality}")1import random
2
3def shuffle_string(string):
4 chars = list(string)
5 random.shuffle(chars)
6 shuffled_string = ''.join(chars)
7 return shuffled_string
8
9def analyze_shuffle_quality(original_string, shuffled_string):
10 hamming_distance = sum(c1 != c2 for c1, c2 in zip(original_string, shuffled_string))
11 shuffle_quality = hamming_distance / len(original_string)
12 return shuffle_quality
13
14# Test Case
15original_string = "abcdefg"
16shuffled_string = shuffle_string(original_string)
17quality = analyze_shuffle_quality(original_string, shuffled_string)
18print(f"Shuffled string: {original_string}")
19print(f"Shuffled string: {shuffled_string}")
20print(f"Shuffle quality: {quality}")Time/Space Complexity Analysis
- Time Complexity: O(N), where N is the length of the input array. where N is the length of the input string.
- Space Complexity: O(N), where N is the length of the input string.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
