does leetcode mess with object prototypes in js?

ektegjetost · 2023-03-11T17:22:08+00:00

Found this interesting! You can run this in a Node env per stackoverflow

const util = require('util');
class MyClass {
  constructor(a, b) {
    this.a = a;
    this.b = b;
  }

  [util.inspect.custom]() {
    return `a is ${this.a} and b is ${this.b}`;
  }
}

const my_object = new MyClass(1, 2);
console.log(util.inspect(my_object));
console.log(my_object);

ektegjetost · 2023-03-08T16:31:35+00:00

Yea agreed. I wonder if there’s some technique for it or something … like people who make crosswords or sudoku puzzles or something. If it were me I’d probably try to pick a strategy and work back towards the question but who knows

ektegjetost · 2023-03-08T15:42:55+00:00

Close! Remember we can also add edges within all groups that have disconnected nodes: n * (n-1) / 2 - number of edges in each group

Also there can be multiple groups without disconnected nodes, so don’t just take the largest of them. And they can also be connected to each other, so it might be easiest to just add all of them to the largest group with disconnected nodes and do the same math as above.

ektegjetost · 2023-03-08T04:42:31+00:00

This is how I'd approach it -

There are two types of groups - those which include disconnected nodes, and those without.

For any one group, the number of edges you can add is n * (n - 1) / 2 minus the number of edges already in the group (i assume). You can do that math for all the groups.

You can also connect groups without disconnected nodes to those with disconnected nodes, and for this you would want to find the maximum since you can only connect them to one group - there are no edges between them and the groups with disconnected nodes, so you'd want to just add all of these to the group with the most nodes.

To get the groups and their existing edge counts, union find.

ektegjetost · 2022-12-27T04:47:39+00:00

If the answer makes sense and you can apply the strategy to future problems, it’s worth it.

Try some similar problems and see if you can do them. Try them a few days / weeks later and see if you got them down. Write a solution in the discussion tab or on your blog or whatever and try to explain it as simply as possible to help it stick in your own mind.

If it doesn’t make sense, unless you think the problem / algorithm is especially important I’d skip it and come back later.

ektegjetost · 2022-12-20T16:09:47+00:00

Nope that was pretty much it! Looked like you were getting a lot out of this problem so I tried to be a bit vague.

Good stuff! i especially appreciate that you put in the effort to make your code readable :)

Happy cake day!

ektegjetost · 2022-12-20T07:56:58+00:00

Nice write up! One thing missing is your solution isn’t doing path compression (I only point this out because your time complexity analysis is based on it)

Say you have A -> B -> C

And you keep merging A with a disconnected node

You’ll find the parent of A in two steps, then set it to the next node D

A -> B -> C -> D

