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.
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.
When I read the Readme, I was thinking this could get a lot of limitations of store app updates. (As long as this thing can use a cached version of your json if it can't connect to the Interwebs).
I hate the walled gardens of the iOS/Android world and the fact that multi platform frameworks are so difficult. Seeing things like this are encouraging.
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.
It's an XML/HTML-like syntax for building native Apple TV apps using native components, but loaded over HTTP and without having to write Objc/Swift code. It's very much like this (or React Native), but in XML.
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.
I mostly agree, but I'd argue that epicycles actually made useful and testable predictions, although we found a simpler description later on. The article underlines a lack of refutable theories. Thus, I think [1] is a better analogy.
The characteristic of metaphorical epicycles is that the make simple, testable predictions that are then wrong, which are fixed with another epicycle.
Another more subtle aspect of epicycles, real ones this time, is that they are too powerful and can be used to prove anything. You can predict the motion of the planets with epicycles, it's just that the required series is very long or infinite. And with very long series of cycles, you can "predict" anything: https://youtu.be/QVuU2YCwHjw?t=25s Thus, one of the problems with epicycles both real and metaphorical is that they are indeed not refutable. Because epicycles can predict anything, they aren't that useful; they exclude far less than meets the eye at first.
It isn't hard to see that characterist showing up in string theory. The theory has for a very long time had problems with excluding possibilities, and each new metaphorical "epicycle" seems to come with more parameters than the last, rather than fewer. Now, this isn't unique to string theory since all the current theories seem to have that problem, but then, the point is, why does this problematic theory have so much more support and money than the other problematic theories?
>Another more subtle aspect of epicycles, real ones this time, is that they are too powerful and can be used to prove anything.
String theorists talk about how rich and complex the mathematics is, but maybe that just means it has so many possibilities you can always come up with an explanation to overcome newly-discovered difficulties.
Well that's really all that is wrong with it: you are adding epicycles instead of working on a better theory. In analogy: once a language is turing complete you can do anything in it, so you can keep using brainfuck to make a gui, but probably it would be easier in java...
Read up on MITMproxy. It works best on Mac. For Windows I recommend Kali-Linux virtually so you don't have to build for Ubuntu. If you have problems just email me: morten(at)punnerud.net
They only force HTTPS, not their own sertificate as in Facebook and Snapchat.
Visit mitm.it on your phone (after you have set up a proxy through your pc running MITMproxy) to automatically ad a sertifificate to get it working, or generate your own if you don't trust the service.
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.
> What's wrong with copying someone else's features ?
Nothing wrong at all in getting inspiration, but the copy was a bit too much like an exact replica. The threads I linked to have more details. Global Delight also posted a short rebuttal after that.
I'm not saying that creating a copy is very simple and does not take effort, but it results in being seen as "unimaginative" or as a "copy cat". Those are not terms that someone would usually want attached to their reputation.
Guess there's always some criticism to be made about apps, but the bit about depositing half your salary is horrible. Some aggressive retention tactics.
I enjoy playing summoners war, but recognize it as basically a slot machine. There are people on there who clearly have spent a LOT of money. I've chatted with a few of them (the largest that someone admitted to was $5,000), and most of them claimed to be well-off enough that it wasn't an issue. One claimed to be the son of a successful investment banker. One was from China and said he doesn't even know how much money they have, but they always have plenty. Nobody I talked with has been all like, "yeah, i am hurting myself and racking up debt, but I just can't stop"
Of course, if you assume even half of those people are lying, that's where the addiction is. You'll tell yourself stories and tell others stories, so they don't see you as a weak person.
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.
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.