The Karat Screen

Some Wayfair candidates get a Karat call instead of the HackerRank link. Karat is an outside service that supplies the interviewer, an engineer who runs the session for Wayfair. The hour starts with a short introduction, then about 20 minutes of scenario questions on system design, then 30 minutes of coding. Both blocks are time-boxed, so if you finish the design questions in twelve minutes, the coding half still starts on schedule and still stops after 30.

The coding half usually comes in one of two shapes. Sometimes a single prompt fills it. Other times a quick counting problem comes first and a harder question on the same kind of log follows, and the clock tends to run out on that second one. Have time and space complexity ready for every answer, because the interviewer asks for both.

The Wayfair angle

Finish the first problem in about ten minutes, complexity included, then state the second problem's approach before you write any of it. The coding half can keep handing out questions until the 30 minutes are gone, so a fast first answer is what gets you to the second. If the second turns out to be a dynamic-programming grid, say so in your first sentence and describe what one cell holds. One candidate did that, ran out of time with the last lines unwritten, and still got the onsite invitation.

How the half hour runs

The design block comes first and stays shallow. Reported scenarios ask whether a bank ledger or a click-analytics feed needs strong or eventual consistency, what happens to a document editor that routes traffic by id % num_instances when the instance count changes, and how to show a friend count beside every post. System design at Wayfair works through those. Not every sitting holds the split tightly. One senior candidate on a four-scenario version explained each answer at length, spent 30 minutes there, and had 25 left for the coding prompt.

Each coding prompt arrives with sample inputs and their expected outputs, and the samples settle rules the prose leaves open. The badge log's samples show one employee landing in both output lists. Other Wayfair rounds have scored output position by position, so decide the order your answer comes back in before you write the loop that emits it.

Asked at Wayfair

Four problems, the most reported first. The counter and the shared run arrive as a pair inside one half hour, so time them together, about ten minutes for the first and twenty for the second. The word grid and the badge log each came as the only coding prompt of their session.

1

Subdomain Visit Count: One Pass Up the Domain

EasyCommonly asked

Problem

A traffic log for Wayfair's storefronts arrives as a list of strings, each of the form " ". The entry "900 www.wayfair.com" means that domain served 900 visits.

A visit to www.wayfair.com is also a visit to wayfair.com and to com. So every entry adds its count to its full domain and to every suffix you get by dropping labels from the left, down to the last label on its own.

Return one " " string for each distinct domain or suffix, where is the summed visits as a plain integer. Order the output by first appearance. Walk the entries in input order, and inside each entry go from the full domain down to its last label. A domain takes its slot the first time that walk reaches it, and later counts add to it without moving it.

Expect at most 100 entries, each count between 1 and 10^4. Domains are lowercase letters separated by single dots, with no leading or trailing dot.

Inputcpdomains = ["900 www.wayfair.com","50 www.allmodern.com","1 birchlane.com","5 wayfair.co.uk"]Output["900 www.wayfair.com","900 wayfair.com","951 com","50 www.allmodern.com","50 allmodern.com","1 birchlane.com","5 wayfair.co.uk","5 co.uk","5 uk"]

com collects 900 + 50 + 1 = 951 but keeps the third slot, the one the first entry gave it. The UK storefront counts toward co.uk and uk like any other suffix, with no special case for a two-part country ending.

Inputcpdomains = ["20 wayfair.com","7 m.wayfair.com","3 com"]Output["27 wayfair.com","30 com","7 m.wayfair.com"]

m.wayfair.com is the newest name, so it lands last. Its parent already holds slot one and com holds slot two, and both just absorb the extra visits.

Inputcpdomains = ["4 com"]Output["4 com"]

A single label has no suffix to climb to. The loop must count it once and stop.

How this uses the pattern

Keep an insertion-ordered map from domain to running total. For each entry, split off the count, then add it to the domain, cut everything up to the first dot, and repeat until no dot is left.

Subdomain Visit Count: One Pass Up the Domain

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (11)

Need a hint? (3 available)

The Wayfair angle

Wayfair sells through a family of storefront domains, wayfair.com beside allmodern.com, birchlane.com, perigold.com and the UK and Canada sites, and this counter rolls visits up by domain. On the Karat screen this counter is reported as the opener of the 30-minute coding half, with a longest common run as the harder second question, and that second question is where the clock runs out. Bank this one in about ten minutes, time and space complexity included, since the interviewer asks for both. Output order is the cheap mistake. Other Wayfair rounds have failed correct values for coming back in the wrong order, so keep an insertion-ordered map and emit each domain where it was first seen.

Take it further

