More patterns for coding interviews |||

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