8 votes
Accepted

Queries to count points lying on arbitrary line

Note that via point-line duality (i.e. mapping each point $(p_x,p_y)$ to the line $y=p_x x - p_y$ and each line $y=mx +c$ to the point $(m,-c)$), this problem is equivalent to: given a set $L$ of $n$ ...
Discrete lizard's user avatar
  • 8,248
6 votes
Accepted

Improving a ranking system with "best rank"

Each query can be implemented to run in $O(\log n)$ time by lazily propagating appropriate operators on the binary search tree. The lazy propagation technique *1, is that it is possible to perform ...
pcpthm's user avatar
  • 2,348
5 votes
Accepted

Find Minimum Transformation Between Multisets of Lists of Cards

I think the variant with sets can be solved using bipartite matching. Build a complete bipartite graph, with one left vertex per set in s0 and one right vertex per set in s1. Also, if there are fewer ...
D.W.'s user avatar
  • 159k
4 votes

I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems

I don't think this is entirely a matter of opinion like the other commentor has said (though they are right, that it can be a bit opinionated or subjective, everyone finds different things easier/...
Minko_Minkov's user avatar
4 votes
Accepted

A data structure for an allocation-free dynamic sample rate buffer

The best name I can think of is derandomized or deterministic reservoir sampling. I don't know of any ready-made implementations.
orlp's user avatar
  • 13.4k
3 votes

Is Group Theory useful in Computer Science in areas other than cryptography?

Group theory is used all over the place in quantum computing. Some examples: The set of reversible quantum logic gates on $n$ qubits is the group $SU(2^n)$. Some important finite groups of quantum ...
shashvat's user avatar
  • 131
3 votes

Find Minimum Transformation Between Multisets of Lists of Cards

Update (or possible correction) to the answer of D.W.. Since we are given the move operations and not the swap operations, we can compute $\pi$ in polynomial time. The problem is known as the ...
Inuyasha Yagami's user avatar
3 votes

Optimal graph data structure for set of points that allows dynamic updates

You are looking for a data structure for nearest neighbor search that supports dynamic updates. I suggest reviewing Wikipedia, as it has a good overview of many different data structures. Inserting ...
D.W.'s user avatar
  • 159k
3 votes

Splitting a binomial heap into 3n/8 and 5n/8 binomial heap whereas 8 divides n with O(log(n)) time

If $n$ is even, you can split the heap into two heaps of size $\dfrac{n}2$: For each binomial tree in the heap, remove its first child; reconstruct a heap with all the children you removed. Since a ...
Nathaniel's user avatar
  • 15.5k
2 votes

How to maintain completely dynamic convex hull quickly?

You can use my code. I implemented the ideas from the paper by Overmars and van Leeuwen. https://github.com/sumeetshirgure/DynamicPlanarHull/tree/master
Sumeet Shirgure's user avatar
2 votes
Accepted

How to handle coplanarity in convex hull?

If You find a co-planar triangle candidate, it has to be one that does not contain any other points in that plane. I am not familiar with rust so here is a pseudo-code attempt to enhance your code: <...
DirkT's user avatar
  • 991
2 votes

Can you simulate the following process in $O(N.log N)$

Since the operation "add 1 to all values greater than or equal to i" preserves order, you can augment a self balancing BST with this operation. While the particulars are dependent on how the ...
Command Master's user avatar
2 votes
Accepted

Data structure for fast look up of ranges, but that allows insertion

You can achieve $O(\log n)$ time for all operations using a self-balancing binary tree. Augment the tree so that you can store a value $\delta$ in each internal node; the meaning is that we add $\...
D.W.'s user avatar
  • 159k
2 votes

Memory (physical addressing)

The whole point of using the abstraction of virtual addresses (which is to say, giving every process the illusion that it has all the memory reserved for itself) is to free the application software ...
Nathan Davis's user avatar
2 votes
Accepted

Creative solving of searching redundant connection in graph

