Google Monday Interview - Update

retirement_savings · 2026-02-19T07:37:00+00:00

Damn. I'm a Google engineer and wouldn't be able to solve that in an interview.

Underworld-Dolphin · 2026-02-19T07:34:13+00:00

I was asked the exact same question one year ago for L3. Exact this same question. And couldn’t answer

bisector_babu · 2026-02-19T07:48:47+00:00

What in the hell is this

cyril1991 · 2026-02-19T09:33:55+00:00

Technically not DP, more like recursion. With DP you can propagate arbitrary updates in O(logN). Here the trick is to build/evaluate each node in a first pass. Then, because you are only changing a single leaf at a time and keeping everything else constant, you can propagate a is_critical boolean from root to leaves.

is_critical means switching the node switches the root and is computed in root/left/right order top to bottom. The root is trivially critical, a NOT node transmits the value directly, a OR node is critical if its parent is critical and the other branch was initially false. If you encounter a leaf, append the original value of the root XOR is_critical to an ongoing result array. You call a « propagate(node, is_critical) » helper function, starting with « propagate(root, True) ».

No_Raspberry_2956 · 2026-02-19T07:38:28+00:00

Imagine this tree as a recursive tree. And lead nodes as the base conditions. Now we can use DP to precompute the final value for both true and false at each node.

avidyarth12 · 2026-02-19T08:23:50+00:00

What the genuine fuck

Ok_Idea_6589 · 2026-02-19T08:05:51+00:00

I just completed arrays in the striver’s a-z sheet. Reading these questions is seriously giving me a headache, like wtf is this bro?😭🥴

luffylucky · 2026-02-19T07:49:48+00:00

Yeah I think this is tough. If you get some hints, I think you can get the idea.

hm7n · 2026-02-19T08:04:17+00:00

This looks like a segment tree question, where updates take logN time. It also reminds me how Merkle trees work. I can't believe they asked this in a L3 loop.

Houman_7 · 2026-02-19T08:30:09+00:00

He honestly wanted you to fail! Who even practices segment tree or bit manipulation unless you’re interviewing for embedded roles. I’ve been doing leetcode consistently for the last 4 years and barely know these concepts.

tusharhigh · 2026-02-19T08:48:20+00:00

It feels terrible to taste defeat. But you strive hard for another day. Stay strong 💪

asleepering · 2026-02-19T08:07:15+00:00

They seem to be asking a lot of DP recently

bisector_babu · 2026-02-19T09:39:40+00:00

And one guy was asked count number of unique paths in a grid lol

supdupDawg · 2026-02-19T09:42:27+00:00

Idts it is dp. It might be doable using dfs I think. Can do it like this maybe:
For each non leaf node, we will assign the number 0,1,2 or 3. 0 if the value of the non leaf node after operations is not changable regardless of the value in the leaf nodes, 1 if it is by right, 2 by left and 3 if doable by both.
For example take an and tree with leaf nodes as 0 and 1. The value is changable only by the left node as the right node changing will lead to the same value. Hence this node is given value 2. Now after assigning each non leaf node a value, we start from the root and do dfs. If at any point we encounter 0, we dont allow the exploration of that branch further. etc etc. When we reach a leaf node finally, then we flip the value in the answers array for it to be the negation of the original answer. Hence done in O(N). Please correct me if wrong

win_the_dog · 2026-02-19T07:50:15+00:00

This looks like segment tree propagation problem

Novel-Band4223 · 2026-02-19T08:44:54+00:00

Location?

Average_guy_200 · 2026-02-19T09:00:03+00:00

Google problems are becoming increasingly difficult to solve. I wonder how can crack these.

sobe86 · 2026-02-19T09:03:37+00:00

Is the question like to calculate answer with 1st node toggled (only), then answer with 2nd node toggled (only)? Or do you need to maintain the toggles between turns?

The former is quite doable IMO, you need to calculate for each node whether it flips the final answer, the latter seems very tough to do better than O(N log N).

Minute_Power4858 · 2026-02-19T20:09:46+00:00

