ishu9bansal / ideone Goto Github PK

1.0 1.0 1.0 161 KB

useful pieces of codes

C++ 100.00%

algorithms algorithms-and-data-structures binary-search modulo-arithmetics inverse-modulo directions-algorithm directions-iterator kmp-algorithm print-tree lru-cache

ideone's Introduction

ideone

will incrementally contain all my ideone codes

usage

Each folder consists of a readme file and associated code file.

README file contains the description of the problem statement, solution approach and complexity.

It also contains the ideone link of the code which will mostly be in runnable state, with some sample inputs.

Check out a user friendly view here!

ideone's People

Contributors

Stargazers

Watchers

Forkers

emkay-git

ideone's Issues

Lazy segment tree

Implement a lazy segment tree, with update and query operations over a range.

Scan a random shaped moving window across a 2d grid

Is there a way to scan (and sum) a random shape (say diamond, circle, etc.) over a 2D grid, and produce a grid of new values, in linear time?

Implement Order Statistic Tree

Interval Intersection

Write an efficient method to insert an interval in a data structure and get all the ranges intersecting with a given range.
The runtime should be proportional to the size of the intersection result.

sum of top k items in a steam

It will be implemented by a priority queue of size k.

Example use case https://leetcode.com/contest/biweekly-contest-93/problems/maximum-star-sum-of-a-graph/

In Place merging two sorted arrays

Neumaier's Algo

adding large and small decimal numbers without loosing the small numbers in the process

https://www.wikiwand.com/en/Kahan_summation_algorithm#/Further_enhancements

https://ideone.com/FQv34o

This is very similar to a filter array method. But this is much useful, with some added functionality. If we think the indices as pointers between the elements then it also gives us clear distinction when dealing with ranges in an array.

Use this submission as an example to set up something like this , and use something useful

https://leetcode.com/submissions/detail/1157513853/

Adding the code block for the same for faster code copying:

template <class T>
vector<int> pickIndices(const vector<T>& v, function<bool(const vector<T>&, int)> predicate) {
    vector<int> ans;
    for(int i=0; i<=v.size(); i++)
        if(predicate(v,i))
            ans.push_back(i);
    return ans;
}

bool isSorted(vector<int>& v) {
    vector<int> kinks = pickIndices<int>(v,
        [](const vector<int>& v, int i) -> bool {
               if(i>=v.size() || i<=0) return false;
               return v[i]<v[i-1];
           });
    return kinks.empty();
}

Create a d3 visual representation for explaining huffman encoding

https://observablehq.com/@benjaminadk/simple-binary-search-tree

Improve time complexity by using queues instead of map

ideone/huffman_coding/7BBdMz.cpp

Lines 15 to 18 in c5628fb

    
           unordered_map<char,int> h; 
        
           for(char c: s) 
        
           	h[c]++; 
        
           multimap<int, Node*> v;

Using queues in correct fashion will also lead to less variance in the encodings.

change the logic to handle INT_OVERFLOW case, for calculating middle value

ideone/binary_search/B0w11Y.cpp

Lines 22 to 30 in c5628fb

    
           int binarySearch(int l, int r, Comp comp, T& t){ 
        
           	int m = (l+r)/2; 
        
           	while(l<r){ 
        
           		if(comp(m,t))	l = m+1; 
        
           		else	r = m; 
        
           		m = (l+r)/2; 
        
           	} 
        
           	return m; 
        
           }

	unordered_map<char,int> h;
	for(char c: s)
	h[c]++;
	multimap<int, Node*> v;

	int binarySearch(int l, int r, Comp comp, T& t){
	int m = (l+r)/2;
	while(l<r){
	if(comp(m,t)) l = m+1;
	else r = m;
	m = (l+r)/2;
	}
	return m;
	}