192 Data Engineer Interview Questions & Answers

Apache Parquet is an open, column-oriented file format built for analytical data. I would explain it as storing each row group as column chunks, with each column chunk divided into pages. This lets a query read only needed columns and use available statistics to skip data that cannot match a filter. Encoding and compression reduce storage and I/O, and Parquet supports nested data. It is great for large scans, but frequent row-level updates usually require rewriting files. Traditional algorithmic Big-O complexity does not apply here.

The question asks why Parquet is a good way to store data that we mostly read and analyze. Instead of keeping every field of one record together, Parquet organizes values by column inside groups of rows. This lets a query avoid reading information it does not need. Stored statistics can also help a reader skip data that cannot match a filter. Encoding and compression reduce storage and I/O. Parquet also supports nested data. The main tradeoff is that changing individual rows is not naturally cheap because Parquet is designed mainly for analytical reads.

1. Should I explain both the physical Parquet layout and the query-time benefits?
2. Should I also compare analytical scans with frequent row-at-a-time updates?

Apache Parquet is an open column-oriented file format. The diagram starts with tabular input containing the columns id, name, age, and country. When that data is written to Parquet, values for the same column are stored together within each row group instead of storing complete rows together.

A Parquet file is split into row groups. Each row group represents a set of rows. Inside each row group, there is one column chunk for each column. In the diagram, those chunks are id, name, age, and country. Each column chunk is divided into pages. Pages are smaller storage units that hold encoded values. The diagram shows 128 MB only as an example row-group size. It is not a required Parquet size.

Column projection means reading only the columns a query needs. The diagram shows a query that needs name and age. A reader can read those column chunks without reading id and country. This reduces the amount of data read from storage. It is especially useful when a table has many columns but a query selects only a few.

Parquet can store statistics such as minimum and maximum values for column chunks. Readers may use those statistics to skip row groups that cannot satisfy a filter. The diagram uses WHERE age > 30. From the visible input, David with age 32 matches. If the available statistics prove that a row group cannot contain an age above 30, the reader can skip that row group. When page-level metadata is available and supported by the reader, pages can also be skipped. This reduces unnecessary I/O.

Parquet supports encodings such as dictionary encoding and run-length encoding. It also supports compression codecs such as Snappy, GZIP, and ZSTD. Because values from the same column are stored together, encoding and compression can work efficiently. Parquet also supports nested structures such as arrays, maps, and structs. Its nested column representation uses definition and repetition levels.

The diagram places file metadata in the footer after the row-group data. The footer contains the schema and metadata about row groups and column chunks, including statistics when they are written. Readers first use this metadata to locate the column chunks they need. Column projection, statistics-based skipping, encoding, and compression can therefore reduce the amount of data read and processed during analytical scans.

Parquet is not automatically ideal for row-at-a-time transactional updates. It is a file format designed for efficient analytical reads of columnar data. Changing or deleting individual rows often means rewriting affected Parquet data files or using a higher-level table format that manages those changes. Parquet therefore fits read-heavy analytical workloads better than workloads that constantly modify individual rows.

This is a storage-format concept rather than a coding algorithm. The key idea is the Parquet hierarchy: a file contains row groups, each row group contains one column chunk for every column, and each column chunk contains pages. The central invariant is that values for the same logical column are grouped together within a row group. That layout lets readers project only required columns. Available statistics can also help readers skip row groups or pages that cannot satisfy a predicate. Encoding and compression reduce stored and transferred bytes. The tradeoff is that this layout favors analytical scans rather than frequent individual-row changes.

Traditional algorithmic Big-O time and auxiliary-space complexity do not meaningfully apply because the question describes a file format, not an algorithm with a fixed input-processing procedure. The practical cost is the amount of data read, decoded, and decompressed. Column projection can reduce that work by reading only needed columns. Statistics can reduce it further by skipping data that cannot match a filter. Compression reduces bytes read from storage but requires CPU work to decompress them. Row-level changes may be expensive because affected Parquet files often need to be rewritten.

