Chargebee · Coding Rounds
DSA Questions Asked at Chargebee
Sourced from reported Online Assessments, screening calls, and onsite coding rounds. Chargebee's coding bar leans on clean, generalizable solutions and the test cases you think of — not just a passing brute force.
// Pattern Note
Interviewers explicitly said they cared more about test-case coverage and extensibility (e.g. "does your knight-move solution work on an N×N board?") than squeezing out the last bit of performance. Narrate your assumptions out loud.
8
Problems
1.5h
Est. Time
ASKED IN: Coding round — asked as "longest non-repeating character sequence"
KEY INSIGHT: Expand right pointer always. When the char at right was seen inside the current window, jump left to (last index of that char + 1) instead of shrinking one step at a time.
Pattern: Sliding Window + HashMap Optimal: O(n) Space: O(min(n, charset))
BRUTE FORCE
def lengthOfLongestSubstring(s):
longest = 0
for i in range(len(s)):
seen = set()
for j in range(i, len(s)):
if s[j] in seen:
break
seen.add(s[j])
longest = max(longest, j - i + 1)
return longest
# Time: O(n^2) | Space: O(n)
OPTIMAL SOLUTION
def lengthOfLongestSubstring(s):
last_seen = {} # char -> last index seen
left = 0
longest = 0
for right, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= left:
left = last_seen[ch] + 1 # jump left past the repeat
last_seen[ch] = right
longest = max(longest, right - left + 1)
return longest
# Time: O(n) — each index visited once | Space: O(min(n, 128)) ASKED IN: Coding round — "flatten an array" (arrays can nest to arbitrary depth)
KEY INSIGHT: Recursion is the natural fit, but interviewers often push for the iterative version to avoid Python's recursion limit on deeply nested input.
Pattern: Recursion / Explicit Stack Optimal: O(n) Space: O(d) — d = max nesting depth
BRUTE FORCE
def flatten(arr):
result = []
for el in arr:
if isinstance(el, list):
result.extend(flatten(el)) # recurse into nested list
else:
result.append(el)
return result
# Time: O(n) | Space: O(n) output + O(d) recursion stack
# Risk: RecursionError on very deep nesting
OPTIMAL SOLUTION
def flatten(arr):
result = []
stack = [iter(arr)] # stack of iterators, not values
while stack:
try:
item = next(stack[-1])
if isinstance(item, list):
stack.append(iter(item))
else:
result.append(item)
except StopIteration:
stack.pop() # this iterator is exhausted
return result
# Time: O(n) | Space: O(n) output + O(d) explicit stack
# Iterative -> no Python recursion-depth limit ASKED IN: AmbitionBox — SDE Intern round
KEY INSIGHT: Sort meetings by start time. Keep a min-heap of end times for rooms in use. If the earliest-ending room frees up before the next meeting starts, reuse it — else allocate a new room.
Pattern: Sort + Min-Heap of end times Optimal: O(n log n) Space: O(n)
BRUTE FORCE
def minMeetingRooms(intervals):
intervals.sort()
rooms = [] # end time of each room currently in use
for start, end in intervals:
# try to fit into any existing room
placed = False
for i in range(len(rooms)):
if rooms[i] <= start:
rooms[i] = end
placed = True
break
if not placed:
rooms.append(end)
return len(rooms)
# Time: O(n^2) worst case | Space: O(n)
OPTIMAL SOLUTION
import heapq
def minMeetingRooms(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[0])
heap = [] # min-heap of end times of rooms in use
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse the earliest-freeing room
else:
heapq.heappush(heap, end) # need a new room
return len(heap)
# Time: O(n log n) | Space: O(n) ASKED IN: Final round — "design a queue using arrays"
KEY INSIGHT: Never shift elements. Track head, count (or a tail + isFull flag) and move indices with (i + 1) % capacity — this gives true O(1) enqueue/dequeue, unlike list.pop(0).
Pattern: Fixed array + head/tail modulo capacity Optimal: O(1) per operation Space: O(k)
BRUTE FORCE
class QueueBad:
"""Naive: uses list, pop(0) is O(n) — shifts every remaining element."""
def __init__(self, k):
self.q = []
self.capacity = k
def enqueue(self, value):
if len(self.q) >= self.capacity: return False
self.q.append(value)
return True
def dequeue(self):
if not self.q: return False
self.q.pop(0) # O(n) shift
return True
# Time: O(n) dequeue | Space: O(k)
OPTIMAL SOLUTION
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.capacity = k
self.head = 0
self.count = 0
def enQueue(self, value):
if self.count == self.capacity: return False
tail = (self.head + self.count) % self.capacity
self.data[tail] = value
self.count += 1
return True
def deQueue(self):
if self.count == 0: return False
self.head = (self.head + 1) % self.capacity
self.count -= 1
return True
def Front(self):
return -1 if self.count == 0 else self.data[self.head]
def Rear(self):
if self.count == 0: return -1
return self.data[(self.head + self.count - 1) % self.capacity]
# Time: O(1) all ops | Space: O(k) ASKED IN: Onsite round — "given a range A to B, find all numbers whose set-bit count is prime"
KEY INSIGHT: For 32-bit inputs, popcount is at most 32, so the set of possible primes ({2,3,5,7,11,13,17,19,23,29,31}) can be precomputed once as a constant lookup set.
Pattern: Bit counting + prime lookup Optimal: O((B - A) · log(max)) Space: O(1)
BRUTE FORCE
def is_prime(n):
if n < 2: return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0: return False
return True
def countPrimeSetBits(left, right):
count = 0
for num in range(left, right + 1):
bits = bin(num).count('1')
if is_prime(bits):
count += 1
return count
# Time: O((B-A) * sqrt(32)) | Space: O(1)
OPTIMAL SOLUTION
PRIMES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31} # only possible popcounts for <= 32-bit ints
def countPrimeSetBits(left, right):
return sum(1 for n in range(left, right + 1) if bin(n).count('1') in PRIMES)
# Time: O(B - A) — popcount is effectively O(1) via bin().count | Space: O(1) ASKED IN: Screening round — "find all possible moves of a knight, other than the naive approach"
KEY INSIGHT: 'Naive' here means writing out all 8 if-statements by hand. The clean solution is a constant array of (dr, dc) offsets looped over with a single boundary check.
Pattern: Direction-delta array + boundary check Optimal: O(1) — at most 8 moves Space: O(1)
BRUTE FORCE
def knightMoves(row, col):
moves = []
if row-2>=0 and col-1>=0: moves.append((row-2, col-1))
if row-2>=0 and col+1<8: moves.append((row-2, col+1))
if row+2<8 and col-1>=0: moves.append((row+2, col-1))
if row+2<8 and col+1<8: moves.append((row+2, col+1))
if row-1>=0 and col-2>=0: moves.append((row-1, col-2))
if row-1>=0 and col+2<8: moves.append((row-1, col+2))
if row+1<8 and col-2>=0: moves.append((row+1, col-2))
if row+1<8 and col+2<8: moves.append((row+1, col+2))
return moves
# Works, but 8 hand-written branches — hard to extend (e.g. NxN board, different piece)
OPTIMAL SOLUTION
KNIGHT_DELTAS = [(-2,-1), (-2,1), (-1,-2), (-1,2),
(1,-2), (1,2), (2,-1), (2,1)]
def knightMoves(row, col, n=8):
return [
(row + dr, col + dc)
for dr, dc in KNIGHT_DELTAS
if 0 <= row + dr < n and 0 <= col + dc < n
]
# Time: O(1) | Space: O(1)
# Generalizes instantly to an N x N board by changing 'n' ASKED IN: AmbitionBox — SDE Intern round: "bananas" → "bans"
KEY INSIGHT: Order must be preserved (unlike LeetCode 316's lexicographically-smallest variant) — just drop any character already seen, in a single left-to-right pass.
Pattern: HashSet of seen characters Optimal: O(n) Space: O(k) — k = distinct chars
BRUTE FORCE
def removeDuplicates(s):
result = ""
for i, ch in enumerate(s):
if ch not in result: # O(n) membership check on a string
result += ch
return result
# Time: O(n^2) | Space: O(n)
OPTIMAL SOLUTION
def removeDuplicates(s):
seen = set()
result = []
for ch in s:
if ch not in seen:
seen.add(ch)
result.append(ch)
return "".join(result)
# Example: "bananas" -> "bans"
# Time: O(n) | Space: O(n) ASKED IN: Coding round — "find the 3rd highest salary of an employee"
KEY INSIGHT: DISTINCT + OFFSET breaks on ties across rows; DENSE_RANK() correctly treats equal salaries as the same rank, which is what "3rd highest" really means.
Pattern: DENSE_RANK() window function Optimal: O(n log n) Space: O(n)
STRAIGHTFORWARD APPROACH
-- Correlated subquery: count distinct salaries strictly greater
SELECT DISTINCT e1.salary AS third_highest_salary
FROM employee e1
WHERE 2 = (
SELECT COUNT(DISTINCT e2.salary)
FROM employee e2
WHERE e2.salary > e1.salary
);
-- Works, but re-scans the table for every row -> O(n^2)
OPTIMAL SOLUTION
-- Window function: rank distinct salaries, pick rank 3
WITH ranked AS (
SELECT salary,
DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
FROM employee
)
SELECT DISTINCT salary AS third_highest_salary
FROM ranked
WHERE rnk = 3;
-- Single sorted pass, correctly handles duplicate salaries as tied ranks