More patterns for coding interviews |||

Mohamed Abogazia
2 min readOct 27, 2021

--

Unpopular patterns that show up often in coding interviews

Series: Part1, Part2

Today I will share one pattern only.
I just came up with this implementation pattern today after knowing from a colleague that Leetcode 767. Reorganize String showed up in her phone interview today with Google. let’s dive right into it

9- Rearrange string k distance apart

This pattern solves problems where you need to reorganize a string/number such that at least there are k characters (inclusive) between instances of the same character.

The algorithm (Greedy):
- Push unique characters, sorted by frequency, k times, while reducing the count of each character you push.
- Repeat the above step until you exhaust the count of all characters.

The implementation approach:
- Count the characters and heapify them in a max heap such that the max frequency character is at the top of the heap
- Pop most frequent character (the top of the heap) k times. while storing the poped elements in a stack
- For elements in the stack, reduce their count by one and push elements with count>0 to the heap again
- Repeat until you empty the queue and the stack.

Examples:

767. Reorganize String(Google)

class Solution:
def reorganizeString(self, s):
queue, stack, ans =[(-count,char) for char, count in Counter(s).items()], [], ""
heapify(queue)

while queue:
for _ in range(2):
if not queue and stack: return ""
if queue:
count, char = heappop(queue)
ans += char
if count<-1: stack.append((count+1, char))

while stack: heappush(queue, stack.pop())

return ans

621. Task Scheduler

class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
time, queue, stack = 0, [(-1*count, char) for char, count in Counter(tasks).items()], []
heapify(queue)

while queue:
for _ in range(n+1):
if queue or stack: time += 1
if queue:
count, char = heappop(queue)
if count<-1: stack.append((count+1,char))

while stack: heappush(queue, stack.pop())

return time

358. Rearrange String k Distance Apart

class Solution:
def rearrangeString(self, s, k):
queue, stack, ans =[(-count,char) for char, count in Counter(s).items()], [], ""
heapify(queue)

while queue:
for _ in range(k):
if not queue and stack: return ""
if queue:
count, char = heappop(queue)
ans += char
if count<-1: stack.append((count+1, char))

while stack: heappush(queue, stack.pop())

return ans

That’s it for today.
Clap and follow for more patterns

--

--