1. Saying Parquet stores complete rows together. It uses a column-oriented layout within row groups.
2. Confusing a row group with a column chunk. A row group contains one chunk for each column, while a column chunk contains values for one column in that row group.
3. Claiming statistics are always present or that every reader always performs the same data skipping. Statistics can be optional, and skipping depends on available metadata and reader support.
4. Treating the diagram's 128 MB row-group size as a Parquet requirement. It is only an example size.
5. Saying Parquet is naturally efficient for frequent row-by-row updates. Those changes commonly require rewriting affected files or using a higher-level table layer.

Explain Parquet in one simple chain: file to row groups, row groups to column chunks, and column chunks to pages. Then connect that layout to column projection, statistics-based skipping, encoding, compression, nested data, and the row-update tradeoff.

Protocol Buffers are a language-neutral and platform-neutral way to serialize structured data. I define messages and fields in a .proto schema, give every field a stable numeric identifier, generate language-specific code, and serialize message objects into compact binary bytes. A compatible consumer can deserialize those bytes even when it uses another supported language. Stable field numbers, unknown-field handling, and careful schema evolution provide backward and forward compatibility. For an encoded message of n bytes, serialization and deserialization take O(n) time and O(n) output or parsed-message space.

Protocol Buffers let different programs agree on the structure of data before they exchange it. The agreement is stored in a .proto schema. In the diagram, the schema defines a User record with an ID, name, and email. Each field also has a number that stays stable over time. A compiler generates code for different programming languages. The producer fills a generated User object and converts it into binary bytes. The consumer reads those bytes using compatible generated code. This design supports compact data exchange and safe schema changes when field-number rules are followed.

1. Should I focus only on the schema and wire format, or also explain generated code?
2. Do you want me to explain backward and forward compatibility separately?
3. Should I compare Protocol Buffers with an analytical file format such as Parquet?

The diagram starts with user.proto. It uses proto3 syntax and the package tutorial. It defines one User message. The fields are int64 id = 1, string name = 2, and string email = 3.

A message is the structured record being exchanged. A field is one value inside that message. The numbers 1, 2, and 3 are numeric field identifiers. They are part of the binary wire contract. Existing field numbers must keep the same meaning and should never be reused for a different field.

The .proto schema is passed to the Protocol Buffers compiler, protoc. The diagram shows generated bindings for Python, Java, Go, and C++. Each generated API represents the same User schema in its own language.

This allows a producer and consumer to use different supported languages while still agreeing on the message structure. The schema is the shared contract between them.

The Python example imports User from user_pb2. It creates a message and sets id = 123, name = "alice", and email = "alice@example.com".

Calling SerializeToString() converts that structured message into binary bytes. The exact bytes shown in the diagram are 08 7B 12 05 61 6C 69 63 65 1A 11 61 6C 69 63 65 40 65 78 61 6D 70 6C 65 2E 63 6F 6D.

Protocol Buffers encode fields using wire-format tags derived from the numeric field identifier and wire type. Field names such as name and email are not stored as a complete embedded schema in every serialized message.

The producer can send the binary bytes over a network or store them. The consumer receives the same bytes and uses compatible generated code to reconstruct the message.

In the diagram, the Python consumer creates User() and calls ParseFromString(binary_data). Reading the fields then gives 123, alice, and alice@example.com.

The producer and consumer do not have to use the same programming language. They need compatible schema definitions and generated bindings that understand the same field numbers and wire types.

Backward compatibility means newer code can read data written using an older compatible schema. If a new scalar field was added later, that field is simply absent from older messages and exposes its default value when read.

Forward compatibility means older code can read data written using a newer compatible schema. Fields that the older code does not recognize are treated as unknown fields. Compatible protobuf runtimes can skip those fields while parsing and preserve them when the message is serialized again.

The main schema-evolution rule is simple. Add new fields with new field numbers. Never reuse an existing field number for a different meaning.

Protocol Buffers are designed mainly for efficient serialization and data exchange. Their serialized binary messages do not contain a complete self-describing analytical schema that an arbitrary analytics tool can discover and query directly. A consumer normally needs the schema definition, generated code, or equivalent descriptors to interpret the data correctly.

Parquet serves a different purpose. It is a column-oriented analytical file format that stores schema information with the file and is designed for efficient analytical reads. Protocol Buffers are therefore well suited to message exchange, while Parquet is better suited to analytical storage and querying.

Let n be the number of bytes in the encoded message. Serialization takes O(n) time because the data must be encoded. Deserialization also takes O(n) time because the encoded bytes must be read. The serialized byte string uses O(n) output space, and the parsed message requires memory proportional to the data it contains.

