Join devRant
Do all the things like
++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple API
Learn More
Search - "divide and conquer"
-
(Interview for sde-3 position)
(continuation of https://devrant.com/rants/2132431/... )
Interviewer - *opens laptop. Gives a question.* solve this.
Me - *a bit surprised that such questions were being asked on a sde-3 level*
this is the 4th or 5th question from geeksforgeeks, isn't it? I know the answer to this. Do u still want me to solve it?
Interviewer - *not believing me* Yes
Me - okay. Well this *writing down the original solution mentioned on the site* is the verbatim code mentioned on the website, with complexity O(n^2).
However I feel this is not the optimal solution. Let me write a better solution.
*I provide a better solution*
This has a complexity of O(n log n) . What do you think?
Interviewer - Nope. This could be a lot better.
Me - okay. Let me see. Did some minor changes, added some caching (obviously this will have no effect on the base algorithm) etc
How about now?
Interviewer - nope. Still not good.
Me - okay. Can you tell me how to improve it?
Interviewer - no we are not allowed to solve problems for you. It is not our interview, it is yours.
Me - that makes no sense. Interviews are a two way street. I'd very much like to know the optimal answer to this.
Interviewer - okay
*copies down the answer from geeksforgeeks*
This is good
Me - *at first I thought this was a prank or something. *
I just mentioned this answer here.
Then I spent the next 10 minutes providing a BETTER solution.
May I know how yours is better?
Interviewer - this solution has 2-3 loops. Yours has a function calling itself.
Me - that's called divide and conquer using recursion mf!
Anyways let's take an example and do a dry run.
Interviewer - okay
*we do dry run*
Interviewer - oh yes. Yours ran faster. But it will run fast only sometimes.
Me - yes. Each time the algorithm rolls a dice to decide if it should run fast or slow. You have one goddamn awesome weed dealer man.
I got to go. Thank you for meeting me.14 -
At an interview, the first round was an online coding round. Two questions, one easy one hard, 90 minutes, easy peasy.
I solved the hard one first.
A bit of good logic, followed MVC pattern, all done. Worked flawlessly.
Submitted code. Online compiler threw up an internal error citing java is an invalid command(jdk not found).
Called the invigilators. What I heard next, I couldn't believe this shit.
"We're not responsible for any errors you may be having. Figure it out yourself"
I was like WTF dude. This is not even a compilation or runtime error!
After a heated discussion, I made him look at the code.
Him - what is all this classes and all? Why haven't you written everything inside the main function?
Me - those are model classes. Those are different helper functions. That is a recursive function to avoid 5 for loops and use divide and conquer. Ever heard of OOP? what kind of person writes a 300 line program inside one function?
Him - no no we write it like that only. Correct this.
Me - I fit everything inside the main function. Still the same error, java not installed. Called the idiot to have a look at it.
Him - yeah your code is wrong.
Me - may I know what's wrong with it? Can you fix it please?
Him - no no we aren't allowed to see the code (he had already read it twice. It was compiling and running perfectly, locally) .
Yeah you solved only 1 problem, you were supposed to solve 2.
Me - yes because the rest of the time I had the pleasure of your company. (It isn't everyday that I see talking buffoons.)11 -
> Root struggles with her ticket
> Boss struggles too
> Also: random thoughts about this job
I've been sick lately, and it's the kind of sick where I'm exhausted all day, every day (infuriatingly, except at night). While tired, I can't think, so I can't really work, but I'm during my probationary period at work, so I've still been doing my best -- which, honestly, is pretty shit right now.
My current project involves legal agreements, and changing agent authorization methods (written, telephone recording, or letting the user click a link). Each of these, and depending on the type of transaction, requires a different legal agreement. And the logic and structure surrounding these is intricate and confusing to follow. I've been struggling through this and the project's ever-expanding scope for weeks, and specifically the agreements logic for the past few days. I've felt embarrassed and guilty for making so little progress, and that (and a bunch of other things) are making me depressed.
Today, I finally gave up and asked my boss for help. We had an hour and a half call where we worked through it together (at 6pm...). Despite having written quite a bit of the code and tests, he was often saying things like "How is this not working? This doesn't make any sense." So I don't feel quite so bad now.
I knew the code was complex and sprawling and unintuitive, but seeing one of its authors struggling too was really cathartic.
On an unrelated note, I asked the most senior dev (a Macintosh Lisa dev) why everything was using strings instead of symbols (in Rails) since symbols are much faster. That got him looking into the benchmarks, and he found that symbols are about twice as fast (for his minimal test, anyway), and he suggested we switch to those. His word is gold; mine is ignorable. kind of annoying. but anyway, he further went into optimizing the lookup of a giant array of strings, and discovered bsearch. (it's a divide-and-conquer lookup). and here I am wondering why they didn't implement it that way to begin with. 🙄
I don't think I'm learning much here, except how to work with a "mature" codebase. To take a page from @Rutee07, I think "mature" here means the same as in porn: not something you ever want ot see or think about.
I mean, I'm learning other things, too, like how to delegate methods from one model to another, but I have yet to see why you would want to. Every use of it I've explored thus far has just complicated things, like delegating methods on a child of a 1:n relation to the parent. Which child? How does that work? No bloody clue! but it does, somehow, after I copy/pasted a bunch of esoteric legacy bs and fussed with it enough.
I feel like once I get a good grasp of the various payment wrappers, verification/anti-fraud integration, and per-business fraud rules I'll have learned most of what they can offer. Specifically those because I had written a baby version of them at a previous job (Hell), and was trying to architect exactly what this company already has built.
I like a few things about this company. I like my boss. I like the remote work. I like the code reviews. I like the pay. I like the office and some socializing twice a year.
But I don't like the codebase. at all. and I don't have any friends here. My boss is friendly, but he's not a friend. I feel like my last boss (both bosses) were, or could have been if I was more social. But here? I feel alone. I'm assigned work, and my boss is friendly when talking about work, but that's all he's there for. Out of the two female devs I work with, one basically just ignores me, and the other only ever talks about work in ways I can barely understand, and she's a little pushy, and just... really irritating. The "senior" devs (in quotes because they're honestly not amazing) just don't have time, which i understand. but at the same time... i don't have *anyone* to talk to. It really sucks.
I'm not happy here.
I miss my last job.
But the reason I left that one is because this job allows me to move and work remotely. I got a counter-offer from them exactly matching my current job, sans the code reviews. but we haven't moved yet. and if I leave and go back there without having moved, it'll look like i just abandoned them. and that's the last thing I want them to think.
So, I'm stuck here for awhile.
not that it's a bad thing, but i'm feeling overwhelmed and stressed. and it's just not a good fit. but maybe I'll actually start learning things. and I suppose that's also why I took the job.
So, ever onward, I guess.
It would just be nice if I could take some of the happy along with me.7 -
Algorithms real life implementation
On the way to your college canteen? -> A* search
Waiting in line in the canteen? -> Queue
Notice that girl standing in front? -> Linear search
Searching for her dad in the phone book? -> Binary search
Stupid! Google it! -> Trie
Search for her on Facebook! -> Depth-first search
Found her! Friend request? Accepted! Send a Hi! -> Graph
Writing her a secret love letter? -> Caesar cipher
Uploading your first date pic on fb? -> Image compression algorithms
Looking through her Whatsapp messages? -> KMP algorithm
She found out and had your first fight? -> Start over with some gifts! Backtracking
Got her list of items to buy? -> Array
Too many items! Low on cash, maybe? -> Priority queue
Making her play treasure hunt for her gifts? -> Linked list
Wait! Go back! Is that a ring? -> Stack
Girl’s family not agreeing to your proposal? -> Divide and conquer
Got married? Congrats! Going for your honeymoon? -> Travelling salesman problem
Your mom packing luggage for you? -> 0/1 Knapsack problem
She packed your favorite pickles? -> Hash table
Driving to the airport? -> Breadth-first search1 -
Been looking into 2D maps for a game. I am learning how to use tools that do autotiling. I want to have generated worlds for terrain. It is interesting how the scope of what you are learning starts expanding rapidly and can overwhelm you. I started wanting to learn autotiling. This went from that to autogen, to modifying terrain, to how to store generated terrain, to how to store difference between autogen and player modified, to how to separate things into chunks, to how to store a whole world worth of data! Like dude, chill. Just learn how to use autotiling first. Then learn how autogen, then learn how to efficiently chunk things,. Also the 2d data won't be big so just store the data you genned so if modified. The worlds don't have to be ultra huge. Really stop freaking out what it could be and see what it is. JUST FUCKING ITERATE!
It is wild to watch yourself get featuritus without learning how to crawl fist. Just divide and conquer.29 -
Divide and conquer is a brilliant form of control. There are entities that benefit from making us fight each other, no matter the reason. From choosing a Linux distro to choosing a political party: everything goes.
If you hate JavaScript, hug your fellow JavaScript developer today. Tell them they're doing good.
Spread peace and unity. Let peace forever hold her way over the Earth.3 -
So today at work, a dev proposed some solution to a performance problem by using divide and conquer. But the way he said it was came across like "this is a brilliant, algorithmic solution, I bet you'd never think of this because no one else knows algos".
So then I just reply to him mentioning Big O and how it seems the performance is N^3, exponential. In which case the optimal size is like 1. But basically like starting an algo discussion to see if he can keep up... Or if he's just dropping some algo slang to look good.9 -
I was trying to make a circular buffer in C++. I was also trying to expose iterators for using the buffer with STL algorithms. I kept trying to think about how to add the functions needed to manipulate the existing internal iterators to not exceed the bounds of the buffer. Then I realized I was "too close" to the problem. There was no way I could properly control the internal iterators of the storage vector I was using. Not without giving too much power to the user of my library. So I abstracted the iterators up one level. Hid all the details of the internal iterator and made a new iterator.
The solution of abstracting the iterator was not the epiphany. The epiphany was if you are struggling with how to solve a particular problem. You keep running into problems with how to represent something, there is too much power available at a particular representation, or the object you are trying to make work just don't fit. This is when you should consider abstracting a level up. Take a higher look at the problem and simplify the interface.
Abstraction could be a number of things. Divide and conquer, hiding details, specializing an object, etc. Whatever tool is needed to make the problem more consumable to your brain. -
Competing on different subjects while in school have taught me how to work efficiently under pressure. My teachers have given me a systemmatic approach to problem solving, from divide and conquer (math), careful reading and analysis of the problem, as well as good documentation (physics).
And last, but not least, I learned to type fast, which is really helpful in speedy expression of thoughts. And for that, I gotta thank IRC. -
Dynamic Programming vs Divide-and-Conquer
👉🏻 https://trekhleb.dev/blog/2018/...
In this article, I’m trying to figure out the difference/similarities between dynamic programming and divide and conquer approaches based on two examples - binary search and minimum edit distance (Levenshtein distance).
The DP concept is still a subject to learn for me, but I hope the article will be helpful for those who are also in the process of learning. -
Programmers are freaks with three limbs and square heads. During your fiery conference speech, as the crowd laughs, one filth, who is your manager, tells another filth, who is someone else’s manager: “Look, this is my mule. Can code many hours. Don’t has to pay many moneys. My mule is more good than your mule. In Bangalore, they ask very many moneys for this mule.”
And you know damn well that when in Bangalore they ask less, you’re gone in a flick of a pen. Your company sent you to give this talk. Meetup? No, just a freak show for mules. Is it a dick measuring contest for investors? No, not at all. As you speak, this filth is fucking his secretary in Aruba while his wife is dying of cancer in Miami. And the supreme filth, the one that has no eyes and no mouth? It grins. Go mule, spaces versus tabs. Vim versus Emacs. Linux versus macOS. Divide and conquer.1 -
In reply to this:
https://devrant.com/rants/260590/...
As a senior dev for over 13 years, I will break you point by point in the most realistic way, so you don't get in troubles for following internet boring paternal advices.
1) False. Being go-ahead, pro active and prone to learn is a good thing in most places.
This doesn't mean being an entitled asshole, but standing for yourself (don't get put down and used to do shit for others, or it will become the routine) and show good learning and exploration skills will definitely put you under a good light.
2)False. 2 things to check:
a) if the guy over you is an entitled asshole who thinkg you're going to steal his job and will try to sabotage you or not answer acting annoyed, or if it's a cool guy.
Choose wisely your questions and put them all togheter. Don't be that guy that fires questions in crumbles, one every 2 minutes.
Put them togheter and try to work out the obvious and what can be done through google or chatgpt by yourself. Then collect the hard ones for the experienced guy and ask them all at once. He's been put over you to help you.
3) Idiotic. NO.
Working code = good code. It's always been like this.
If you follow this idiotic advice you will annoy everyone.
The thing about renaming variables and crap it's called a standard. Most company will have a document with one if there is a need to follow it.
What remains are common programming conventions that everyone mostly follows.
Else you'll end up getting crazy at all the rules and small conventions and will start to do messy hot spaghetti code filled with syntactic sugar that no one likes, included yourself.
4)LMAO.
This mostly never happens (seniors send to juniors) in real life.
But it happens on the other side (junior code gets reviewed).
He must either be a crap programmer or stopped learning years ago(?)
5) This is absolutely true.
Programming is not a forgiving job if you're not honest.
Covering up mess in programming is mostly impossible, expecially when git and all that stuff with your name on it came out.
Be honest, admit your faults, ask if not sure.
Code is code, if it's wrong it won't work magically and sooner or later it will fire back.
6)Somewhat true, but it all depends on the deadline you're given and the complexity of the logic to be implemented.
If very complex you have to divide an conquer (usually)
7)LMAO, this one might be true for multi billionaire companies with thousand of employees.
Normal companies rarely do that because it's a waste of time. They pass knowledge by word or with concise documentation that later gets explained by seniors or TL's to the devs.
Try following this and as a junior:
1) you will have written shit docs and wasted time
2) you will come up to the devs at the deadline with half of the code done and them saying wtf who told you to do that
8) See? What an oxymoron ahahah
Look at point 3 of this guy than re-read this.
This alone should prove you that I'm right for everything else.
9) Half true.
Watch your ass. You need to understand what you're going to put yourself into.
If it's some unknown deep sea shit, with no documentations whatsoever you will end up with a sore ass and pulling your hair finding crumbles of code that make that unknown thing work.
Believe me and not him.
I have been there. To say one, I've been doing some high level project for using powerful RFID reading antennas for doing large warehouse inventory with high speed (instead of counting manually or scanning pieces, the put rfid tags inside the boxes and pass a scanner between shelves, reading all the inventory).
I had to deal with all the RFID protocol, the math behind radio waves (yes, knowing it will let you configure them more efficently and avoid conflicts), know a whole new SDK from them I've never used again (useless knowledge = time wasted and no resume worthy material for your next job) and so on.
It was a grueling, hair pulling, horrible experience that brought me nothing in return execpt the skill of accepting and embracing the pain of such experiences.
And I can go on with other stories. Horror Stories.
If it's something that is doable but it's complex, hard or just interesting, go for it. Expecially if the tech involved is something marketable.
10) Yes, and you can't stop learning, expecially now that AI will start to cover more and more of our work.4 -
When I'm really really stuck, I generally stress out that I should be able to figure it out so I walk outside, sit down, listen to relaxing music and imagine I'm on some isolated mountain somewhere away from all the problems of deadlines and managers and algorithms...then i just write down what i need to do and what i have done already and have a little brainstorm session with myself over possible causes/solutions from sensible to crazy, just anything possible... generally I always come to 2 methods - divide and conquer and document and destroy (the latter being used in cases such as having to fix something in an undocumented 10,000s lines long sproc that someone who left the company wrote)
-
So, some data need to be prepared during the summer and the diverse departments' elected data processors got shared in a Google spreadsheet they will need to fill with some basic data IT needs. Simple, straightforward data entry, with nothing private nor confidential. Just another divide-and-conquer-style large amount of data to enter & organise, that's all.
Today, I received a new comment notification as the owner of the spreadsheet. You can imagine my surprise when I saw that, for some f*cked up reasons, one of the guys just wrote the super-admin username & pw for one of the main data systems we use in a freaking comment in the spreadsheet... WTF...
Oh, and also, juuust in case, he also wrote the pin code that is normally required to pass through the device-check when you log-in as a super-admin from an unknown device and/or location.
Fortunately I could catch it on time, but this just ruined half of my day.
I am supposedly on freaking annual leave. Ha Ha. Ha. -
I really want to divide this frontend into two parts, one that faces the users and other for administrators so I can release changes on both without works on one part blocking the other, but, I have many question, like, how do I manage authentication in two different React projects from one login page?
Maybe there are more problems than benefits, what do you think?3