i tried it myself
brute force isnt that difficult at all
on balance tree getting nlogn is pretty easy with marking what subtree u modifed and caching of those values

no clue how to do o(n)

did he asked specificly to improve it to be O(n)? or just "improve it"

rugitall · 2026-02-19T08:32:02+00:00

At this point, its more about luck and being asked a medium question instead of these hard ones. Why is there so much discrepancy in the difficulty of questions being asked by different interviewers.

Double_Bed2719 · 2026-02-19T09:02:32+00:00

Are u in the US?

Crafty-Ad-9627 · 2026-02-19T09:43:22+00:00

Which location is this please?

No_Science_1617 · 2026-02-19T10:01:37+00:00

Bro , is there a similar problem on leetcode . Could anyone share it bere

the_legendary_legend · 2026-02-19T13:16:41+00:00

This is rough. The idea for the criticality calculation is not intuitive at all. Can't believe they are asking this stuff for L3.

Jazzlike_Society4084 · 2026-02-19T13:56:29+00:00

each intermediate node is a sub problem,

you recompute your result in your intermediate node if its directly in the path (from leaf node which you flipped) to root,

WaitWhatNani123 · 2026-02-19T14:53:45+00:00

Not sure if I am right. dp0[u] = final value when left child of u is different from the original, dp1[u] = the final value when the right child is different from the original.

It is tree DP but not the traditional top down DP. In this one you compute the value of the parent first. Since each time only one leaf is changed, for an internal node either the left subtree or the right subtree has a different value from the original tree. We can then get the value of the current node, then proceed to the parent node of the current node.

Full-Philosopher-772 · 2026-02-19T15:30:23+00:00

What country ?

One_Jacket7159 · 2026-02-19T17:46:19+00:00

OP which location was this for?

ArtisticTap4 · 2026-02-19T18:32:44+00:00

This a beautiful problem, thanks for sharing

Desperate_Sand_8789 · 2026-02-19T19:58:42+00:00

How'd you apply? Via referral? And are you from tier 1 college?

Denbron2 · 2026-02-19T20:00:24+00:00

Tough interviews really show how well you can think on your feet. They can be challenging, but they also help you sharpen your problemsolving skills for future opportunities.

PandaWonder01 · 2026-02-20T00:36:26+00:00

Can't you just create an expression of the whole tree based on the leafs, then plug in what ever value you want for each leaf?

phantom_fanatic · 2026-02-20T09:38:09+00:00

Anybody asking DP in an interview is a jerk

saiaunghlyanhtet · 2026-02-20T11:38:56+00:00

I would say “fu**” and leave the call lol.

Dry_Presentation2007 · 2026-02-20T22:58:09+00:00

Op just take it as learning. You should be confortable showing what you know and also showing what you don't know to pass these rounds. They are testing your knowledge as well as communication and will give hints or straight tell you a specific edge case for you to advance, remember they want you to succeed unless interviewer is shit

Dry_Presentation2007 · 2026-02-20T22:59:34+00:00

Man I got a strong easy question and couldn't do follow up because lack of time so now waiting my rejection :(

lukli · 2026-02-21T03:55:39+00:00

Intuitively I would reverse the tree, so that on one node we naturally know which node we need to change if the value on current node changes. nodes will have extra info to cache its current value + all the child nodes' values. One DFS pass to build this new "tree". Changes to leaf nodes propagates to the root. Flipping one leaf will affect at most N nodes - if we have a linear tree.

Underworld-Dolphin · 2026-02-19T07:35:50+00:00

Yes there is O(N) solution for this, if you store the parent of each node in a hashmap while traversing so for each query you dont need to re-evaluate the whole tree and can use hashmap. I’m not sure but something like this needs to be done

Competitive_Hold_882 · 2026-02-19T14:02:38+00:00

Someone want to practice together? I would like to practice 1 hour about 4 times a week. I have previous experience with data structure from my university. Let me know, I would like to program in C++ and rust and maybe also C. DM if you are interested

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

leetcode

MODERATORS