I've done interviews with Facebook.
I just have a quick tip to add to naumazeredo's great answer,

Be careful with details (such as ambiguity, corner cases, coding style... etc.).
naumazeredo is right about the difficulty of these questions.
However, interview questions are often asked with hidden ambiguities. This might include the size of input, range of numbers, permissible conditions (eg. can a number be used twice?) ...etc..
It's also very likely that these questions will include sneaky corner cases you need to think of before coding. You don't want to write an ugly fix for just one type of corner case.
As for coding style, the interviewers at these big-4 companies will seriously look for signals that indicate whether you're a good developer. So if you're one of those people who use a, b, c as variable names for example, quit doing so during interviews.

Yeah LeetCode should probably be in there :)

If we include data science competitions, I think there will be a lot to be added.

I think it would be better to leave those for ML resource collections.

That's interesting, because I was able to download those documents last year.

It was actually one of the more accessible download locations I could manage to find.

I'll probably end up removing it, because it is a little controversial.

Yes! :)

Your blog looks amazing.

I apologize for being not as responsive lately.

I'll get back to you when I have time, and ping me if I don't.
Also, I'm so sorry that I cannot provide individual assistance.
I've been quite busy and I don't think I'm the right person to ask for help (I'm blue you see).

You're very, very welcome! Glad it's helpful for you :)

Well, I would love to, but I need an authoritative review of those books because I have not read these books entirely.

Would you be kind enough to share your thoughts?

Wow! Their notebook looks awesome!

I'll add that to the list when I get off work today.

I admit that it's a little overwhelming :P

That said, there are also overwhelmingly many ways you can start!

if you don't have a clue, I would suggest that you start with an open course :)

This does look like a good book.
Can you give us an introduction for the book?

I'm sorry that I do not understand Spanish, nor am I familiar with the Spanish-speaking competitive programming community.

I would love to, but I have rather limited knowledge when it comes to Computational Geometry.

You should be able to find some relevant resources on the listed websites, but other than that, I'm afraid that I am a bit on the ignorant side when it comes to CG :/

Yes it does depend on the interviewer, but the questions typically won't be very difficult for interns.

For me, it was a little bit of everything.
Algorithms and data structures, architectures, easy maths and some past experiences.

1) I'm guessing this is because Google also takes Winter interns and they're always hiring for full-time positions.

2) I'm having difficulties understanding the sentence. You can apply for intern during the application periods as long as you're currently enrolled as a student in an academic institution.

Hmm it doesn't seem to just depend on the ranks.
Up to which rank in Google APAC tests are students called for interviews? — Quora

Competitive programming experiences actually do make interviews a bit easier but a good understanding of other CS subjects is also required :)

Thanks for the kind words :)

It's been a year since I launched this project.
Time flies!

Hello,
Thank you. I appreciate the effort.

However, I don't think any of these are qualified for the list.
They are all well-organized, but too simple (only cover basic stuff).

Thank you!
I'll replace the link to the website with this one :)

The items are significantly harder too o.o

geeksforgeeks is up there, 3rd item in the first section.

Thanks, added.

Sorry, it's been busy for me recently.

I actually stumbled upon his profile a while ago,
and he didn't have many answers back then :P

Thanks,
I'll place him on the list.

Hello. Thanks for the suggestion.

Can you tell me a bit more about him?

Maybe not in the sites to practice,
because I think interview questions are quite different.
(This list is for competitive programming for the most part)

I'm sorry. I do intend on including it.
I just haven't gotten around to explore this site.

Sorry for the late reply.
I've been pretty busy recently (doing 2 jobs atm).

It looked great I think.
I checked out a few of the problems.

I have a question: Is it being actively maintained? (eg. new problems every now and then?)

Hello, Thanks first of all.

Can you tell me how you would recommend it?
(Sorry, I don't know these sites well enough)

Thank you!
Added :)

I'm still relatively unfamiliar with interview questions.
Did 2 Facebook interviews last year, but I didn't do very well :(

