Slaying Live Coding Challenges: A Beginner's Guide to Successby@zavodnoyapl

Slaying Live Coding Challenges: A Beginner's Guide to Success

March 26th, 2024

Get ready for your live coding session by mastering step-by-step problem-solving strategies.

Below, I will describe the conditions of the problem for a live coding interview, the discussion of which I came across on Twitter.

The candidate was asked to write a method that takes a list of transactions and the user's balance and returns an arbitrary structure where each transaction is marked as valid or invalid. The conditions are as follows:

• Transactions are processed from the smallest id to the largest.
• A Bet decreases the balance by the amount, while a Win increases it.
• If the balance becomes negative, the transaction is considered invalid.
• If a transaction is invalid, subsequent transactions with the same orderId are also considered invalid.
• If the id of a transaction is repeated, that transaction is invalid, but the rest with the same orderId should still be processed

The structure of input transactions was:

``````type Transaction = {
id: number,
orderId: number,
amount: number,
txType: 'Bet' | 'Win'
}
``````

The task is quite simple, so it would be doubly disappointing not to solve it during the interview. The peculiarity of this task is that it's easy to make a mistake while solving it, by not carefully reading the conditions, not asking the necessary questions, thereby missing boundary conditions, etc. Adding to all this the heightened level of stress during the interview, we get a higher probability of a failed interview.

Abstraction

Since the task involves several conditions, trying to keep them all in mind and implementing them all at once is a risky practice. According to Miller's law, a person can hold 7 ± 2 elements in their mind simultaneously, but considering the stressful conditions of the interview, this number decreases.

Therefore, let's divide the solution to this problem into independent steps and concentrate our attention on each one separately.

To understand which conditions are independent of others and which ones have a clear dependency, we can apply the following approach: if removing a chosen condition from the overall list preserves the logical structure for both the condition itself and the remaining ones in the list, then that condition is independent and can be solved as a separate task. Let's consider an example:

"Transactions are processed from the smallest `id` to the largest" sounds like an independent task. By solving it, we can rephrase the original problem as follows:

Write a method that takes a list of transactions sorted by `id` and the user's balance and returns an arbitrary structure where each transaction is marked as valid or invalid.

• Transactions are processed from the smallest `id` to the largest;
• A `Bet` decreases the balance by the `amount`, a `Win` increases it;
• If the balance becomes negative, the transaction is considered invalid;
• If a transaction is invalid, subsequent transactions with the same `orderId` are also considered invalid;
• If the `id` of a transaction is repeated, that transaction is invalid, but the rest with the same `orderId` should still be processed.

Therefore, let's consider this as a composition of two functions, where F represents the transaction list validation function, S represents the transaction sorting function, and transactions is the original list of transactions:

``````                                                   Result = F(S(transactions))
``````

Following the above, we can confidently solve the task "Transactions are processed from the smallest `id` to the largest" separately:

``````transactions = transactions.sort((a: Transaction, b: Transaction) => a.id - b.id)
``````

The code turned out to be very simple, but questions immediately arise: what will happen if the transaction IDs are equal but other data is different? Which of these transactions will be processed first?

It's important to understand why this question is crucial. According to an unwritten rule in development, if something can happen, it will happen, and a good programmer should anticipate all boundary conditions in advance.

Let's assume that the transaction which appears first in the original array will be processed first. Therefore, we can consider the above code as solving the given task. If not, then we can refine it according to new conditions, such as dependencies on the `amount` or `orderId`, etc.

Now let's abstract the processing of a single transaction. According to the task conditions, our code should return a structure containing information about the validity or invalidity of a transaction, and each condition specifies that a transaction's status changes to invalid. From this, we can assume that by default all transactions are valid. Then our code may look like this:

``````type Transaction = {
id: number,
orderId: number,
amount: number,
txType: 'Bet' | 'Win'
}

type TransactionAfterValidate = Transaction & {
isValid: boolean
}

function validateTransactionList(transactions: Transaction[], balance: number): TransactionAfterValidate[] {
transactions = transactions.sort((a: Transaction, b: Transaction) => a.id - b.id)

return transactions.map(transaction => validateTransactionItem({...transaction, isValid: true}))
}