Important edge cases are unknown fields, fields that are absent in older messages, and incompatible schema changes such as changing the meaning of an existing field number.

The key idea is schema-driven serialization. The .proto file is the shared data contract. Each field has a type, a name, and a stable numeric field identifier. protoc generates language-specific bindings from that contract. A producer fills a generated message object and serializes it into binary bytes. A consumer uses compatible bindings to deserialize those bytes. The central invariant is that an existing field number keeps the same meaning across compatible schema versions. This stable numeric mapping allows old and new readers to identify known fields while safely handling fields they do not understand.

Let n be the number of bytes in the encoded Protocol Buffers message. Serialization takes O(n) time because the message data must be encoded into bytes. Deserialization also takes O(n) time because those bytes must be read and decoded. The serialized byte string requires O(n) output space. A parsed message also needs memory proportional to the values stored in that message. These costs depend on the message size, not on how many programming languages can use the schema.

A common mistake is treating field names as the stable wire identity. Numeric field identifiers are the important part of the binary contract. Another mistake is changing or reusing an existing field number during schema evolution. Candidates also sometimes think that an older reader must fail when it sees a new field. Compatible readers can skip unknown fields and preserve them through normal binary parse-and-reserialize flows. Another mistake is calling Protocol Buffers self-describing in the same way as Parquet. A protobuf message does not carry the complete analytical schema needed to interpret itself independently.

Explain Protocol Buffers as one simple flow: define the schema, generate code, create the message, serialize it to bytes, and deserialize it on the consumer. Then emphasize that stable numeric field identifiers are the key to safe schema evolution. Use the diagram's User example before discussing compatibility and the difference from Parquet.

I would validate the password in one left-to-right pass. First, I reject a length below 6 or above 100. Then I keep four Boolean flags for lowercase, uppercase, digit, and special character. For each character, a normal space returns false immediately. Otherwise, I update the matching flag or reject a character outside the allowed set. After the scan, I return true only if all four flags are true. This takes O(n) time and O(1) auxiliary space.

The input is one password with 0 to 100 characters. A secure password needs at least six characters. It must contain at least one lowercase letter, one uppercase letter, one digit, and one character from !@#$%^&*()_. An ordinary space makes it invalid. The example "FooBar123!" is valid because it meets every rule. The other supplied examples either miss a required character type or contain a space. We can check every rule while moving through the password from left to right and storing only four yes-or-no values.

1. Should characters outside English letters, digits, ordinary spaces, and !@#$%^&*()_ be rejected defensively if they appear?
2. Should the function stop immediately when it finds an ordinary space or another invalid character?

The input is one string named password. Its stated length is from 0 to 100 characters. The stated input characters are English letters, digits, ordinary spaces, and the special characters !@#$%^&*()_.

The function returns a Boolean value. It returns True only when the password has length at least 6, contains at least one lowercase letter, at least one uppercase letter, at least one digit, at least one listed special character, and contains no ordinary space. Empty and too-short passwords return False.

The diagram also checks the upper length limit of 100 and defensively rejects a character outside the stated input set.

First, get the password length. If it is below 6 or above 100, return False immediately.

Then create four Boolean flags: lower, upper, digit, and special. All four start as False. Each flag records whether its required character type has appeared so far.

The central invariant is that after each processed character, these four flags correctly describe which required character types have appeared in the processed prefix of the password.

For every character, first test whether it is an ordinary space. If it is, return False immediately because spaces are forbidden.

Otherwise, classify the character. A character from a through z sets lower to True. A character from A through Z sets upper to True. A character from 0 through 9 sets digit to True. A character contained in !@#$%^&*()_ sets special to True.

If the character belongs to none of those groups, the diagram defensively returns False because it is outside the stated character set.

For "FooBar123!", the length is 10, so the length check passes. The four flags begin as False.

F is uppercase, so upper becomes True. The lowercase letters make lower become True. The digits 1, 2, and 3 make digit become True. The final ! is in the listed special-character set, so special becomes True.

No ordinary space or invalid character is found. At the end, all four flags are True, so the function returns True.