CHelper supports multiple platforms. TopCoder is supported I believe.

I think that would be CHelper.
Check the Tools section.

I haven't tried it myself though.
In case you have any issues, ask Egor, the author of CHelper.

At least my take on it :P
(It started off as a simple compilation of my browser bookmarks :P )
I still have many ideas to improve on the current list!

Good luck to you as well :)

Hello there :)

Since you mentioned MS-Word, I would suggest you to try an online syntax highlighter. This is my solution for making slides with code snippets.

• Markup.su
• Tohtml.com

Paste your source code on the website,
and copy-and-paste the converted, formatted source code back to MS-Word.
Since MS-Word retains formatting, the outcome would look pretty nice :)

I'm not aware of a better solution. Would highly appreciate if there's any :)

PS. If this is for your team notebook, you may also use latex — a clever solution refined by my ex-teammate pwliao. Link to our notebook repo

Glad to hear that. Comments like yours made my efforts worthwhile.

Best wishes to your competitive programming journey :D

First and foremost, Thank you!
This is exactly the kind of feedback I'm hoping for :)

Well, I'm not exactly sure. I actually gave it 2 stars initially precisely for the reason you stated in your comment. But then I decided to give it a 3-star rating because of the large amount of classic problems on there. IIRC, Johnny Ho (IOI 2012 Perfect Scorer) said that he practiced primarily on POJ. This also contributed to decision.

In the Taiwanese community these days, from what I've heard, people practice on local online judges (such as HSNU OJ, sprout, TIOJ ... etc.) in addition to CF and topcoder. I think our current situation is kind of similar to yours (Japanese community) by your description :)

Thanks for the recommendation!

I'll take a look. Here is a collection of good C/C++ books by StackOverflow members.
I think I'll add both of them to the list.

Yes, you are absolutely right. Sometimes finding good resources in text is already hard enough, but these open courses help more or less.

I'd say this is partly due to the competitive nature of the scene. Plus practice and schoolwork take up a significant amount of time.

I highly support Alex7 's initiative. The scene is really getting better and better with all of you nice people :)

Well, there are plenty of video lectures (from open courses) for algorithms and data structures.

prakhar1989/awesome-courses#algorithms

kllp had a blog post about it.

There are also some discussions below.

The approach was also mentioned in this blog post by PrinceOfPersia. Perhaps it might help :)

(PS. I don't how to do it yet. I was also having issues understanding these tutorials.)

I have some of Prof. Wu's books.
I've even taken a summer training course from him back in 2014.

Frankly speaking, they are not good. It doesn't seem like the professor truly understands the materials. Almost everything (definitions, tutorials, problem editorials) was poorly written. The books cover absolute nothing about the ideas/thought processes. Everything was like "Declare an array/ds with key = X, value = Y. Then you do this ... and you do that. Finally this is the answer."

I personally would disagree that it gives better readability.
Also, C macros were not designed for such purposes.

The reason is simply writability (fewer keystrokes).

At least use commas...

You will need to check for negative cycles, rather than edges with negative weights.
To do that, iterate through the E edges again (After Bellman-Ford) and see if any vertex is still "relaxable". If so, there exists at least 1 negative cycle on the graph which means there are no shortest paths for certain vertices.

I suggest you to read all the fantastic answers over here.
How do I start competitive programming? — Quora

I have also been maintaining this list of resources which I think should be helpful to you.
Awesome Competitive Programming
If you're unsure about what to learn, start by reading through the lecture materials from the Stanford's course.

Yes, but slightly different.
The original paper from 1972 covered it all.

Sorry, misunderstood the problem statement.

if(b[i] && b[j] && i + j < 5200){
    br += dp[i + j + 1] * b[i] * b[j];
}

Out-of-bound access.

i + j < 5200 => i + j + 1 < 5200

You might have misunderstood the sentence I think.
Dropping the bigger median would leave the smaller one as the new median.

A quick example:
[1, 2, 3, 4] => Median = (2 + 3) / 2 = 2.5
(Drop 3)
[1, 2, 4] => Median = 2

I think this was asked a week ago. The OP perhaps deleted the thread, cannot find it now.

The 2 states are (It's a tree DP, so for each vertex i, we consider only its subtrees and itself):

1. Maximum number of edges with the vertex not "full" (ie. connected to no more than 1 vertex, the vertex can still connect to the parent).
2. Maximum number of edges with the vertex "full" (ie. connected to 2 vertices already).

I want to touch on the first few paragraphs.

I think the goal for the ACM-ICPC or the whole competitive programming scene is promote computer science (perhaps more on data science). To really excel in the competitions, one would still need to be reasonably proficient in various subjects in computer science.

Most of the people I was with ace in everything despite regularly participating in competitions.
This is also the case for many elite competitive programmers I know.

I'd say given your premise is false, it's kind of hard to discuss further.

As this is a problem from CodeChef,

Wouldn't it be better to raise a question on the CodeChef Forum?

Thank you :)

Added.

SBT (or Size-Balanced Tree) was reinvented in late 2006, and published in the 2007 China IOI Camp.

It was said to be an extremely-efficient balanced BST that supports common BST operations and is easy to implement.

Here's a link for reference
I have only just heard about it a while ago though. Never really did look into it.

Update: SBT was reinvented. A paper dating back to 1993

Np :)
Glad to hear that.