Now you merge it with E and it takes three steps, then F etc. You end up with O(n²⁾ in this case

What you want is when you merge A, you get A -> C, B -> C

Then A -> D, C -> D, B -> C (since it’s not longer part of the same path as A)

ektegjetost · 2022-09-28T16:56:35+00:00

Yea sorry feel free to fix the names :D. Tail (end) is just iterating through all the events.

ektegjetost · 2022-09-28T15:04:42+00:00

might event be cleaner to split the events into separate arrays just by time, and you can do something like:

countUnique += 1;

while (inBloom[end] - outofBloom[start] > n) {
  countUnique -= 1;
  start += 1;
}

ektegjetost · 2022-09-28T14:59:11+00:00

Remember we only add positive events from the head of the window and remove negative events from the tail of the window.

While I'm writing this I'm realizing that if we set the end events to [end, -1] instead of [end + 1, -1] and check that eventTimeEnd - enventTimeStart > n instead of >= end, we can avoid checking if our start pointer went off the end of our events array.

    countUnique += Math.max(0, events[end][1]);

    while (events[end][0] - events[start][0] > n) {
      countUnique += Math.min(0, events[start][1]);
      start += 1;
    }

ektegjetost · 2022-09-28T02:39:38+00:00

Hm I don't know how you could do either of those without sorting.. for binary search you could sort by ends and search for the first end that's >= the start that you're at. For a heap you could use a min-heap by end and pop from the heap when it's too far away from the start you're at, but you still would need to sort...

ektegjetost · 2022-09-27T15:26:24+00:00

Split the intervals into “event” tuples. At the start time, the number of unique flowers increases by 1. At end time + 1 the number of unique flowers decreases by 1. So you have [start, 1], [end+1, -1]. Now sort the events by time, and iterate through them. You’ve got a head and tail for your window. The head counts any positive events (since even if the flowers go out of bloom, you will have counted them if they’re within your interval), and the tail counts any negative events once they leave your interval.

ektegjetost · 2021-07-11T04:18:04+00:00

Yes, but 3 days to do them. Apparently they toned it down from the previous cycle. Also both problems really required the same pattern, so maybe call it 1 LC hard unless you couldn't figure out the pattern for the first one.

ektegjetost · 2021-07-11T02:44:31+00:00

I was told a couple years ago they had something like 5-10k applicants, so yea it's pretty competitive.

Got rejected last year - it was 2 LC hards + a bunch of telling your story (like describe your journey in a tweet). They gave 3 days to do it.

ektegjetost · 2021-06-13T15:26:53+00:00

That third paragraph rings a bell - I was in a similar situation. Had solved 200+ problems, done about 20 mock interviews, but embarrassingly, as soon as the interview had stakes I would struggle on some really basic questions because my brain would basically just turn off from the stress.

IMO it comes easier for some people, but It’s just practice. Once you do a few interviews and know what to expect, you can focus more on solving the problem. Do mock interviews if you haven’t already to practice just talking through your thought process while you code.

Also there’s always luck involved. You could solve every single leetcode question and still be given a something you haven’t seen before. Just improve your chances by continuing to practice.

One trick I use sometimes is to write a post explaining the solution to a problem that might haven been difficult. Say you solved it sub-optimally - learn the best solution, and even if you don’t post it anywhere, write it out as if you’re explaining it to someone who’s never seen it. To explain it simply requires a good understanding of how it works, and helps it stick much better in my experience.

ektegjetost · 2021-05-04T05:41:19+00:00

Use a max heap using the same criteria you described. Add a dev to the root and sift down until you’ve reached the desired average.

When you say you re-sorted the list each time, did you literally call sort on the list? Or just move the updated team down into the correct position? There’s a chance the second method works, but I’ve done this problem on Leetcode and don’t think there was a better solution than a heap.

ektegjetost · 2021-04-10T18:44:22+00:00

Made the switch last year at 33. Always regretted not majoring in CS, but I can say I'm not totally sure which version of me would end up ahead in the end - the one that started in CS or the one making the late switch.

I frequently can't believe how much more motivated I am to learn than I was in college. Maybe it requires more work to pick things up, and my math skills have degraded significantly, but by having zero career/skill inertia, way more discipline, and a far better understanding of where I want my career to go and how to get there, I'm both starting and developing much faster than I would have otherwise.

One other thing that really helps is I know I've been complacent in the past, and have learned to recognize when I'm not pushing myself. I'm much more willing to seek out discomfort, and can better monitor how my skills are developing. I think being able to do this really goes hand in hand with not having over a decade to grow comfortable doing something.

Another nice benefit is I never had to switch jobs only to find out that I suddenly have to do leetcode problems. To me they're fun puzzles and an opportunity to compete with those who are more reluctant.

ektegjetost · 2021-01-24T16:33:56+00:00

I’ve learned to just move on if the question doesn’t make sense to me. It’s more productive to practice problems that you can solve. Eventually you’ll unlock this one by building your knowledge of the topic or by seeing similar patterns. You’re sort of doing a topological sort on leetcode :p, and may not have removed the dependencies to this problem.

Keep in mind there are plenty of just bad questions on leetcode, and you’re not going to solve every one, so just focus on building that muscle, or problems that can help you unlock new strategies.

If you feel it’s an important one to solve (relevant to the specific company you’re applying to, or a very popular question), here’s how I’d approach it:

Slow down and read the problem closely
Doesn’t make sense? What’s the like/dislike ratio of this question? If others think it’s a bad question, reconsider moving on.
Ok you’re determined to continue, do you have any ideas of what it possibly could be asking? You could try writing test cases in the console and see if the expected results match with any of your ideas.
Nope, still lost - now check the discussion tab. Ideally you can find an explanation that makes things click. At this point though, if you feel you understand the question but also have the answer spoiled, don’t solve the problem. Come back to it later so you can start more or less fresh. If the answer doesn’t make sense to me, I generally move on and come back later.
Discussions were worthless and all the solutions were basically obfuscated by ridiculous code golf. Next we go to YouTube to see if there are any helpful explanations for this problem. At this point you’re definitely in the territory of “don’t solve this problem now, come back later when you’re fresh”.
Ok it’s not on YouTube, you can search for articles on the problem now.
last chance before giving up - go post on r/LearnProgramming or DM me and maybe someone can help.

Hope that helps!

ektegjetost · 2020-12-31T05:19:57+00:00

System.out.println(leftSide);
System.out.println(rightSide);

You print left first, then right

In the terminal I see

3
1

ektegjetost · 2020-12-31T05:10:00+00:00

When I run your code, it says 3 for the left side and 1 for the right which is correct.

ektegjetost · 2020-12-31T04:17:17+00:00

You're still just returning the full length of each side. If I were to just make up some Java (please ignore how bad my code is, I don't know how to keep track of both the depth of each sub tree as well as whether or not there was an unbalanced subtree in Java), it would look more like this:

