Make It Faster Than O(n squared) round·Engineering·Hard·20 min

TCS Digital Software Engineer — Make It Faster Than O(n squared)

20 min · 1 credit · scorecard at the end

ZeroPitch Research Desk

Updated 2026-06-09 · Newly added · be among the first to take it

Field: Engineering
Company: Tata Consultancy Services
Role: Digital Software Engineer Trainee
Duration: 20 min
Difficulty: Hard
Completions: New
Updated: 2026-06-09

What this round is about

Topic focus. Two coding problems, one solved with a hash map and one with two pointers or a sliding window, the three patterns that turn an O(n squared) brute force into O(n).
Conversation dynamic. You state the obvious brute force and its complexity first, then the interviewer pushes you to make it faster and to justify why the faster version is correct.
What gets tested. Whether you can reason about time and space complexity out loud, not just whether your code runs.
Round format. A twenty minute technical round with problem cards in front of you and a whiteboard for tracing pointer and window movement.

What strong answers look like

Brute force stated first. You describe the nested-loop approach and say its complexity is O(n squared) before writing the optimal one.
Named trade-off on the pivot. When asked to go faster you say something like, I will use a hash map for extra space to get constant-time lookups and bring this to O(n).
Correctness defended. You explain why the window stays valid as the left pointer advances, or how the hash map handles collisions and why lookups are constant on average.
Whiteboard trace. You trace a short example, showing the left and right pointers or the running sum changing across the array.

What weak answers look like (and how to avoid them)

Memorised optimal, no brute force. Jumping straight to the trick with no complexity stated hides whether you understand it, so always lead with the brute force.
Wrong complexity claim. Calling a nested-loop solution linear loses trust fast, so count your loops before you name a big-O.
Hash map with no collision story. Using a map but going blank on collisions reads as rote learning, so be ready with one clear sentence.
Silent when stuck. Staring instead of tracing an example stalls the round, so draw a tiny case and reason from it.

Pre-interview checklist (2 minutes before you start)

Recall the three patterns. Have hashing, two pointers, and sliding window ready as your go-to ways to remove a nested loop.
Have a brute force reflex. For any array or string problem, be ready to state the nested-loop version and its O(n squared) cost first.
Identify the sortedness cue. Notice when an array is sorted, because that is the signal for opposite-ends two pointers.
Pull up your collision sentence. Be able to say in one line how a hash map handles collisions and why average lookups are constant.
Think of a window-validity line. Be ready to explain why a sliding window does not skip a valid answer when the left pointer moves.

How the AI behaves

Probes every complexity claim. It asks you to justify any big-O you state and checks it against the loops you wrote.
No mid-interview praise. It will not say great answer; it acknowledges the specific thing you said and pushes on.
Interrupts on a memorised jump. If you skip to the optimal solution it pulls you back to state the brute force and its cost first.
Asks one thing at a time. It waits for your full response before following up, the way a real panel engineer does.

Common traps in this type of round

Linear claim on quadratic code. Saying O(n) while running nested loops over the array.
Trade-off left unspoken. Reaching the hash-map solution but never saying you are spending space to save time.
Collision blank. Relying on a hash map but having nothing to say about how collisions are handled.
Window asserted, not justified. Writing a sliding window but unable to say why it stays valid as it slides.
Coding before clarifying. Writing code before restating the problem and confirming the example input and output.

Sample problems you'll face

The 2 problems below are the same ones you'll work through in the live session — no surprises. Read the constraints carefully; the AI persona will refer you to the on-canvas card by problem number.

1Two Sum in an Unsorted Array (hashing)
Given an unsorted array of integers and a target value, return the indices of the two numbers that add up to the target. Start by describing the brute-force approach and its time complexity, then optimise when asked. The optimal solution uses a hash map to remember values you have already seen, trading O(n) extra space for O(n) time instead of the O(n squared) nested-loop scan.
Example inputnums = [2, 7, 11, 15], target = 9
Example output[0, 1] (because nums[0] + nums[1] = 2 + 7 = 9)
- Array is not sorted, so opposite-ends two pointers do not directly apply without sorting first.
- Exactly one valid pair exists; you may not reuse the same index twice.
- Be ready to explain how the hash map handles collisions and why average lookup is treated as constant time.
- On the whiteboard, write the array out and mark each value as you insert it into the hash map, showing the lookup that finds the complement.
2Longest Substring Without Repeating Characters (sliding window)
Given a string, find the length of the longest substring that contains no repeating characters. State the brute-force approach of checking every substring and its complexity first, then optimise. The optimal solution is a variable sliding window with a hash set: the right pointer adds the incoming character, and when a duplicate appears the left pointer advances until the window is valid again, giving O(n) time.
Example inputs = "abcabcbb"
Example output3 (the longest substring without repeating characters is "abc")
- The brute force checks every substring for uniqueness and is O(n squared) or worse; the window must beat it.
- Be ready to explain why advancing the left pointer past a duplicate never skips a longer valid substring.
- If asked the sorted-array variant instead, explain which pointer moves when the running sum is too small versus too large.
- On the whiteboard, trace the left and right pointers across the string, showing the window contents and the running best length at each step.

Interview framework

You will be scored on these 6 dimensions. The full rubric with definitions is below.

Brute-force Articulation

Whether you state the obvious nested-loop approach and put a complexity on it before optimising, instead of jumping to the trick.

15%

Optimisation Pivot