Feel free to contribute if you know any site that's not on the list.
I sincerely feel that there's plenty to be improved about this list :)

Thanks!

I have E-Maxx up there already :) (I place it higher now)

I've added igor's code archive to the list,
and shortened the Chinese IOI paper link so that the CF markdown interpreter would work correctly :)

Most lists I found classify their contents by problem types. (ie. The entries in the list of lists section)
The list I created is meant to be a semi-complete list that covers different aspects on a grander scale.
It's actually significantly different :)

Thanks for the link!

Good idea, there are too many great people to name :)

Thanks :)

Also added yeputons's Quora profile.

I did use DP for n > m actually.
With knapsack optimization, you can achieve something like O(M²logN) with pretty small constants.
Submission

In case you're curious,
Here is an interesting discussion (in Chinese sadly) on what algorithms/data structures was truly invented by Chinese sport programmers.

Of course myself I do not know any of these :P

The technique, or the term "Mo's Algorithm" ("莫隊算法" in Chinese) was originally thought of and popularized by 莫涛 (Mo Tao) and his teammates.

It was first used to tackle a problem from 2009 China IOI Camp: 小Z的袜子(hose) — authored by 莫涛 himself.
The problem was: given a sequence of integers, for any given interval, calculate the probability of choosing any 2 numbers and the 2 numbers are equal.

The technique itself certainly wasn't new. A Chinese PhD student studying in NYU surveyed this technique a while back. "Rectilinear Steiner Minimal Arborescence technique" mentioned in this paper — Carmel Kent, Gad M. Landau, Michal Ziv-Ukelson, On the Complexity of Sparse Exon Assembly (2005) seems to be identical to Mo's Algorithm. There could be earlier sources.

Only for Top 200 Div.1 users.

L01 as an example.
You'll see Prof. Erik's notes on the right, and the cool thing is that the notes actually sync with the video (It automatically switch from page to page based on where you're watching).
Another thing is that it provides scribe notes which I find useful for later review.

The link you gave is a course from Spring 2012. A classmate of mine discovered a mistake in one of the lectures which was corrected in Spring 2014. Therefore, I think in terms of correctness, Spring 2014 might be more reliable.

Just curious,

How did you know which code he copied? (Is there a tool for this or ?)

I think I used similar ideas.

Here is my code

I suggest to watch it here.

As for which ones are important, I honestly have no idea.
Most of these topics covered are really really hard.

I've only looked at A-N,
but my favorite problem in this set has to be problem L :)

Thank you for an interesting contest!

My solution doesn't have hashing actually.