The supplied failing examples follow the same rules. "foobar123!" has no uppercase letter, so it returns False. "FooBar123" has no listed special character, so it returns False. "F0bar! F0bar!" contains an ordinary space, so the function stops at that space and returns False.

Each flag records whether its required character type has appeared in the portion of the password already processed. Once a flag becomes True, it can remain True because seeing more characters cannot remove an earlier match.

A forbidden ordinary space causes an immediate False. The defensive branch also returns False for a character outside the stated input set. Therefore, reaching the final return means no forbidden character has been accepted.

The final expression returns True only when lower, upper, digit, and special are all True. That exactly matches the required character policy.

The Python code follows the diagram directly. It checks the length first, initializes four flags, and then scans the string from left to right. The if and elif conditions classify each character and update the appropriate flag. A space or unsupported character returns False immediately. After the loop, the function returns the logical AND of the four flags.

Let n be the number of characters in the password. The function processes the input at most once, so its time complexity is O(n). It stores only a fixed number of variables, so its auxiliary space complexity is O(1).

Important cases are an empty password, a password shorter than six characters, a password missing one required character type, and a password containing an ordinary space. The diagram also rejects a password longer than 100 characters and defensively rejects characters outside the stated input set.

The key idea is to check all password requirements during one left-to-right scan instead of making separate scans for lowercase letters, uppercase letters, digits, and special characters. Four Boolean flags store whether each required character type has appeared. The invariant is that after every processed character, lower, upper, digit, and special correctly describe the processed prefix. A space or an out-of-domain character returns False immediately. If the scan finishes, the logical AND of the four flags gives exactly the required result.

Let n be the password length. We process the input at most once, so the time complexity is O(n). The function stores only the length and four Boolean flags. The number of stored variables does not grow with n, so the auxiliary space complexity is O(1). An invalid length, ordinary space, or unsupported character may make the function return earlier, but O(n) is still the worst-case time complexity.

A common mistake is checking the four required character types but forgetting that an ordinary space must return False. Another mistake is using a broader character test that does not preserve the exact English-letter and listed-special-character policy. Candidates may also forget the minimum length check, use the wrong special-character set, or return True as soon as all four flags become true. That early success would be incorrect because a later space could still invalidate the password. Another mistake is claiming more than O(1) auxiliary space even though this implementation uses only fixed-size state.

Explain the four Boolean flags before writing the loop. Also point out why the function may return False early but should not return True early when all four flags become true: a later ordinary space could still invalidate the password. That shows the interviewer that you understand the stopping condition.

I would process the string from left to right and build the answer in a Python list used like a stack. Before I append each character, I check whether the last two kept characters are already equal to it. If they are, I skip the current character. Otherwise, I keep it. This preserves the original order and removes only characters beyond the first two in each run, so the deletions are minimum. The solution takes O(n) time and O(n) space.

The input is a string of lowercase English letters. We need to delete as few characters as possible so that no three equal characters remain next to each other. We cannot change the order of the characters we keep. A run of one or two equal letters should stay unchanged. The main idea is to build the answer from left to right. We keep each character unless it would become the third equal character in a row. A Python list works well because we can inspect the last two kept characters before adding the next one.

1. Should I preserve the original order of every character that remains?
2. Should runs of one or two equal characters remain unchanged?
3. Is O(n) output storage acceptable for the returned string?

The function receives a string named text containing 1 to 200000 lowercase English letters. The result must be created only by deleting characters. The order of all retained characters must remain unchanged. The returned string must contain no run of three identical adjacent characters, and the number of deletions must be as small as possible.

I use a Python list named result as a stack-like output buffer. The key invariant is that result always contains the retained characters in their original order and never contains three identical adjacent characters. Before adding a new character, I inspect the last two characters already in result. If both are equal to the current character, adding it would create a forbidden triple, so I skip it. Otherwise, I append it.

Start with result as an empty list. Process text from left to right. For each character ch, first check whether result has at least two characters and whether result[-1] and result[-2] both equal ch. If that condition is true, continue skips ch. If it is false, result.append(ch) keeps the character. Because every accepted character is checked before it is added, the invariant remains true after every step.

The example input is "eedaaad". Start with result = []. Read the first "e" and append it, so result becomes "e". Read the second "e" and append it, so result becomes "ee". Read "d" and append it, giving "eed". Read the first "a" and append it, giving "eeda". Read the second "a" and append it, giving "eedaa". The next character is another "a". The last two kept characters are already "a" and "a", so this third "a" is skipped and result stays "eedaa". Finally, append "d", giving "eedaad". The function returns "eedaad".

