r/datastructure • • Jun 19 '20

Python program for Insertion sort

Thumbnail
itvoyagers.in
3 Upvotes

r/datastructure • • Jan 07 '19

Selection Sort Algorithm

4 Upvotes

Selection sort is conceptually the most simplest sorting algorithm. This algorithm will first find the smallest element in the array and swap it with the element in the first position, then it will find the second smallest element and swap it with the element in the second position, and it will keep on doing this until the entire array is sorted.

It is called selection sort because it repeatedly selects the next-smallest element and swaps it into the right place.


r/datastructure • • Jan 01 '19

Space Complexity of Algorithms

4 Upvotes

Whenever a solution to a problem is written some memory is required to complete. For any algorithm memory may be used for the following:

  1. Variables (This include the constant values, temporary values)

  2. Program Instruction

  3. Execution

Sometime Auxiliary Space is confused with Space Complexity. But Auxiliary Space is the extra space or the temporary space used by the algorithm during it's execution.


r/datastructure • • Nov 08 '19

Data Structure Interview Questions

Thumbnail
javatpoint.com
3 Upvotes

r/datastructure • • Jan 31 '19

Python Panda’s in modern C++

3 Upvotes

Last year I implemented a Pandas like data frame in C++. Since then, I have added a lot more functionality and documentation including views and a cool date/time class.

I appreciate your constructive criticism/suggestions.

https://github.com/hosseinmoein/DataFrame


r/datastructure • • Mar 30 '19

Linked List

5 Upvotes

Questions about linked lists used to be extremely popular with interviewers because although they are simple to implement, they test very important programming concepts (notably pointers) and still allow room for challenging questions. However, with the growth of Java, these types of questions are a little less common, but if you are applying for a C/C++ position, this is still a perennial classic.

A linked list is a data structure composed of nodes. Each node is represented by a class or struct and contains at least a data payload of some type as well as a pointer to the next node. The first node in a linked list is called a head, and is often also referred to confusingly as the linked list. The last element is called the tail.

Three different kinds of linked lists exist:

  1. Singly linked lists have a single pointer pointing to the next element in the list. The last pointer is empty or points to null, signaling the end of the list.

  2. Doubly linked lists have two pointers, one pointing to the next element and one pointing to the previous element. The head node's previous pointer points to null and the tail node's next pointer points to null to signal the end of the list.

  3. Circular linked lists usually represent buffers. They have no head or tail, and the primary issue is avoiding infinite traversals because of the cycle. These questions rarely come up in interview questions. Arrays are oftentimes a better substitute for a circular linked list, using the modulus operator to wrap around.

The most popular one by far is the singly linked list; when people refer to linked lists, you can assume they mean a singly linked list. Interview questions involving doubly linked lists are rare because many operations are trivial when dealing with them, plus the overhead of keeping twice as many pointers makes them less attractive in real life.

Linked lists have a lot of potential hazards. Lists can only be traversed in one direction, so you will always need to keep track of the head element; otherwise you lose the ability to access all of the elements in the list since you'll be unable to traverse the full list. Also, remember to check for null pointers.


r/datastructure • • Nov 12 '19

Everything you need to know about tree data structure

3 Upvotes

Everything you need to know about tree data structure

A recommended blog post about tree data structure.


r/datastructure • • Dec 29 '18

What is Stack in Data Structures

Thumbnail tutorialride.com
4 Upvotes

r/datastructure • • Jan 01 '19

Upper Bounds: Big-O

3 Upvotes

This notation is known as the upper bound of the algorithm, or a Worst Case of an algorithm.

It tells us that a certain function will never exceed a specified time for any value of input n.

The question is why we need this representation when we already have the big-Θ notation, which represents the tightly bound running time for any algorithm. Let's take a small example to understand this.

Consider Linear Search algorithm, in which we traverse an array elements, one by one to search a given number.