What I did was: do a All-Pairs Shortest Path by using Dijkstra V times.
Then I enumerate through each edge, and see if the shortest path between any pairs of nodes pass that edge.

The whole solution works in O(V³ + E * V²).
The complexity is kind of lousy, but we have 8 minutes to work with.

Good luck :)

I am not sure what you mean by modified Dijkstra,
but I did solve it with Dijkstra.

Can you give us the link to the problem?
(to try and to verify this isn't a problem from an ongoing contest)

If they give T-shirts to Div.2, we will be seeing loads of fake Div.2 users.

Yes it does. It will occur again and again.

Incidentally there is an easier way to resolve this.

1. Click on the icon to the left of the URL.
   
2. Select uva.onlinejudge.org and click Remove
   

Sorry for giving a short answer there. It's not easy to explain.

Consider treating each bite as an entry and assume we bit 2 already ('U' from (0, n + 1) and 'L' from (n + 1, 0)).

Let's take 'U' for instance. Suppose our starting point is (x, y).
We need only to look at the entry to our immediate right.

1. Suppose the entry starts from (x2, y2).
2. If the entry is 'U' and it reaches (x2, y3), then we can reach (x, y3).
3. If the entry is 'L' and it reaches (x3, y2), then we can reach (x, y2).

Similarly with 'L', we only need to look at the entry to our immediate left.

Now the only thing to consider is how to use an ordered container to store the entries.

The short version of Case of Chocolate requires quite a bit of observations (and proofs).

You cannot understand it through the code itself.

The short explanation is that you only need to look at 1 of your neighbors to tell the result.

You should print any of them.

• Edit: incorrect.

Lucas' theorem stated that p must be a prime.
The OP said he needed nCr modulo a prime power (p^SomeNumber).

I'm not sure whether Lucas' theorem still holds.

Scoreboard has been updated (also with solutions!)

It looks like tourist used the strategy everyone speculated for A, B and E (His solutions for small and large are identical).
tomek's Simulated Annealing solutions to D and E are really interesting too.

-

Oh and for a good laugh, look at the filename for tourist's solution to C-small.

Now for anything counted in C_n, take all the elements that are not in a partition yet and put them together in a set with n + 1

I love the idea here :)
Also thank you for pointing us to Bell numbers (I love combinatorics!).
It took me a day (not in a good health condition atm, feeling stupid) to grasp all these.

This is a difficult book for a self-learner. (at least for me)

I highly recommend Introduction to Algorithms (SMA 5503) — MIT lectured by one of the coauthors — Prof. Charles Leiserson (The 'L' of CLRS) and Prof. Erik Demaine who is a bright and fantastic teacher (Perhaps you've heard about Cartesian Trees(treaps)?).
I especially love the materials which offer more intuitive (and perhaps easier) proofs.

In case you need solutions when you're stuck, here is a CLRS Study Group.
But note that some solutions are apparently incorrect.

In case you want to know more about CLRS, consider giving Prof. Thomas Cormen (The 'C' of CLRS) a follow on quora :)
It's also worth mentioning that he recommends another book for starters — Algorithms Unlocked

You're the one being delusional.

Feel like googling "Taiwan" and look it up on wikipedia?

Oh wait, you can't :) (without using VPN, proxy)

This is just pathetic.

Oh and, this will be the last comment I made on this topic.

Not interested in arguing with some politics zealots.

Keep living in your own world where every country is yours essentially.

Speaking from a country clouded by all sorts of censorship, your comment is so trustworthy!

Okay I'm kidding, I kind of feel sorry for you,
since you've been brainwashed by a corrupted government since your birth :)

Of course, I still respect your freedom of neglecting the fact that Taiwan is an independent country and spitting out ignorant comments :)

Wow.
Didn't expect politics to be brought up on Codeforces.

Seriously?

Thank you so much!

I was looking for a tool like this :D

You don't really need LCA for this one. I don't have the energy to explain it right now.
However, consider doing a simple Prim/Kruskal algorithm first to find out an arbitrary MST,
then do the minimization through all edges (not on the MST) afterwards.