A natural extension ranks the traffic. Return only the k busiest domains, highest total first, with a tie keeping the first-seen slot, so the first sample with k = 2 gives ["951 com","900 www.wayfair.com"]. The counting pass stays exactly as it is, and a stable sort on descending totals settles the ties without a second key, while heapq.nlargest returns the same order in O(m log k) when k is small. Go's sort.Slice and C++'s std::sort are not stable, so reach for sort.SliceStable or std::stable_sort there, and the longest common run that tends to follow on the screen is the next problem below.

Show solution & walkthrough

2

Longest Common Run: Two Users' Event Lists

MediumCommonly asked

Problem

Two shoppers' sessions on Wayfair arrive as lists of page paths, user1 and user2, each in the order that shopper visited them. Find the longest run of pages that appears in both lists back to back and in the same order, with no other page between them in either list. Pages match on exact string equality.

Return that run as a list of page paths. When several runs tie for the longest, return the one that starts earliest in user1. When the lists share no page at all, return an empty list []. Either list may be empty.

Inputuser1 = ["/", "/sofas", "/sofas/sectionals", "/rugs", "/cart", "/checkout"]user2 = ["/", "/lighting", "/rugs", "/cart", "/checkout", "/sofas"]Output["/rugs", "/cart", "/checkout"]

Both shoppers went rugs, cart, checkout without a detour. The home page and the sofas page are shared too, but each one is a run of a single page.

Inputuser1 = ["/sofas", "/rugs", "/lamps", "/cart"]user2 = ["/sofas", "/lamps", "/rugs", "/cart"]Output["/sofas"]

No pair of neighbouring pages in user1 shows up back to back in user2, so every shared run is one page long and the tie goes to the earliest start in user1. A subsequence answer would report three pages, sofas, rugs, cart, by skipping over lamps.

Inputuser1 = ["/beds"]user2 = ["/rugs", "/lamps"]Output[]

Nothing is shared, so the answer is the empty list and no page gets returned by default.

How this uses the pattern

Fill a grid where each cell holds the length of the shared run ending at one position in each list. A match extends the diagonal neighbour by one, a mismatch resets the cell to zero, and the largest cell tells you where the answer ends.

Longest Common Run: Two Users' Event Lists

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (12)

Need a hint? (3 available)

The Wayfair angle

On a Karat screen for Wayfair this tends to come second, after Subdomain Visit Count, in a coding half of about 30 minutes that cannot borrow time from the design questions before it. Candidates describe getting most of the way and running out of clock. The prompt reads as two shoppers' page-visit logs, the url-visits shape some screens use, and the shared run has to be unbroken in both. If one shopper goes sofas, rugs, lamps and another goes sofas, lamps, the contiguous answer is one page long while a subsequence answer reports two. Name the dynamic-programming grid before you type, return the pages themselves, and have both costs ready, since the Karat interviewer asks for time and space.

Take it further

Keep the running time at O(n * m) but hold a single row of the grid, so memory falls to O(m). Each cell reads only its upper-left neighbour, which means sweeping j from right to left lets one array act as the previous row and the current row at once. A mismatch now has to write the zero explicitly, because the array still holds a number from the row above in that slot.

Show solution & walkthrough

3

Word Search: Right and Down Only, Returning the Path

MediumCommonly asked

Problem

A letter grid board arrives as a 2D array of single uppercase characters, along with a word. Spell word by starting on any cell that holds its first letter and moving to the next letter each time, where every step goes one cell right (r, c + 1) or one cell down (r + 1, c). Moving up or left is never allowed.

Return the path as a list of [row, col] pairs, one per letter of word, in spelling order. Return [] when the word cannot be spelled this way.

When several paths spell the word, return the first one a fixed search order finds: try start cells in row-major order, and from every cell try right before down. Assume 1 <= rows, cols <= 10 and 1 <= len(word) <= 20.

Inputboard = [["S","O","X"],["Q","F","A"],["Z","R","A"]]word = "SOFA"Output[[0,0],[0,1],[1,1],[1,2]]

S, then right to O, down to F, right to A. The second A at (2,2) sits below the first one and never gets a look, because the path is complete as soon as the last letter lands.

Inputboard = [["L","A","M","Q"],["A","M","X","Z"],["Q","P","Z","Z"]]word = "LAMP"Output[[0,0],[0,1],[1,1],[2,1]]

Right-first reaches the M at (0,2), but neither neighbour of that M is a P. That cell has to come back off the path before the search drops to the M at (1,1) and finds the P below it.

Inputboard = [["A","B"],["C","D"]]word = "BA"Output[]

The only A sits to the left of the only B. A four-direction solution would happily return [[0,1],[0,0]], which breaks the movement rule.