function validateTransactionItem(transaction: TransactionAfterValidate) {
return transaction
}
``````

The code above solves the abstract part of the task:

• Write a method that takes a list of transactions and the user's balance.
• Return an arbitrary structure where each transaction is marked as valid or invalid.
• Transactions are processed from the smallest `id` to the largest.

Let's pay attention to the condition that "Bet decreases the balance by the amount, Win increases it." This cannot be implemented in advance because it violates the logical component of another task: "If the balance becomes negative, the transaction is considered invalid." Therefore, the condition about decreasing the balance will be considered outside the abstract description of the method.

Detailing

When detailing, it's important to remember what's being inputted. According to the current condition, although we process each transaction individually, we remember that transactions are sorted by `id`.

Let's solve the next part of the task:

• `Bet` decreases the balance by the amount, `Win` increases it.
• If the balance becomes negative, the transaction is considered invalid.
• If a transaction is invalid, subsequent transactions with the same `orderId` are also considered invalid.
• If the `id` of a transaction is repeated, that transaction is invalid, but the rest with the same `orderId` should still be processed.

Let's solve the problem by breaking it down into two independent subtasks:

1. Handling balance changes due to Bet and Win transactions:
• Bet decreases the balance by the amount, Win increases it.
• If the balance becomes negative, the transaction is considered invalid.
• If a transaction is invalid, subsequent transactions with the same `orderId` are also considered invalid.
2. Handling invalid transactions with duplicate transaction IDs:
• If the `id` of a transaction is repeated, that transaction is invalid, but the rest with the same `orderId` should still be processed.

We'll address each subtask separately to ensure a clear and systematic approach to solving the problem. Based on the returned condition (transaction valid or invalid), we can describe a common interface for services that fulfill these conditions:

``````interface ValidateService {
isValid(transaction: Transaction): boolean
}
``````

The invocation of all these services in validateTransactionItem:

``````function validateTransactionItem(transaction: TransactionAfterValidate, validateServices: ValidateService[]) {
for(const validateService of validateServices) {
transaction.isValid = transaction.isValid && validateService.isValid(transaction)
}

return transaction
}
``````

Now we need to solve the two tasks mentioned earlier and write the services with these solutions into `validateServices`!

• Handling balance changes due to Bet and Win transactions:
• Bet decreases the balance by the amount, Win increases it.
• If the balance becomes negative, the transaction is considered invalid.
• If a transaction is invalid, subsequent transactions with the same `orderId` are also considered invalid.

Does the initial condition provide us with anything regarding the transactions being input in sorted order by `id`? No, because the task doesn't mention transaction IDs. Therefore, the solution to this problem doesn't depend on how transactions are inputted: in sorted order or in random order.

Based on the condition, a transaction is considered invalid if the`orderId` is invalid, and the `orderId` is invalid when the balance becomes negative.

It remains to ask the question: is the balance a static or dynamic variable (can each transaction increase or decrease it)? This question needs to be asked to the interviewer during the live coding session, and in this article, we will consider both cases. Let's start with the case where the balance is static. We'll write the following service, which checks whether the balance will be negative or positive:

``````function initBalanceService(balance: number) {
const getAmountFromTransaction = (transaction: Transaction) => (transaction.amount) * (transaction.txType === 'Win' ? 1 : -1)

return {
canBeNegativeAfterApply: (transaction: Transaction) => (balance + getAmountFromTransaction(transaction)) < 0
}
}
``````

And the service responsible for validating the transaction:

``````function initValidateByBalance(balance: number) {
const balanceService = initBalanceService(balance)
const invalidOrdersMap = new Map<number, true>()

return {
isValid: function (transaction: Transaction) {
if (balanceService.canBeNegativeAfterApply(transaction)) {
invalidOrdersMap.set(transaction.orderId, true)
}

return invalidOrdersMap.has(transaction.orderId)
}
}
}
``````

Now let's consider the case where the balance is dynamic. To fulfill this condition, we just need to modify `initBalanceService`:

``````function initBalanceService(initBalance: number) {
let balance = initBalance
const getAmountFromTransaction = (transaction: Transaction) => (transaction.amount) * (transaction.txType === 'Win' ? 1 : -1)

return {
canBeNegativeAfterApply: (transaction: Transaction) => (balance + getAmountFromTransaction(transaction)) < 0,
apply: (transaction: Transaction) => balance += getAmountFromTransaction(transaction)
}
}
``````

And call the added method in the `initValidateByBalance` service:

``````function initValidateByBalance(balance: number) {
const balanceService = initBalanceService(balance)
const invalidOrdersMap = new Map<number, true>()

return {
isValid: function (transaction: Transaction) {
if (balanceService.canBeNegativeAfterApply(transaction)) {
invalidOrdersMap.set(transaction.orderId, true)
} else {
balanceService.apply(transaction)
}

return !invalidOrdersMap.has(transaction.orderId)
}
}
}
``````

Let's consider the last condition, namely: "If the id of a transaction is repeated, such a transaction is also invalid, but the rest with the same `orderId` should still be processed."

Initially, it seems tempting to use a HashMap, as in the case of orderId, but here we must remember that transactions sorted by id are inputted, and in this task, we can use this without allocating additional memory. To check for duplicates, we only need to store the `id` of the previous transaction: if it's the same as the current one, then it's a duplicate; if not, we overwrite it.

``````function initDuplicateChecker(): ValidateService {
let prevId: number|null = null

return {
isValid: function (transaction: Transaction) {
if (transaction.id === prevId) {
return false
}
prevId = transaction.id

return true
}
}
}
``````

Now we just need to initialize the services, and the final solution will look like this:

``````type Transaction = {
id: number,
orderId: number,
amount: number,
txType: 'Bet' | 'Win'
}

type TransactionAfterValidate = Transaction & {
isValid: boolean
}

interface ValidateService {
isValid(transaction: Transaction): boolean
}

function initBalanceService(initBalance: number) {
let balance = initBalance
const getAmountFromTransaction = (transaction: Transaction) => (transaction.amount) * (transaction.txType === 'Win' ? 1 : -1)

return {
canBeNegativeAfterApply: (transaction: Transaction) => (balance + getAmountFromTransaction(transaction)) < 0,
apply: (transaction: Transaction) => balance += getAmountFromTransaction(transaction)
}
}

function initValidateByBalance(balance: number): ValidateService {
const balanceService = initBalanceService(balance)
const invalidOrdersMap = new Map<number, true>()

return {
isValid: function (transaction: Transaction) {
if (balanceService.canBeNegativeAfterApply(transaction)) {
invalidOrdersMap.set(transaction.orderId, true)
} else {
balanceService.apply(transaction)
}

return !invalidOrdersMap.has(transaction.orderId)
}
}
}

function initDuplicateChecker(): ValidateService {
let prevId: number|null = null

return {
isValid: function (transaction: Transaction) {
if (transaction.id === prevId) {
return false
}
prevId = transaction.id

return true
}
}
}

function validateTransactionList(transactions: Transaction[], balance: number): TransactionAfterValidate[] {
transactions = transactions.sort((a: Transaction, b: Transaction) => a.id - b.id)
const validateServices = [
initValidateByBalance(balance),
initDuplicateChecker()
]

return transactions.map(transaction => validateTransactionItem({...transaction, isValid: true}, validateServices))
}

function validateTransactionItem(transaction: TransactionAfterValidate, validateServices: ValidateService[]) {
for(const validateService of validateServices) {
transaction.isValid = transaction.isValid && validateService.isValid(transaction)
}

return transaction
}
``````

Conclusion

This article has examined an example of how to solve tasks that are closely related to everyday tasks in a company during live coding sessions. The key feature is to try to break down the task into small and concise subtasks. By focusing on these subtasks step by step, we can easily identify boundary conditions, ask the right questions (which the interviewer may not even suspect), and arrive at the most efficient solution.

L O A D I N G
. . . comments & more!