This step is incomplete: sets[el].push(edges[i][1]); For edge $(2,3)$, only $3$ is getting added to the existing set $\{2,8\}$. And, only $2$ is getting added to existing set $\{3,7,9, \dotsc\}$. ...
Inuyasha Yagami's user avatar
2 votes
Accepted

Splay Trees - Sequential Access Theorem & lower bound for comparison-based sorting

There is nothing wrong in saying that if you access the nodes of a BST (not necessarily a splay tree) in symmetric order in time $O(n)$ then the sequence of the corresponding elements is sorted. ...
Steven's user avatar
  • 29.5k
2 votes
Accepted

Understanding the Internal Stack Frames in a Recursive Function Call

It might be helpful to think of call-stack frames as remembering "where to return to" when a function call returns. There are two recursive calls in your example (one for the left child, and ...
Sam Westrick's user avatar
2 votes

Checking equality of self-referential lists

We define the signature of an srlist $S$ as the set of finite sequences $a_i$ of integers such that $S[a_1][a_2][a_3]...[a_n]$ exists. It's not hard to see that two srlists are equal iff the have the ...
Command Master's user avatar
2 votes
Accepted

Data Structure for efficient nearest neighbor search using generalized distance?

You can use a CoverTree. It indexes objects purely by distance. One implementation is available here. I have my own implementation here (Java) which is based on a more recent publication "Faster ...
TilmannZ's user avatar
  • 764
2 votes
Accepted

Why boolean value in Python is 24/28 bytes?

A boolean value can be represented with just one bit, but are usually four or eight bytes long in most statically typed languages because dealing with values smaller than the register size (four or ...
Stand with Gaza's user avatar
2 votes

Does immutability in functional programming really exist?

Let me answer one of your not fully addressed points: Because of all above, immutability adds huge space complexity to a program You're kinda right on the concern over immutability adding huge space ...
Humoyun Ahmad's user avatar
2 votes

I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems

For data structures you need to learn - stack, queue, linked list, and binary search tree. These 4 should be enough for interviews. You can google them and you will know how to implement them. There ...
Andrew's user avatar
  • 51
2 votes
Accepted

Does a sorted sequence from in-order traversal imply a binary tree is a BST?

Indeed. A binary tree is a BST iff its inorder traversal is sorted. First: when is a binary tree a binary search-tree (BST)? I for any node of the tree all nodes in its left subtree are less than the ...
Hendrik Jan's user avatar
  • 30.6k
2 votes
Accepted

Prove that the number of comparisons between elements in binary heap build is at most (2n-2)

The first two proofs only work for a fully populated heap of height h, which contains n=2h-1 items. The third proof also works for partial heaps. Throughout this answer, i will use two functions ...
Rainer P.'s user avatar
  • 842
2 votes

Recursive formula for height of BST

The formula is wrong. Indeed, we can find by hand that $H(1) = 0$, $H(2) = 1$ and $H(3) = \frac95$ ($5$ different trees, $4$ of them being of height $2$, the last of height $1$). But: $$\frac13\sum\...
Nathaniel's user avatar
  • 15.5k
1 vote
Accepted

Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Each pair of adjacent words $w_i,w_{i+1}$ in the dictionary list $[w_1,\ldots,w_N]$ generates at most one edge in the DAG. Why "at most"? (a) because that edge may be present already and (b) ...
Kai's user avatar
  • 865
1 vote

Can a trie or DAWG loop?

I will try to answer your questions from my personal experience with tries. Some time ago I had to face a similar problem: I had to store all well-formed meaningful Italian words (300'000 more or less)...
Chaos's user avatar
  • 543
1 vote

Linked Lists, Ordered Pairs?

Now that you have defined ordered pairs, you can do what LISP does: $\operatorname{NIL}$ is a list and if you have a list $l = (a, b)$ then $a$ is a value and $b$ is a list. Of course, lists can be ...
Turambar's user avatar
1 vote

Should I concatenate three lists together or use two separate while loops in Python? Which option offers a better runtime complexity?

First, measure. If you can’t measure the difference then it doesn’t matter. Second, you don’t know the time complexity of add_term. You need to find its implementation and analyse its behaviour. ...
gnasher729's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible