You could just go on merging sets with each other.
For i from 0 to n-1 , find all sets from i+1 to n-1 which have a non empty intersection with set i. Union set i with all those sets and replace i with the union set.
If you use a disjoint set data structure this will be quadratic or O(n^2)
EDIT:
On further thought you need to merge from the end and backwards.
I'm currently prepping for an interview at one of the Big 4. I can tell you that this site is quite useful.
They have tons of problems to help you with the recognition part as well. You don't have to be a genius to be able to do these problems. It just comes down to pattern matching.
That said I don't think this is the ideal way to interview people. However no one has as yet proposed a better alternative. I turned down an interview assignment recently because they wanted me to implement an app with :
- Syncing to a database
- UI Tests (with a mock API)
- Unit tests
- Functional reactive programming
- A really complex architectural design pattern
All this just to get a shot at the interview. I was too tired to do it at the time so I turned it down. So I would criticise programming interviews but I don't have a better alternative. Sane assignments are a reasonable middle ground (Perhaps they could have knocked off a few from the above list).
So if you want to work at a top employer and not be forever stuck doing CRUD then your only option is to learn algorithms and practice interviewing. I know it sucks but that is how the game is played.
The reason some people can do them is not because they're geniuses but they come from employers,schools where there is a culture of doing interview problems. They've been doing this for atleast a year if not more. So try doing them for a year and then tell me whether you still find them impossible.
I realised this when I took the help of a champion competitive coder for preparation. It was hard to find a question typically asked in these interviews which he hadn't heard of in some shape or form.
I have some tips I'm compiling which I might turn into a blogpost or book.
For recognition you need to practice abstract thinking . Thinking of something in terms of code should be completely avoided. Suppose I ask you to find the common ancestor of two divs.
In this case the DOM is a tree whose nodes have parent pointers.
Turn every question into a mathematical abstract form. Find a k such that , Find two numbers x & y such that and so on.
The next step is massive repetition. It feels like you're grinding with no understanding , but something happens when you repeat something 20+ times. Depending on how smart you are it happens sooner. Eventually it will become intuitive.
Always learn multiple solutions. Never settle for just one answer. Learn all possible answers and how it might be possible to go from a brute force to the optimal one.
Use Geeks4Geeks and Elements of Programming Interviews to build your pattern recognition.
Next read books and PDFs by Udi Manber on algorithm design.
This is a lot of effort. But that's just how it is. You don't HAVE to work at Google. You can work at other places and do quite well too. But if you want the top jobs then this the road you must take.
But my personal view is that we should support a syntax that is a subset or derivative of HTML while being performant so that any existing web framework can generate smooth native apps (while also side stepping Apples rules against implementing a browser engine :P).
It sounds stupid but I work in E-commerce and have wished for this many times.
Don't listen to the haters. This is extremely valuable. Especially in E-commerce.
Like when you have an ever expanding product line and new categories are being added all the time. Ever wondered why Amazon uses web views all over ?
Many E-commerce companies would love to be able to do extensive A/B testing or add analytics on the fly but are crippled by the App store and the limitations of native apps. Some have even built versions of this themselves.
What we need is an Android port of this and then this will be some hot shit. I am willing to help on the iOS side in any way I can.
I've thought of making a Native renderer for some subset of HTML like Google AMP that would work on both Android and iOS. That way all existing web frameworks could generate native apps.
But you'd have to do something like this to ensure that you're not breaking Apples rule of not making your own browser engine.
You need to connect it to the perceptions of growing inequality.
As long as your life is visibly improving , you don't mind that some people are doing insanely well. But it's much harder to stomach when you're struggling to get by.
As someone who has worked there I'd like to set the record straight.
What's wrong with copying someone else's features ?
AFAIK Camera Plus was released BEFORE Camera+. But it was easily beaten by the other and it became so popular that now it seems like it was the other way around.
But yeah Boom is a bit over hyped. It doesn't increase your speaker output beyond the permitted maximum and so it can't really do any damage. Its just applying a limiter / compressor to your audio output. The thing is that noone has bothered to make something cheaper or free.
Robosoft was working on Apple Tech way before it was cool (from 1995..). A lot of the experienced Apple developers in India may have had their origins at Robosoft.
One minor but important aspect missing in the PR of the essay is about how they treat their employees. Anyone joining them fresh out of college has to deposit an amount equivalent to half their starting salary in a bank account for which you surrender the papers to the company.
If you leave within 3 years , the amount is forfeited. Now this is an incredibly shabby way to treat your developers. They claim it's to recover training expenses , but yeah 3 years !? Gimme a break.
Not exactly the "global" startup they claim to be. If you think I'm lying just go go to glass door and read their reviews. Remember to sort by date.
I didn't write this to crib on my employer but to add some perspective. Sometimes devs on places like HN forget how lucky and privileged they are to be treated so well. This is how Indian developers are treated even at some companies doing good work that is globally competitive.
But all in all it's still a pretty impressive achievement. I admire what they have done. However the building mentioned in the article is only half full even after the company has been in operation for 15 years.
I'd like to think that one of the reasons they've never reached their true potential because of the high attrition resulting from how they treat their developers.
But then that's how Indian IT consulting works. Keep a small skeleton crew of experienced "managers" or "lead developers",while most of the actual work is done by fresh grads , who are then billed to the client as "experienced senior developers". By the time they get actually experienced and start demanding more , replace them with another set of grads , chain them to the company , rinse and repeat.
Don't hate the player , hate the game and all that.
Yes , it's the bean counting IT firms that have to share a large portion of the blame.
Anyone who is good and asks for a higher salary is quietly moved out.
In an IT services company it's all about the billing rate. A manager can always be billed at a higher rate than a lowly developer. So say you've been a developer for five years. Now the company can no longer "afford" to bill you as a developer.
So they'll force you into management so that they can bill you as a manager. I've seen brilliant developers , who're still interested in writing code , but now all they do is fill excel sheets and status reports. And you'll be forced to manage multiple projects so that they can make even more money off of you.
Otherwise you'll forever be stuck at a lower pay grade as a "mere" developer.
IT services companies have a super low cost business model and they aren't interested in moving to the premium end of the market.
The attrition in this sector is enormous. Just look into the figures for Infosys , TCS etc. It's reached upto 30% ! If 30 % leave in a year , it doesn't take long for all your experienced people to move out.
But they've perfected this continuous conveyor of clueless graduates being cycled into the software meat grinder. They don't even hire CS grads. They'll hire almost anyone put them through their cookie cutter "training" and now you're ready to work on projects for the Fortune 500.
Then there is the pervasive cheating and deception. Resumes are faked , they hire clueless developers straight out of college and make them work night and day to deliver their first project all the while assuring the client that they've put their best devs , with 3+ years of experience on the project.
You're endlessly in maintenance projects which means you don't have much of a chance to learn and grow.
So a lot of the "bad Indian coder" meme is due to the way that low cost IT services firms are structured and the people they hire.
So very few people who take pride in coding can survive for very long in such an environment. If they're really good , they've already jumped ship to some top 10 product firm or startup.
So you're very unlikely to find any good coders there , and the ones left will be doing management.
I am an Indian developer and I feel that you're onto something there. This needs more discussion.
For eg: An executive an HCL , a leading Indian outsourcing firm called American developers "unemployable" :
>> He says students from countries like India, China, and Brazil are more willing to put the effort into "boring" details of tech process and methodology, such as ITIL, Six Sigma, etc.
Yeah. These folks questioning our ability are in for a rude shock in a few years . There's a whole eco system of mid tier firms + startups which are shaping up really well .:D
Indian developers are not over-rated. Infact noone outsources India because they think they think that Indian coders are geniuses.
They know that Indian developers are mediocre but management believes that mediocre is "good enough" at half the price , and guess what , it might hurt your ego , but in many cases mediocre developers + long working hours can solve most problems that typical devs encounter. You just need a good dev overseeing the efforts if the project is complex.
Just add everything one by one to a Disjoint set union.
My bad.