How this uses the pattern

Depth-first search from each start cell with one shared path list. Append a cell when its letter matches, recurse right and then down, and pop the cell when both branches fail.

Word Search: Right and Down Only, Returning the Path

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (16)

Need a hint? (3 available)

The Wayfair angle

Wayfair's Karat screen spends its first stretch on quick system-design questions, then hands over a coding problem. A twist on LeetCode's Word Search has come up more than once. You may only step right or down, and you return the route itself. The first rule helps you. A walk that only travels right and down can never come back to a cell it used, so the visited set goes away and each call branches two ways. The second rule is where people come unstuck. Append the cell before you recurse and pop it on every dead end, or the list you return still carries cells from branches that failed.

Take it further

Lift the direction limit and allow all four moves, as in the original LeetCode problem. A path can now loop back onto a cell it already spelled with, so a visited grid returns. Mark the cell before recursing and clear it on the same line as the path pop. Trying right, down, left and up in that fixed order keeps the returned route unique.

Show solution & walkthrough

4

Badge Access Records: Enters Without Exits

MediumSometimes asked

Problem

A security system guards a badged-access room in the office. Every swipe lands in an ordered log, given to you as a list of [name, action] pairs where action is "enter" or "exit".

Two rules frame the log. The room is empty when the log begins, and every employee must leave before the log ends. Return two collections:

- Employees who entered without a matching exit. An "enter" from someone already inside means their earlier entry never got its exit, and anyone still inside when the log ends owes one too.
- Employees who exited without a matching enter, meaning an "exit" from someone who is not inside at that moment.

A record that breaks a rule leaves the employee where they were. A second "enter" keeps them inside, and an unmatched "exit" keeps them outside.

Each collection holds a name at most once, however many times that employee breaks the rule, and one employee can sit in both. Return [enteredWithoutExit, exitedWithoutEnter] with each list sorted alphabetically by character code. Names are ASCII letters and case-sensitive. Aim for a single pass over the n records.

Inputrecords = [["Raj","enter"],["Paul","enter"],["Paul","exit"],["Paul","exit"],["Paul","enter"],["Raj","enter"]]Output[["Paul","Raj"],["Paul"]]

Paul's second exit comes while he is outside, so he owes an enter. He walks back in and the log stops with him inside, so he owes an exit as well. Raj swipes in twice without leaving.

Inputrecords = [["Paul","enter"],["Paul","enter"],["Paul","exit"],["Paul","exit"]]Output[["Paul"],["Paul"]]

The second enter flags the first one as unclosed and Paul stays inside. The first exit matches, and the second finds him already out. Four records put one employee in both lists.

Inputrecords = [["Paul","enter"],["Pauline","exit"],["Paul","enter"],["Paul","exit"],["Martha","exit"],["Joe","enter"],["Martha","enter"],["Steve","enter"],["Martha","exit"],["Jennifer","enter"],["Joe","enter"],["Curtis","exit"],["Curtis","enter"],["Joe","exit"],["Martha","enter"],["Martha","exit"],["Jennifer","exit"],["Joe","enter"],["Joe","enter"],["Martha","exit"],["Joe","exit"],["Joe","exit"]]Output[["Curtis","Joe","Paul","Steve"],["Curtis","Joe","Martha","Pauline"]]

Steve and Curtis are still inside when the log stops, so neither double-swiped and both still owe an exit. Martha exits from outside twice and Joe double-enters twice, yet each name appears once.

How this uses the pattern

Keep a set of who is inside right now, starting empty. Each record either moves an employee across the door or breaks a rule, and a broken rule adds the name to one of two output sets without moving anyone.

Badge Access Records: Enters Without Exits

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (13)

Need a hint? (3 available)

The Wayfair angle

One senior-level phone interview at Wayfair gave this badge log twenty minutes, squeezed between a five-minute introduction and fifteen minutes of system design questions. The prompt arrived with four sample logs and their expected output, and those samples carry the rules. Paul lands in both lists from just four records, and Martha exits from outside twice yet appears once. The two rules also differ at the edges, since the room starts empty and has to end empty, so whoever is still inside when the log stops owes an exit. Twenty minutes leaves no slack for pairing events up afterwards. Keep one inside-or-outside state per employee and settle every record as it arrives.

Take it further

A natural extension drops the alphabetical sort. Each name goes in the order that employee first broke a rule, and anyone still inside at the end follows, in the order they last walked in. Other Wayfair rounds have scored output position by position, so the change is worth having ready. Swap every set for an insertion-ordered one. Append a name the first time it qualifies, and let an exit delete the employee from the inside map, so a fresh entry re-inserts them at the back.

Show solution & walkthrough