Whenever a run contains more than two equal adjacent characters, every character beyond the first two must be deleted from that run. Otherwise, at least three equal adjacent characters would remain. The algorithm deletes exactly those extra characters and keeps the first two. It never removes a character from a run of length one or two. Therefore, it satisfies the rule with the minimum possible number of deletions while preserving character order.

The Python code performs the same left-to-right process shown in the diagram. Each input character is examined once, so the time complexity is O(n). The result list can grow to O(n) characters, so the space complexity is O(n). A one-character string and a two-character run remain unchanged. A run of exactly three keeps its first two characters. Longer runs also keep only their first two characters. Equal letters separated by other letters are handled independently and are allowed.

Use a greedy left-to-right scan with a Python list used as a stack-like result buffer. The central invariant is that result contains the retained prefix in original order and never contains three identical adjacent characters. For each character, check the last two retained characters before appending. If both already equal the current character, skip the current character because keeping it would create a triple. Otherwise, append it. This greedy choice is optimal because in every run longer than two, each character beyond the first two must be deleted. The algorithm deletes exactly those necessary characters and no others.

Let n be the length of the input string. We process each character once, and each check of the last two list elements is constant time, so the total time is O(n). The result list can hold up to n characters, so it uses O(n) space. The final returned string can also contain up to n characters.

One common mistake is removing every repeated character instead of keeping the first two characters in each run. Another is checking neighbors in the original input instead of checking the last two characters already retained in result. A candidate may also append the current character before testing whether it creates a triple, which makes the invariant harder to maintain. Reordering characters is also incorrect because the result must be produced only by deletion. Finally, claiming O(1) space is incorrect for this implementation because the result list can grow with the input size.

State the invariant before you code: the result built so far keeps the original order and never contains three identical adjacent characters. Then explain that a character is skipped only when it would become the third equal character in the current run.

I would keep committed data in one hash map and active transactions in a stack of write maps. A begin pushes an empty map, so I never copy the full database. A set writes only to the top transaction. A get searches from the innermost transaction outward, then checks committed data. Rollback pops one level. Commit applies levels from outermost to innermost so deeper writes win, then clears all levels. begin, rollback, and count are O(1), set is expected O(1), get is O(d), commit is O(W), and space is O(P + W + d).

The function receives up to 200000 token-array operations and returns one string for every operation. Some writes are temporary because they belong to open transactions. A temporary write becomes permanent only after commit. A rollback removes only the newest open transaction. Reads must always see the newest visible value. The main idea is to keep permanent values separate from pending values. Each transaction gets its own write map, so begin does not copy the permanent database.

1. Should commit publish every active transaction level and close all of them? In this problem, yes.
2. Should count ignore every pending transaction write and count only permanent keys? In this problem, yes.
3. Can a key or stored value equal "NULL"? No. This means "NULL" can safely represent a missing key.

The input is a list of token-array operations. The supported commands are begin, set, get, rollback, commit, and count. The function returns exactly one string for every operation. Successful begin, set, rollback, and commit operations return "OK". get returns the newest visible value or "NULL" if the key is absent. count returns the permanent-key count as a decimal string. If set, rollback, or commit is called without an active transaction, it returns "ERROR: No active transaction" and changes nothing.

Use permanentData as one hash map for committed values. Use transactions as a stack of hash maps. Each stack entry stores only the writes made in one active transaction level. The last stack entry is the innermost transaction. The central invariant is that each pending write belongs only to its own transaction level, while reads always choose the newest visible write.

For begin, append a new empty write map to transactions. This does not copy permanentData. For set, first check whether a transaction exists. If not, return the required error without changing state. Otherwise, write the key and value only into transactions[-1].

For get, search the transaction maps from innermost to outermost. Stop at the first map containing the key because that is the newest visible pending value. If no active transaction contains the key, read permanentData. If the key is absent there too, return "NULL".

For rollback, require an active transaction and pop only the innermost map. For commit, require at least one active transaction. Apply transaction maps from outermost to innermost into permanentData. This order is important because an inner write to the same key must overwrite an outer write. After publishing all levels, clear the transaction stack. For count, return the number of keys in permanentData as a decimal string, so pending writes are excluded.