In Worst case, starting from the front of the array, we find the element or number we are searching for at the end, which will lead to a time complexity of n, where n represents the number of total elements.

But it can happen, that the element that we are searching for is the first element of the array, in which case the time complexity will be 1.

Now in this case, saying that the big-Θ or tight bound time complexity for Linear search is Θ(n), will mean that the time required will always be related to n, as this is the right way to represent the average time complexity, but when we use the big-O notation, we mean to say that the time complexity is O(n), which means that the time complexity will never exceed n, defining the upper bound, hence saying that it can be less than or equal to n, which is the correct representation.

This is the reason, most of the time you will see Big-O notation being used to represent the time complexity of any algorithm, because it makes more sense.


r/datastructure • • Dec 30 '18

What is Time Complexity

4 Upvotes

Time Complexity is a way to represent the amount of time required by the program to run till its completion. It's generally a good practice to try to keep the time required minimum, so that our algorithm completes it's execution in the minimum time possible.


r/datastructure • • Oct 13 '19

Is there any pattern in the data structure question by applying them, it would be possible to reach to the solution .

3 Upvotes

for example 2 pointer technique is there, are there any other techniques also present ?


r/datastructure • • Jan 01 '19

Lower Bounds: Omega

3 Upvotes

Big Omega notation is used to define the lower bound of any algorithm or we can say the best case of any algorithm.

This always indicates the minimum time required for any algorithm for all input values, therefore the best case of any algorithm.

In simple words, when we represent a time complexity for any algorithm in the form of big-Ω, we mean that the algorithm will take atleast this much time to cmplete it's execution. It can definitely take more time than this too.


r/datastructure • • Jan 01 '19

Asymptotic Notations

4 Upvotes

When it comes to analysing the complexity of any algorithm in terms of time and space, we can never provide an exact number to define the time required and the space required by the algorithm, instead we express it using some standard notations, also known as Asymptotic Notations.

When we analyse any algorithm, we generally get a formula to represent the amount of time required for execution or the time required by the computer to run the lines of code of the algorithm, number of memory accesses, number of comparisons, temporary variables occupying memory space etc. This formula often contains unimportant details that don't really tell us anything about the running time.

Let us take an example, if some algorithm has a time complexity of T(n) = (n2 + 3n + 4), which is a quadratic equation. For large values of n, the 3n + 4 part will become insignificant compared to the n2 part.

For n = 1000, n2 will be 1000000 while 3n + 4 will be 3004.

Also, When we compare the execution times of two algorithms the constant coefficients of higher order terms are also neglected.

An algorithm that takes a time of 200n2 will be faster than some other algorithm that takes n3 time, for any value of n larger than 200. Since we're only interested in the asymptotic behavior of the growth of the function, the constant factor can be ignored too.


r/datastructure • • May 13 '19

Algorithm for Bubble Sort

Thumbnail solutionfactory.in
7 Upvotes

r/datastructure • • Jan 01 '19

Types of Asymptotic Notations

3 Upvotes

We use three types of asymptotic notations to represent the growth of any algorithm, as input increases:

  1. Big Theta (Θ)

  2. Big Oh(O)

  3. Big Omega (Ω)


r/datastructure • • Dec 30 '18

Basic types of Data Structures

4 Upvotes

anything that can store data can be called as a data structure, hence Integer, Float, Boolean, Char etc, all are data structures. They are known as Primitive Data Structures.

Then we also have some complex Data Structures, which are used to store large and connected data. Some example of Abstract Data Structure are :

Linked List Tree Graph Stack, Queue etc. All these data structures allow us to perform different operations on data. We select these data structures based on which type of operation is required.