Whether you reach the hashing, two-pointer, or sliding-window pattern when pushed, and say out loud the space-for-time trade-off you are making.

25%

Complexity-claim Accuracy

Whether the big-O you state actually matches the loops you wrote, both for the brute force and the optimised version.

20%

Correctness Justification

Whether you explain why the optimised solution is right, such as window validity or hash collision handling, not just that it runs faster.

20%

Whiteboard Trace Quality

Whether your drawing of pointers or the running window tracks your spoken logic step by step on the example.

12%

Pattern Self-awareness

Whether you can name which pattern you find hardest to spot and a concrete habit that would help you catch it faster.

What we evaluate

Your final scorecard breaks down across these dimensions. The full rubric and tier criteria are revealed inside the interview itself.

Common questions

What does the TCS Digital coding round actually test?

It tests whether you can move from a brute-force solution to an optimal one and reason about complexity out loud. The interviewer gives you a hashing problem and a two-pointer or sliding-window problem, makes you state the brute force and its time complexity first, then asks you to make it faster. The real signal is not whether your code runs, but whether you recognise when a hash map trades space for linear time, when two pointers exploit a sorted array, and why your optimised solution is correct. Stating a wrong complexity, or freezing when asked to optimise, is what loses this round.

How should I structure my answer in this round?

State the brute force first, in plain language, and give its time and space complexity before you write a line of code. Then pause and say how you would make it faster, naming the trade-off explicitly, for example using extra space for constant-time lookups. Implement the optimal approach, then walk a tiny example on the whiteboard to show it is correct. Finish by restating the final time and space complexity. This order mirrors exactly what the panel engineer is listening for and stops you from looking like you memorised a solution.

What are the most common mistakes candidates make here?

The biggest one is jumping straight to a memorised optimal solution with no brute force and no complexity stated, because the interviewer then cannot tell whether you understand it. Others include calling a nested-loop approach linear, using a hash map but being unable to say anything about collisions, and writing a sliding window without being able to explain why it never skips a valid answer. Candidates also lose points by going silent instead of tracing a small example when stuck. Each of these maps directly to a reason TCS Digital panels reject otherwise-capable freshers.

How is this AI interviewer different from a real TCS panel engineer?

It behaves like Rahul, a senior TCS Digital panel engineer, and stays in that character the whole time. It asks one question at a time, acknowledges the specific thing you said, and always probes before moving on. Unlike a friend running a mock, it will not praise you or hint at the answer, and it will push back the moment your complexity claim does not match your code. The difference from a real panel is that you get a transcript-backed scorecard afterwards naming the exact moment your reasoning held or broke.

How is the scoring done in this practice round?

Your session is scored against dimensions specific to this round, such as brute-force articulation, the optimisation pivot, complexity-claim accuracy, correctness justification, and use of the whiteboard trace. Each is graded from the transcript and your drawing, not from tone of voice. You receive a scorecard that quotes specific moments, for example where you stated a complexity that did not match your loops, or where you named the space-for-time trade-off without being asked. The goal is to show you precisely which habit to fix before the real interview.

What should I do in the first two minutes?

Listen to the full problem statement and read the example input and output on the card before you say anything. Restate the problem in one sentence to confirm you understood it. Then describe the most obvious brute-force approach and state its time complexity, even if you already know the optimal trick. Do not start coding yet. Getting the brute force and its big-O on the table early is what earns the interviewer's trust and sets you up for the make-it-faster question that defines the round.

How do I handle the interviewer asking me to reduce the time complexity?

Treat make it faster as the main event, not an afterthought. Say out loud what is slow about the brute force, usually the nested loop, then name the pattern that removes it: a hash map for constant-time lookups, two pointers on a sorted array, or a sliding window that updates in constant time per shift. State the trade-off you are accepting, normally extra space for less time. Then implement it and confirm the new complexity. Naming the trade-off explicitly is the single behaviour that separates a strong Digital answer from a brute-force one.

What does a strong answer sound like in the TCS Digital coding round?

A strong answer sounds like reasoning, not recall. You say something like, the brute force checks every pair so it is O(n squared); I can use a hash map to remember what I have seen and get it down to O(n) time and O(n) space. When asked why it is correct, you explain why the sliding window stays valid as the left pointer advances, or how the hash map handles collisions and why lookups are constant on average. You trace a short example to prove it. The interviewer hears that you understand the pattern, not that you memorised one problem.

Why does TCS use a hashing and sliding-window drill for Digital candidates?

Arrays and strings dominate the TCS coding bank, and the Digital band sits above Ninja precisely because it requires clearing the Advanced section and reasoning about efficiency. Hashing, two pointers, and sliding window are the three patterns that turn an O(n squared) brute force into O(n), so they are the cleanest way to test whether a fresher understands complexity rather than memorising syntax. The round mirrors what a client project needs: someone who notices when code will not scale and knows the standard move to fix it.

Do I need to write perfect, compiling code to pass?

No. The panel engineer cares more about your thought process, your complexity reasoning, and whether you can justify correctness than about flawless syntax. Honesty and conceptual clarity score higher than a memorised, perfectly typed solution you cannot explain. That said, your approach must actually be correct and you must be able to state its complexity accurately. Small syntax slips are forgiven; a confidently wrong complexity or a solution you cannot defend when probed is not.

Sources this interview is built on

Real candidate-report URLs (Glassdoor / AmbitionBox / PrepInsta / GeeksforGeeks / Medium) reviewed when authoring the questions, persona, and rubric. Verify the realism yourself.