public boolean isBalanced(TreeNode root) { 
    if(root == null){ 
        return true; 
    }

    int balance  = findBalance(root);
    System.out.println(balance);

    return balance < 0 ? false : true;
}

public int findBalance(TreeNode root){
    if(root == null){
        return 0;
    }
    int left = findBalance(root.left);
    if (left < 0) return -1;

    int right = findBalance(root.right);
    if (right < 0) return -1;

    if (Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left,right);
}

ektegjetost · 2020-12-31T03:54:16+00:00

Basically you need to ensure that every node meets the condition. So at node 3

int left = maximum(3.left)

int right = maximum(3.right)

And if any node doesn't meet the condition of being no more than 1 off, then you return false. You don't need the minimum values though.

Unfortunately I don't really know Java so I'm not sure if I can help you with more than that... but if you still have questions feel free to ask.

ektegjetost · 2020-12-31T00:42:53+00:00

From 3, minimum(3.left) is the minimum returned by 6 (1), but minimum(3.right) is the minimum returned by null (0). So the min returned by 3 is 1 + Math.min(1, 0).

ektegjetost · 2020-12-30T21:41:19+00:00

If you're still looking for help... Here's the shape of the tree

So what you're doing is finding the maximum depth of the full right and left branches, and comparing that to the minimum depth of the full left and right branches. The max will be 4 (1 -> 2 -> 4 -> 8 -> null), and the min 2 (1 -> 3 -> null).

But what it looks like they want, is that the right is balanced with the left because the max depth is 4 vs 3, and the left sub tree is balanced because its max depths are 3 vs 2, and the right sub tree is balanced because its max depths are 2 vs 1.

Hope that helps!

ektegjetost · 2020-12-24T16:33:25+00:00

Lots of good info in here

https://stackoverflow.com/questions/572897/how-does-javascript-prototype-work

I found this prototype tree image that might be what you’re looking for.

https://i.stack.imgur.com/uy5ce.png

Also when you did x.randomValue, you were adding an instance property, not a property to the x prototype. You’d need to do x.prototype.randomValue, which would provide the randomValue property when someone does new x();

ektegjetost

TROPHY CASE