February 2019 ~ Ankur's Blog

Time Complexity: If we assume that insertion in a bucket takes O(1) time then steps 1 and 2 of the above algorithm clearly take O(n) time. The O(1) is easily possible if we use a linked list to represent a bucket (In the following code, C++ vector is used for simplicity). Step 4 also takes O(n) time as there will be n items in all buckets.

Heap Sort

Ankur's BlogFebruary 19, 2019Algorithm, GeeksForGeeks, Sorting No comments

Heap Sort

Time Complexity: Time complexity of heapify is O(nLogn). Time complexity of createAndBuildHeap() is O(n) and overall time complexity of Heap Sort is O(nLogn).

Radix Sort

Ankur's BlogFebruary 19, 2019Algorithm, Code Repository, Sorting No comments

Complexity: O(n+b)*logb(max_value)

Counting Sort

Ankur's BlogFebruary 19, 2019Algorithm, Code Repository, Sorting No comments

Binary Search Tree (BST)

Ankur's BlogFebruary 18, 2019Datastructure No comments

Binary Search Tree (BST) is a node-based binary tree data structure having the following properties:

The left subtree of a node contains only nodes with keys less than the node’s key.

The right subtree of a node contaisns only nodes with greater than the node’s Key.

The left and right subtree each must also be a binary search tree.

BST has some basic operation like Search, Insert, Delete, Traversal (In-order, pre-order, post-order).If we want to delete a node from BST, Firstly we search this node and delete this node.

Now we make a BST using some data and following the BST properties. The data is given below:

47,40,54,38,30,39,49,60,57,80;

Odd Sum SubSequence

Ankur's BlogFebruary 17, 2019Greedy No comments

problem statement:

You are given sequence *a[1]*, *a[2]*, ..., *a<[n]* of integer numbers of length *n*. Your task is to find such subsequence that its sum is odd and maximum among all such subsequences.
It's guaranteed that given sequence contains subsequence with odd sum.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You should write a program which finds sum of the best subsequence.

Solution:

Fractional Knapsack Problem

Ankur's BlogFebruary 17, 2019Algorithm, Code Repository, GeeksForGeeks, Greedy No comments

Fractional Knapsack Problem

Implementation: 01

Implementation: 02

Two Pointer

Ankur's BlogFebruary 17, 2019Algorithm, two pointer No comments

Resource Link:

Shakil Ahmed's Blog

The Two Pointer Algorithm

Problems:

Topic: two pointer

explanation: Shakil Ahmed's Blog

solution 01:

QuickSort

Ankur's BlogFebruary 15, 2019Algorithm, Code Repository, Divide and Conquer, Sorting No comments

Implementation:

Merge Sort

Ankur's BlogFebruary 15, 2019Algorithm, Divide and Conquer, Sorting No comments

Implementation:

Binary Search

Ankur's BlogFebruary 15, 2019Algorithm, Binary Search, Divide and Conquer, Searching No comments

Binary Search

01. বাইনারি সার্চ – ১(শাফায়েত আশরাফ)
02. বাইনারি সার্চ - ২(বাইসেকশন) - শাফায়েত আশরাফ
03. বাইসেকশন মেথড - আহমাদ ফাইয়াজ
04. বাইনারি সার্চ - হাসান আবদুল্লাহ
05. Painless Binary Search - আবু আসিফ খান চৌধুরী
06. Binary Search part - 1 - শাকিল আহমেদ
07. TopCoder Tutorial
08. One Problem from Spoj
09. Chinese problem solving blog
10. Good Resource (***)
11. HackerEarth1, HackerEarth2
12. TopCoder
13. GeeksForGeeks

Implementation:

complexity: O( nodes + edges).

Problem:

Spoj:

1. PPATH - Prime Path

2. ONEZERO - Ones and zeros

3. WATER - Water among Cubes

4. KATHTHI - KATHTHI

5. NAKANJ - Minimum Knight moves !!!

Codechef:

1. Chef and Digit Jumps

uva:

1. 10004 - Bicoloring

2. 336 - A Node Too Far

3. 567 - Risk

4. 10653 - Bombs! NO they are Mines!!

5. 439 - Knight Moves

6. 762 - We Ship Cheap

7. 429 - Word Transformation

LightOj:

1094 - Farthest Nodes in a Tree ( tree Diameter)

1257 - Farthest Nodes in a Tree (II) (tree diameter)

E-Maxx blog problemlist link

Topic: DFS

Topic: BFS

Concept: সব গুলা কম্পোনেন্ট এ চেক করবো সমান পরিমান টাকা আছে কিনা।

Topic: Topological Sorting

Resource Link

TopSort using DFS:

TopSort using BFS: (Kahn’s algorithm)

Topic: dijkstra

solution 01:

Resource Link

Topic: combinatorics + Binomial Coefficient

Topic: BigMod

solution:

Topic: Counting.

Topic: DFS

Solution 01:

Topic: BFS, Flood Fill, DFS

Resource Link:

টিউটোরিয়াল গুলো ক্রম অনুযায়ী সাজানো নাই।

Bucket Sort

Heap Sort

Complexity: O(n+b)*logb(max_value)

Binary Search Tree (BST) is a node-based binary tree data structure having the following properties:

The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contaisns only nodes with greater than the node’s Key. The left and right subtree each must also be a binary search tree.

problem statement:

Solution:

Resource:

Implementation: 01

Implementation: 02

Resource Link:

Problems:

Topic: two pointer

explanation: Shakil Ahmed's Blog

solution 01:

Resources:

Concept:

Implementation:

Resource Link

Implementation:

Resource Link

The left subtree of a node contains only nodes with keys less than the node’s key.

The right subtree of a node contaisns only nodes with greater than the node’s Key.

The left and right subtree each must also be a binary search tree.