Google｜Coding Interview｜Redistribute spaces in a fixed-sized array of characters
Anonymous User
1828
GoogleInterview

I was given this problem during a google interview last year. I didn't pass that round, but I recently coded up my solution and was wondering if this is right, or if there's a better solution? Thanks!

Question:
Input: fixed-size array of characters, containing:

  • 0 or more leading spaces
  • 0 or more words separated by 1 or more spaces
  • 0 or more trailing spaces

Output: the same array where spaces are re-distributed between the words in such a way that they are:

  • no more leading spaces
  • no more trailing spaces
  • roughly the same space gaps between the words. I.e. the minimum and the maximum number of spaces between the words can not differ by more than 1.

Restriction: in-place algorithm. Do not use additional space for copying the characters.

Example:
Input: "....word1.....word2.....word3....."
Output: "word1.........word2..........word3"
Gaps: 10 and 9

My solution: (I do notice that since string is immutable in python, my solution is not in-place?)

# remove leading and trailing spaces
s = raw_input()
orig_len = len(s)
s = s.strip(" ")
new_len = len(s)

# find indices of non-space chars
indices = [i for i in range(new_len) if s[i] != ' ']
num_spaces = orig_len - len(indices)

# find indices of start and end of words
start_indices = [indices[i] for i in range(1, len(indices)) if indices[i] != (indices[i-1] + 1)]
start_indices = [0] + start_indices

end_indices = [indices[i] for i in range(len(indices)-1) if indices[i+1] != (indices[i] + 1)]
end_indices = end_indices + [indices[-1]]

intervals = zip(start_indices, end_indices)
num_words = len(intervals)

spaces_each = num_spaces / (num_words - 1)
extra = num_spaces % (num_words - 1)
adjust = 0

for i in range(num_words-1):
	end_of_prev = intervals[i][1]
	start_of_next = intervals[i+1][0]
	gap = start_of_next - end_of_prev - 1

	if extra > 0:
		if gap != spaces_each + 1:
			s = s[:end_of_prev+1+adjust] + (spaces_each + 1) * ' ' + s[start_of_next+adjust:]
			adjust = adjust + spaces_each + 1 - gap
		extra = extra - 1
	elif extra <= 0:
		if gap != spaces_each:
			s = s[:end_of_prev+1+adjust] + spaces_each * ' ' + s[start_of_next+adjust:]
			adjust = adjust + spaces_each - gap
print(s)
Comments (6)