Linear - In Linear data structures,the data items are arranged in a linear sequence. Example: Array Non-Linear - In Non-Linear data structures,the data items are not in sequence. Example: Tree, Graph Homogeneous - In homogeneous data structures,all the elements are of same type. Example: Array Non-Homogeneous - In Non-Homogeneous data structure, the elements may or may not be of the same type. Example: Structures Static - Static data structures are those whose sizes and structures associated memory locations are fixed, at compile time. Example: Array Dynamic - Dynamic structures are those which expands or shrinks depending upon the program need and its execution. Also, their associated memory locations changes. Example: Linked List created using pointers


r/datastructure • • Mar 24 '19

Reversing a Linked List

Thumbnail
i.imgur.com
6 Upvotes

r/datastructure • • Mar 06 '19

Selection Sort In Python

5 Upvotes

r/datastructure • • Dec 30 '18

What is an Algorithm ?

6 Upvotes

An algorithm is a finite set of instructions or logic, written in order, to accomplish a certain predefined task. Algorithm is not the complete code or program, it is just the core logic(solution) of a problem, which can be expressed either as an informal high level description as pseudocode or using a flowchart.

Every Algorithm must satisfy the following properties:

Input- There should be 0 or more inputs supplied externally to the algorithm. Output- There should be atleast 1 output obtained. Definiteness- Every step of the algorithm should be clear and well defined. Finiteness- The algorithm should have finite number of steps. Correctness- Every step of the algorithm must generate a correct output.

An algorithm is said to be efficient and fast, if it takes less time to execute and consumes less memory space. The performance of an algorithm is measured on the basis of following properties :

  1. Time Complexity

  2. Space Complexity


r/datastructure • • Jan 01 '19

Tight Bounds: Theta

6 Upvotes

When we say tight bounds, we mean that the time compexity represented by the Big-Θ notation is like the average value or range within which the actual time of execution of the algorithm will be.

For example, if for some algorithm the time complexity is represented by the expression 3n2 + 5n, and we use the Big-Θ notation to represent this, then the time complexity would be Θ(n2), ignoring the constant coefficient and removing the insignificant part, which is 5n.

Here, in the example above, complexity of Θ(n2) means, that the avaerage time for any input n will remain in between, k1 * n2 and k2 * n2, where k1, k2 are two constants, therby tightly binding the expression rpresenting the growth of the algorithm.


r/datastructure • • Feb 10 '19

Best Books for Algorithms & Data Structures

8 Upvotes
  1. “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

  2. “Algorithms Unlocked” by Thomas H. Cormen

  3. “The Algorithm Design Manual” by Steven S. Skiena

  4. “Data Structures and Algorithms Made Easy: Data Structures and Algorithmic Puzzles” by Narasimha Karumanchi

  5. “Grokking Algorithms: An illustrated guide for programmers and other curious people” by Aditya Bhargava

  6. “Algorithms” by Robert Sedgewick and Kevin Wayne

  7. “Advanced Data Structures” by Peter Brass

  8. “Automate This: How Algorithms Came To Rule Our World” by Christopher Steiner


r/datastructure • • Dec 29 '18

The top data structures you should know for your next coding interview

Thumbnail
medium.freecodecamp.org
5 Upvotes

r/datastructure • • Dec 30 '18

What is Space Complexity

4 Upvotes

Its the amount of memory space required by the algorithm, during the course of its execution. Space complexity must be taken seriously for multi-user systems and in situations where limited memory is available.

An algorithm generally requires space for following components :

Instruction Space: Its the space required to store the executable version of the program. This space is fixed, but varies depending upon the number of lines of code in the program. Data Space: Its the space required to store all the constants and variables(including temporary variables) value. Environment Space: Its the space required to store the environment information needed to resume the suspended function.


r/datastructure • • Jan 06 '20

Data Structure beginner

Thumbnail datastructureseasy.blogspot.com
4 Upvotes

r/datastructure • • Nov 12 '19

Difference between Stack and Heap

2 Upvotes

This tutorial explains the differences between Stack and Heap data structure

#Stack #Heap #Differences

https://www.stechies.com/difference-between-stack-heap/