The database starts with permanentData = {} and no transactions. begin creates Level 1 and returns "OK". set color blue stores color = blue only in Level 1 and returns "OK". A second begin creates Level 2 and returns "OK". set color green stores color = green only in Level 2 and returns "OK".

get color searches Level 2 first, finds green, and returns "green". rollback removes only Level 2 and returns "OK". Now get color searches Level 1 and returns "blue". count returns "0" because permanentData is still empty. commit publishes Level 1 into permanentData, clears all active transaction levels, and returns "OK". The final count returns "1". The exact output is ["OK", "OK", "OK", "OK", "green", "OK", "blue", "0", "OK", "1"].

Each pending write stays in the transaction level where it was created. A read checks transaction levels from newest to oldest, so it always sees the most recent visible pending value. Rollback removes only the newest level, which can reveal an older value again. Commit applies outer levels before inner levels, so deeper writes overwrite shallower writes. permanentData changes only during commit, so count correctly excludes every pending write.

The function creates permanentData, transactions, and result. Python dictionaries hold key-value writes. A Python list acts as the transaction stack. append creates a new innermost level, pop removes the innermost level, and reversed(transactions) gives the required get search order. During commit, iterating transactions in normal order applies outermost levels first and innermost levels last. Each input operation appends exactly one output string.

begin is O(1). set uses one hash-map assignment, so it is expected O(1). rollback is O(1). count is O(1). A get may inspect all d active transaction levels, so it performs O(d) map lookups in the worst case across those levels. A commit applies every pending key-value entry, so it is O(W), where W is the number of pending entries applied. Auxiliary space is O(P + W + d), where P is the number of permanent keys. Important cases are a missing key, repeated writes to the same key at different levels, rollback exposing an outer value, and set, rollback, or commit with no active transaction.

Keep committed state and pending state separate. permanentData is a hash map containing only committed key-value pairs. transactions is a stack of hash maps, where each map stores writes for one active transaction level. begin pushes an empty map instead of copying the database. set changes only the top map. get searches from the innermost map to the outermost map and then checks permanentData. rollback pops one map. commit applies maps from outermost to innermost and then clears the stack. The invariant is that each pending write belongs only to its own level and lookup always uses the newest visible write. Applying commit from outermost to innermost preserves the same newest-write-wins rule because deeper writes overwrite shallower writes.

Let d be the number of active transaction levels, P be the number of permanent keys, and W be the number of pending key-value entries. begin is O(1). set is expected O(1) because Python dictionary insertion is O(1) on average. rollback is O(1). count is O(1). get may check up to d transaction maps, so it takes O(d) map lookups in the worst case across the active levels. commit processes every pending entry that must be published, so it takes O(W). Auxiliary space is O(P + W + d) for permanent keys, pending writes, and the transaction-level stack.

One mistake is copying the complete database on every begin, which violates the requirement and wastes memory. Another is letting set modify permanentData before commit. get must search transaction maps from innermost to outermost, not in the opposite direction. rollback must discard only one level, while commit must publish and close every active level. During commit, applying inner levels before outer levels would let older outer values incorrectly overwrite deeper values. count must read only permanentData. Also, set, rollback, and commit must return the exact no-active-transaction error without changing state.

Explain the visibility rule first: get searches the innermost transaction first and then moves outward. Once that invariant is clear, rollback and commit are easier to justify. Also state explicitly that begin pushes only an empty write map, so the solution avoids copying the full database.

I would build a hash map from each account number to its original balance, then process transfers in input order. A transfer is valid only when both accounts exist and its amount is no greater than the source account’s original balance. Accepted transfers never change balances. I append valid transfers and count their source accounts. The total expected time is O(A + T + S log S), and the auxiliary space is O(A + S), excluding the returned valid-transfer list.

We have account records and transfer records. Each account has an account number and an original balance. Each transfer has a source account, destination account, and amount. We keep a transfer only when both accounts exist and the amount fits within the source account’s original balance. Successful transfers do not reduce balances for later checks. We must preserve the input order of accepted transfers, count their distinct source accounts, and return up to ten most frequent sources using the required ranking rule.

