osmanorhan's blog

By osmanorhan, history, 3 years ago, In English

Hey all,

We are excited to invite everyone to the Quora Programming Challenge 2022, a free programming competition open to participants from around the world*! The competition will take place on February 5, 2022 from 14:00 to 18:00 (UTC + 00:00). We had a successful challenge last year with great participation and positive feedback for the problems, so we’re excited to do it again this year!

Quora (https://www.quora.com/) is a platform to ask questions, get useful answers, and share what you know with the world. In this contest, we include some problems inspired by real-world challenges that Quora engineers faced building and growing the product. In addition to competitive programming-style questions, there will also be some machine learning problems. We hope that this contest will be fun for everyone!

You will be given several algorithm problems and a few machine learning problems.

  1. Algorithm problems: These are competitive programming-style questions that have strictly algorithmic solutions. It is possible to achieve a full score on these problems.
  2. Machine Learning problems: These are problems around machine learning concepts. Scoring is problem-dependent, based on a scaled accuracy metric. It may not be possible to achieve a full score on these problems.

The problems were prepared by Quora employees including KhaledRezk, vlchen888, Myungwoo, Hwan Seung Yeo, Ryan Cheu, and me. They were tested by gafeol, huikang, and many other Quora employees.

The top contestants will be able to win the following prizes:

  • 1st place: $3000 USD
  • 2nd place: $2000 USD
  • 3rd place: $1000 USD
  • 4th to 10th place: $200 USD
  • 11th to 20th place: $100 USD
  • Top 100 places: Quora T-Shirt

Our recruiting team will also be reaching out to top participants for their interest in interviewing for roles at Quora. We recently became a remote-first company, so you don’t have to relocate to work with us.

Hope to see you at the contest!

Register here by February 3, 2022 16:00 (UTC + 00:00): https://www.quora.com/careers/challenge.

For any feedback or questions, please comment on this post or email: programming-challenge@quora.com.

*Except for excluded countries. Full details, including the dates and rules of the competition, can be found here

  • Vote: I like it
  • +128
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Great initiative

»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Great, but Cuba isn't an available country :'(

»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

Hi all, I participated in this challenge last year. I got an interview and a shirt from the challenge.

I am currently two months into my new grad role at Quora. This is me with the shirt.

There are three of us are who are hired from the interviews from the competition, with a few more in the pipeline.

These are the last year's problems for reference, obtained from this Codeforces comment.

Feel free to reach out if you have any questions!

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    On what basis are participants divided into div 1 and div 2? I did not find any such preference during registration.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      It was more like session one and session two, held at different times with different questions. Participants could choose to participate in either or both of the sessions. The intention is to make it more convenient for participants of different timezones.

      This year we decided to have only one session, and they share one prize pool.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is there somewhere we can submit solutions to last year's problems?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We will not provide a venue to submit solutions to the last year's problems. However, when we invite the participants to try out our contest environment nearer to the contest date, we may feature an easy problem from the last year.

    You can refer to comments shared by other participants for some clues on how to solve them. Some of them may have shared their code too, and you can compare your code with theirs.

    For ML problems, it is difficult to compare and see if your solution works because it involves a very customized checker and hidden datasets. You can refer to my solutions, which were pretty high scoring for the ML problems.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are people from balkans not allowed to compete?

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Upcoming Practice Session!

Registration will be open until February 3, 2022 16:00 UTC, so it’s not too late to sign up! We will be sending out the login credentials and instructions to access the contest platform shortly after the registration closes.

As a reminder, the challenge will take place on February 5th, 2022 14:00 — 18:00 UTC.

To help you get familiar with the platform before the contest, we will be holding a practice session on February 3, 2022 18:00 UTC to February 4, 2022 18:00 UTC where you can login to the contest platform using your login credentials, and try out the example problem. The example problem is not representative to the difficulty level of the contest, but hopefully this would be helpful for you to get used to the input / output mechanisms that will be used in the contest.

If you encounter any issues, please reach out to us at programming-challenge@quora.com.

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it
Last Day Notice

Programming challenge will be held on February 5, 2022 from 14:00 to 18:00 (UTC + 00:00).

Don't forget to participate!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the level of problems according to codeforces rating?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hard to tell, there are easy to hard problems, as well as ML problems integrated into challenge

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the real contest be held in same website as practice round?

If so, where will be able to see the standings? (as there was no standings in practice round)

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Thank you so much for the amazing problems. Can we get something like an editorial after it ends?

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

I CAME TO WHINE

HOW THE FUCK DO YOU WRITE DCHT WITH ROLLBACK?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    Test are weak, my solution with copying cht for every children got 100 lol

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    You can use HLD technique and have $$$O(n \log^2 n)$$$ solution.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I suppose that we need keep cht for every path?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes we have a list of chts and when we go down on a light path we make another one and add it to the end of the list, when we are done with that subtree we can just pop it. When we go down on a heavy edge we don't add anything. For every node we always use the last added cht.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    You can use heavy light decomposition, maintaining O(log n) dynamic converx hull for chains from current node to root.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got sick at the end so I wrote some decomposition of hulls which passed but it's O(NsqrtNlgN) at best considering the set's constant factor it should be a little more still it's fucked up that this passes.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried persistent Li Chao tree but it ran out of memory. I wonder if it's possible to get it within bounds...

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What implementation did you use? I used persistent Li Chao tree using the implementation linked in the comments of https://mirror.codeforces.com/blog/entry/68363 and I got AC.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I rolled my own, and tried to optimize by using a vector + indices instead of pointers, but didn't work either.

        Did you use long long for the line slopes/intercepts with the linked implementation? Or had to stick with int?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No, I changed everything to int64_t, and also changed the maximum from 1e9 to 4e18.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did it. I created static array with 7'500'500 nodes instead of pointers.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I would get literally sick if I tried doing something like that :(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I used persistent Li Chao tree: https://mirror.codeforces.com/blog/entry/68363

    This contest was the first time I have ever used this data structure on any problem, LOL

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can write Persistent LiChao tree. I actually wrote it but failed to get AC due to some formatting issues while reading input in java (subtask 2, file 21 and subtask 3, file 49).

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like it

    Isn't there a simple and straightforward $$$O(n \log^2 n)$$$ solution? If you have vertices in dfs order, build a segment tree on it and store a CHT in every vertex. Now you only need to be able to add a new line (car) to a segment (which is adding a line to at most $$$\log n$$$ CHT's), and do point queries where you take the best value from every CHT on the way to the corresponding segment tree vertex.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I simply saved the changed values on the Li Chao Tree and then rollback. The complexity is O(nlogn)

»
3 years ago, # |
  Vote: I like it +70 Vote: I do not like it

tourist (Gennady Korotkevich) while submitting the last point on task to get 100.0 points instead of 99.0, that's was incredible remontada.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve Xuora?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Case work (n = 4k, n = 4k+1, n = 4k+2, n = 4k+3)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain, how will you find the (m — n) numbers.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I didn't solve it, but here's an idea I had after the contest ended:

        If we consider some m, then we want to find (m — n) numbers <= m where xor(1..m) = xor(the numbers we choose). Let k = xor(numbers we choose).

        We can get k like this: satisfy each bit from (msb, 0) in that order (msb is most significant bit). We can see that once we are done taking bits for some msb, we can jump down until the msb changes, and no matter what we choose we do not mess up the answer we already have.

        The problem with this is we need at least bitcount(k) moves to make it work. What if (m — n) is less than this? We can combine some bits and take them all at once. This is because we can find any number < 2^(msb) in [1..m]. Then we need at least min(bitcount(k), 2) moves to make it work.

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +9 Vote: I do not like it

    If $$$n$$$ is $$$4k + 3$$$, you're done. $$$\newline$$$ If $$$n$$$ is $$$4k$$$, $$$m = n + 1$$$. Remove 1. $$$\newline$$$ If $$$n$$$ is $$$4k + 2$$$, you can prove that unless $$$n + 2$$$ is of the form $$$2^k$$$, you can remove 2 numbers keeping $$$m = n + 2$$$. Otherwise, $$$m = n + 3$$$. $$$\newline$$$ Similarly, if $$$n$$$ is $$$4k + 1$$$, you can show that unless $$$n + 3$$$ is of the form $$$2^k$$$, you can remove 3 numbers keeping $$$m = n + 3$$$. Otherwise, $$$m = n + 4$$$.

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

In case anyone wants to upsolve the IP problem (not sure how strength of test data compares): https://codingcompetitions.withgoogle.com/kickstart/round/00000000004349ac/0000000000434880

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My code passed the Google one but failed the Quora one :( can you share your code?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why 96 for problem IP?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In my case, my solution was broken if one of the addresses started with 0.0.0.0 (and fixing that took me from 96 to 100) but not sure if it's the same for you.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    One possible issue is that (1 << 32) doesn't work, you need to use (1LL << 32).

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had 56 in problem IP and have no idea why. Did anyone experience a similar thing?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Question for anyone from quora, or anyone with knowledge of last year's contest result:

Upto what rank can people expect to get interview call from quora?

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve "subtracting?"

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Congratulations on the only full solve for cake!

    There are a few ways to subtract better than random

    • From classes that are overrepresented (this was most effective in internal testing)
    • From points of the same class that are close to each other
    • From points that are giving the strongest and correct prediction if evaluated with the trained model

    This requires some intuition on how classifiers, metrics and the black magic of gradient boosting decision tree works.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    33 points: for each point, find the distance to the closest point of the same class. Keep $$$n-k$$$ points with the maximum value. (kind of "deduplicating" the points)

    52 points: the same, but when calculating the value for each point $$$i$$$, only consider points $$$j > i$$$ (this way, if two points are close to each other, we don't remove both because of that, but only remove one).

    100 points: first, pick around $$$0.5 \cdot (n-k)$$$ points using algorithm X, then pick the remaining $$$0.5 \cdot (n-k)$$$ points using the above method. (and do a lot of parameter tweaking)

    Algorithm X: for each class, try to pick a representative subset of points of size $$$0.5 \cdot (n-k) / num_{classes}$$$. Start with an arbitrary point, then repeat adding the point with the largest sum (or min) of distances to the already picked points of the class.

    What were your approaches to cake and coldstart? In particular, I saw you solved coldstart very quickly, but my approach required a lot of tweaking too, so I wonder if there's anything simple. (My approach was built around finding training data records with at least 3 or 4 pairs <person; upvoted> in common with the query, then taking some kind of an average.)

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 8   Vote: I like it +28 Vote: I do not like it

      Cake: I modified bicsi's half-plane set: https://mirror.codeforces.com/blog/entry/61710. It maintains all half-planes that determine the border of the cake.

      Unfortunately, the version linked in that post didn't seem to compile, so I ended up copying a working version from https://infoarena.ro/monitor?task=camera, and then modifying it to dynamically maintain the area.

      For each employee, the idea is to first try the orientation of the plane that results in fewer half-planes being removed from the set. If that results in the remaining cake having less than half the area, we can afford to try the other orientation (and the number of vertices in the cake will halve). The runtime is $$$O(N\log N)$$$.

      Unfortunately, I didn't understand the code well enough to implement this so I ended up just picking an arbitrary vertex of the convex hull and first trying the orientation that resulted in this vertex still being inside the cake, and then trying the other. Definitely hackable but okay in the average case.

      I also ran into some floating-point issues (I think the __float128 in the code below is necessary). It is probably possible to make this WA ...

      Cake Code

      Coldstart: All you needed to do was modify one of huikang's solutions to last year's Quora challenge. :)

      Coldstart Code

      Congrats on the win! For "subtracting" I spent the last 20 minutes or so just resubmitting my nondeterministic solution that usually earned zero points but did manage to increase my score by a few points more than once. I suppose I was rather lucky that this earned me any points at all ...

      I also found it interesting that 20 of my points on "subtracting" came from printing out 0...k-1 ...

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Use FFT. $$$\newline$$$ $$$polyA(i) = 1$$$, if $$$s[i] = A$$$. Odd coefficients of $$$polyA * polyT$$$ give you the values where $$$A$$$ and $$$T$$$ match. Similarly compute this for $$$G$$$ and $$$C$$$, add and take max over the odd coefficients.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I had neither Karatsuba nor FFT in my library, so I quickly implemented Karatsuba and it was too slow.

      Tried FFT, it was also too slow. I guess people have optimized implementations in their libs if it worked for them?

      The limit on N was 300000, annoyingly only slightly above a power of two, hampering both Karatsuba and FFT. Changed the base case in Karatsuba from 32 to 40, still too slow.

      Unrolled manually the 40-40-loop in the base case of Karatsuba, also taking into account that we need only the odd coefficients. And now it passed...

      Not sure how it worked for other people, but my impression about that problem was that there was not much algorithmic thinking (the idea to use fast polynomial multiplication should be rather obvious for those who know the technique), more using prewritten algorithms and/or low-level optimizations.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I had to think about this problem a lot as I am not well versed with FFT or convolutions. But since I knew the definition of convolution, I was able to notice that property in the problem.

        I have no idea how to calculate a convolution fast so I used the AtCoder Library

        There was minimal implementation and the code ran pretty fast. I was only able to solve this "library" problem because of ACL. Overall it was more of algorithmic problem for me, so I liked it a lot.

        Code
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can we find the full standing of the contest?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the tree problem (dfs from node 1) then for each node check all ancestors ans[node] = min(ans[node] , ans[ancestor] + R[ancestor] + C[ancestor] * distance) What's wrong with this? I couldn't pass first subtask

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    A node can take rent from any ancestors of its ancestor. in the sample test case, node 4 took rent from node 1 instead of its parent 5.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ancestor i mean any node up in the tree (parents of parents .... etc)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    distance = distance from ancestor?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    It should be true, maybe overflow?

»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

For those who did not participate the contest and would like to follow the discussion, here is the problem statements (thanks to rfpermen for downloading these)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the solution for DNA?

I see a lot of people solved it, but I still can't figure out a linear solution

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +17 Vote: I do not like it

    It is a FFT problem.

    Let $$$polyA$$$ be a sequence of numbers $$$a_0, a_1, \dots, a_{n-1}$$$ where $$$a_i=1$$$ if the $$$i$$$th letter in the string is "A" and $$$a_i=0$$$ otherwise. Make similar sequences for $$$polyT$$$, $$$polyG$$$, and $$$polyC$$$.

    Now, take the convolution of $$$polyA$$$ and $$$polyT$$$ (this is where FFT comes in, because FFT calculates convolution very quickly). Let's say the convolution is the sequence $$$c_0, c_1, \dots, c_{2n-2}$$$. For any $$$1\leq i\leq n-1$$$, observe that $$$c_{2i-1}$$$ represents the number of A-T/T-A bonds that will occur when you fold the DNA string with $$$i$$$ bases on the left side of the fold.

    Now, take the convolution of $$$polyG$$$ and $$$polyC$$$, and let's say the convolution is the sequence $$$d_0, \dots, d_{2n-2}$$$. By similar reasoning, $$$d_{2i-1}$$$ represents the number of G-C/C-G bonds that will occur when you fold the DNA string with $$$i$$$ bases on the left side of the fold.

    Thus, the number of bonds that will occur when you fold the DNA string with $$$i$$$ bases on the left side of the fold is $$$c_{2i-1}+d_{2i-1}$$$, and from here it is very easy to find the $$$i$$$ which maximizes $$$c_{2i-1}+d_{2i-1}$$$ using a simple for loop. Since we only do two convolution operations on sequences of length $$$n$$$, the complexity is $$$O(n log n)$$$.

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Not even able to solve the first problem, the challenge is ended, can u share ur code here. (i mean the IP BLOCKs}

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it
    import ipaddress
    n = int(input())
    lol = []
    for i in range(n):
    	lol.append(ipaddress.ip_network(input()))				
    result = ipaddress.collapse_addresses(lol)
    for x in result:
    	print(x)
    
»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Any place for upsolving?

Also, picture is a standard problem, right? Count axis-aligned rectangles formed by line segments. I'm pretty sure I saw it at least once in a contest.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Have people received invitations for interviews or similar?