When you have the MST already, you can preprocess by starting from an arbitrary vertex and record on each vertex, the longest edge it has seen so far. This way, the query takes O(1) for each edge you check.

Ok now I think I know what you mean.

Your method is almost equivalent to a O(V²) algorithm I know.
Except that there's a tiny issue with your idea.
You need to minimize d over all edges, rather than iterations of Kruskals only. Fix that, and I think your idea should be correct :)

Like I said, I didn't solve the problem this way.

You can perhaps look at the author's solution.

You're welcome :)

Your solution (the link you gave on the main post) doesn't check for collisions.

For example, you will visit both 1 + 1/2 and 1/2 + 1 which shouldn't be necessary.

Your solution is not rubbish. You are just relatively inexperienced :)
The state space is simply way too large.
Even if we're only concerned with integers, we're looking at a set with 10¹⁸ states {1, 2, ..., 1e18}.

You're right. Made a typo there.
Thanks for pointing that out :)

Assuming you're asking the case with a > b
It's rather straightforward.

Let me explain the intuitions. We have 2 equations: (1) R = R_e + R₀, (2)
Notice equation (2) would yield results R < 1.
This means if is greater than 1 and we decompose it into (where N >= 1 and M < 1), N has to come from equation (1).

I have problems understanding your claim.

Can you write it in psuedo code or elaborate a bit more?

1 ≤ a, b ≤ 10¹⁸

Your conclusion is obviously correct, but far from sufficient to solve this problem.

I think Sweep Line Algorithm should work here.

Basic idea is sort the intervals, first by starting point then by ending point.
Then scan the edges from left to right.
Complexity would be O(ElogE) = O(ElogV).

I didn't solve the problem this way, so I cannot really go into details on this. In case I made a mistake, let me know :)

It's not a graph problem, but a math problem rather.

Consider f(a, b):

1. f(a, b) = a / b + f(a % b, b), if a > b
2. if a < b
   Solve
   => , which reduces the problem to f(a, b — a)
   which then leads us to f(a, b % a)
   f(a, b) = f(a, b % a) + b / a, if a < b
3. Special case comes when a = 1, but it should be trivial to see the answer.

-

By the way, I like this problem. Thank you for pointing me to it :)

d(3) = 9 actually.

[2, 9] overlaps with the interval [d(2), d(4)] = [2, 10]

I have explained his ideas in my other comment below.

My solution is based on this fact (This should be easier if you have some graph theory knowledge):

An edge exists in all shortest paths iff. it is a bridge in the shortest path graph

His idea is pretty interesting.
I am not sure if I understood it correctly, but here it goes:

1. Consider any valid shortest paths (Suppose the length of which is D).
2. As we traverse through the edges,
   The distance traversed starts from 0 (Starting vertex) to D (Terminal).
3. Now we consider an edge (u, v) on the shortest path graph.
   Suppose the shortest distance to u is d(u) and the shortest distance to v is d(v)
   This edge essentially allows us to go from d(u) to d(v).
4. For each edge, treat "d(u) to d(v)" as an interval [d(u), d(v)]
5. Recall (2) the distance traversed starts from 0 to D.
   If an interval doesn't overlap w ith other intervals (from other edges),
   then this means that if we would like to "pass through" any value of distance ,
   this edge is the only way to go, which means this edge always exists in the shortest paths.

Hope this helps.

No. The number of ways can be something like 2⁵⁰⁰⁰⁰.

The more correct way to do this is to module the number by one or several(just to be safe) big prime number(s). This is still incorrect nonetheless, but has a very small error rate.

Yes.

I took a look. Your submission runs in O(V²).
Reason: V Extract-Min & Relaxations, and Each iteration runs in O(V)
=> V * O(V) = O(V²)

No you don't need to. Refer to my submission

Problem E

Problem F

I think Problem E needs more explanation.
In case you don't understand the discussion, reply below and I'll explain :)
It needs some graph theory facts.