1. If the source and destination account are the same account, should I still apply only the stated existence and original-balance checks? Under the stated rules, I would.
2. Should rejected transfers be omitted completely from the result and from source frequency counts? The stated contract says yes.
3. Should the returned top-source dictionary preserve the required ranking order? I would preserve that order in the returned dictionary.

The input contains accounts as (accountNumber, balance) and transfers as (fromAccountNumber, toAccountNumber, transferAmount). Account numbers are unique strings. Balances and amounts are nonnegative integers. We return three values: valid transfers in their original input order, the number of distinct source accounts among those valid transfers, and a dictionary containing at most ten source accounts ranked by count descending and then account number ascending. If no transfer qualifies, the result is [], 0, and {}.

I create a dictionary called balance_by_account. Each key is an account number. Each value is that account’s original balance. I build this dictionary once before scanning transfers. I never change it. This is the main invariant because the problem says every transfer must be checked independently against the source account’s original balance.

For each transfer, I check three conditions. The source account must exist. The destination account must exist. The transfer amount must be less than or equal to the source account’s original balance. If all three conditions are true, I append the transfer to valid_transactions and increment the count for its source account. Otherwise, I reject it. After either result, I continue to the next transfer until no transfers remain.

The account lookup is A1 -> 100, A2 -> 50, and A3 -> 200.

1. A1 -> A2, 70: both accounts exist and 70 <= 100, so accept it. Source counts become A1: 1.
2. A1 -> A4, 10: destination A4 does not exist, so reject it.
3. A2 -> A3, 60: both accounts exist, but 60 > 50, so reject it.
4. A3 -> A1, 150: both accounts exist and 150 <= 200, so accept it. Source counts become A1: 1, A3: 1.
5. A1 -> A3, 70: both accounts exist and 70 <= 100, so accept it. Source counts become A1: 2, A3: 1.

The valid transfers are [("A1","A2",70), ("A3","A1",150), ("A1","A3",70)]. There are 2 distinct source accounts. Ranking by count descending and then account number ascending gives {"A1": 2, "A3": 1}.

The account lookup always stores the original balances and is never mutated. Therefore, every transfer uses exactly the same original account data, so accepted transfers cannot affect later validation. A transfer is appended only after both account-existence checks and the source-balance check pass. Only accepted transfers increase source_count. Because transfers are processed and appended in input order, the valid-transfer output also preserves input order.

The Python code builds the account dictionary, scans all transfers, appends accepted transfers, and counts their sources. After the scan, len(source_count) gives the distinct-source count. It sorts the source-count pairs with the key (-count, accountNumber), keeps the first ten, and converts them to a dictionary in that ranked order. Building and validating takes O(A + T) expected time with average O(1) dictionary operations. Sorting S distinct accepted sources costs O(S log S). Total expected time is O(A + T + S log S). Auxiliary space is O(A + S), excluding the returned valid-transfer list.

The key idea is to separate transfer validation from balance updates because balances must never change. Build one hash map from account number to original balance. Then scan transfers in input order. For each transfer, use the map to verify that both account numbers exist and that the amount is no greater than the source account’s original balance. Append only accepted transfers and count only their source accounts. The central invariant is that the balance lookup always contains the original balances and is never mutated. After processing all transfers, sort source frequencies by descending count and ascending account number and keep the first ten.

Let A be the number of accounts, T the number of transfers, and S the number of distinct source accounts among accepted transfers. Building the account dictionary takes O(A) expected time. Checking all transfers takes O(T) expected time because dictionary membership and lookup are O(1) on average. Sorting S source-count entries takes O(S log S). Therefore, total expected time is O(A + T + S log S). The auxiliary space is O(A + S), excluding the returned list of valid transfers. Since every accepted source must be an existing account, S is at most A.

A common mistake is subtracting accepted amounts from account balances. That breaks the rule that every transfer uses the original source balance. Another mistake is checking only the source account and forgetting that the destination must also exist. Candidates may accidentally count rejected transfers in the source frequencies or reorder accepted transfers before returning them. Another common error is sorting source accounts only by frequency and forgetting the ascending account-number tie breaker. Finally, the empty qualifying case should naturally return [], 0, and {}.

State the invariant early: balance_by_account stores the original balances and is never mutated. That immediately explains why transfers are independent and prevents the most important implementation error.