2013-09-12 17:39
原创声明:本作品采用知识共享署名-非商业性使用 3.0 版本许可协议进行许可,欢迎转载,演绎,但是必须保留本文的署名(包含链接),且不得用于商业目的。
GeeksforGeeks终于改版了。。经常去GeeksforGeeks上搜题,也经常能淘到许多宝,但是GeeksforGeeks给人最大的印象就是——乱,今天发现它终于改版了,各个目录都整理的清晰了,非常值得一看。
Topics
- Linked List
- Stack
- Queue
- Binary Tree
- Binary Search Tree
- Heap
- Hashing
- Graph
- Advanced Data Structure
- Array
- Matrix
- Misc
Singly Linked List:
- Introduction to Linked List
- Linked List vs Array
- Linked List Insertion
- Linked List Deletion
- A Programmer’s approach of looking at Array vs. Linked List
- Find Length of a Linked List (Iterative and Recursive)
- Search an element in a Linked List (Iterative and Recursive)
- How to write C functions that modify head pointer of a Linked List?
- Write a function to get Nth node in a Linked List
- Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
- Print the middle of a given linked list
- Nth node from the end of a Linked List
- Write a function to delete a Linked List
- Write a function that counts the number of times a given int occurs in a Linked List
- Reverse a linked list
- Detect loop in a linked list
- Function to check if a singly linked list is palindrome
- Given a linked list which is sorted, how will you insert in sorted way
- Intersection point of two Linked Lists.
- Recursive function to print reverse of a Linked List
- Remove duplicates from a sorted linked list
- Remove duplicates from an unsorted linked list
- Pairwise swap elements of a given linked list
- Practice questions for Linked List and Recursion
- Move last element to front of a given Linked List
- Intersection of two Sorted Linked Lists
- Delete alternate nodes of a Linked List
- Alternating split of a given Singly Linked List
- Merge two sorted linked lists
- Identical Linked Lists
- Merge Sort for Linked Lists
- Reverse a Linked List in groups of given size
- Reverse alternate K nodes in a Singly Linked List
- Delete nodes which have a greater value on right side
- Segregate even and odd nodes in a Linked List
- Detect and Remove Loop in a Linked List
- Add two numbers represented by linked lists | Set 1
- Delete a given node in Linked List under given constraints
- Union and Intersection of two Linked Lists
- Find a triplet from three linked lists with sum equal to a given number
- Rotate a Linked List
- Flattening a Linked List
- Add two numbers represented by linked lists | Set 2
- Sort a linked list of 0s, 1s and 2s
- Flatten a multilevel linked list
- Delete N nodes after M nodes of a linked list
- QuickSort on Singly Linked List
- Merge a linked list into another linked list at alternate positions
- Pairwise swap elements of a given linked list by changing links
- Given a linked list of line segments, remove middle points
- Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some Common nodes
- Can we reverse a linked list in less than O(n)?
- Clone a linked list with next and random pointer | Set 2
- Insertion Sort for Singly Linked List
- Point to next higher value node in a linked list with an arbitrary pointer
Circular Linked List:
- Circular Linked List Introduction and Applications,
- Circular Linked List Traversal
- Split a Circular Linked List into two halves
- Sorted insert for circular linked list
Doubly Linked List:
- Doubly Linked List Introduction and Insertion
- Delete a node in a Doubly Linked List
- Reverse a Doubly Linked List
- The Great Tree-List Recursion Problem.
- Copy a linked list with next and arbit pointer
- QuickSort on Doubly Linked List
- Swap Kth node from beginning with Kth node from end in a Linked List
- Introduction to Stack
- Infix to Postfix Conversion using Stack
- Evaluation of Postfix Expression
- Reverse a Sting using Stack
- Implement two stacks in an array
- Check for balanced parentheses in an expression
- Next Greater Element
- Reverse a stack using recursion
- The Stock Span Problem
- Design and Implement Special Stack Data Structure
- Implement Stack using Queues
- Design a stack with operations on middle element
- How to create mergable stack?
- How to efficiently implement k stacks in a single array?
- Iterative Tower of Hanoi
- Queue Introduction and Array Implementation
- Linked List Implementation of Queue
- Applications of Queue Data Structure
- Priority Queue Introduction
- Deque (Introduction and Applications)
- Implement Queue using Stacks
- Check whether a given Binary Tree is Complete or not
- Find the largest multiple of 3
- Find the first circular tour that visits all petrol pumps
- Maximum of all subarrays of size k
- An I nteresting Method to Generate Binary Numbers from 1 to n
- How to efficiently implement k Queues in a single array?
- Binary Tree Introduction
- Handshaking Lemma and Interesting Tree Properties
- Binary Tree Properties
- Types of Binary Tree
- Applications of tree data structure
- Tree Traversals
- Threaded Binary Tree
- Size of a tree
- Determine if Two Trees are Identical
- Maximum Depth or Height of a Tree
- Write a C program to Delete a Tree.
- Write an Efficient C Function to Convert a Binary Tree into its Mirror Tree
- If you are given two traversal sequences, can you construct the binary tree?
- Given a binary tree, print out all of its root-to-leaf paths one per line.
- The Great Tree-List Recursion Problem.
- Level Order Tree Traversal
- Count leaf nodes in a binary tree
- Level order traversal in spiral form
- Check for Children Sum Property in a Binary Tree.
- Convert an arbitrary Binary Tree to a tree that holds Children Sum Property
- Diameter of a Binary Tree
- How to determine if a binary tree is height-balanced?
- Inorder Tree Traversal without Recursion
- Inorder Tree Traversal without recursion and without stack!
- Root to leaf path sum equal to a given number
- Construct Tree from given Inorder and Preorder traversals
- Given a binary tree, print all root-to-leaf paths
- Double Tree
- Maximum width of a binary tree
- Foldable Binary Trees
- Print nodes at k distance from root
- Get Level of a node in a Binary Tree
- Print Ancestors of a given node in Binary Tree
- Check if a given Binary Tree is SumTree
- Check if a binary tree is subtree of another binary tree
- Connect nodes at same level
- Connect nodes at same level using constant extra space
- Populate Inorder Successor for all nodes
- Convert a given tree to its Sum Tree
- Vertical Sum in a given Binary Tree
- Find the maximum sum leaf to root path in a Binary Tree
- Construct Special Binary Tree from given Inorder traversal
- Construct a special tree from given preorder traversal
- Check whether a given Binary Tree is Complete or not
- Boundary Traversal of binary tree
- Construct Full Binary Tree from given preorder and postorder traversals
- Iterative Preorder Traversal
- Morris traversal for Preorder
- Linked complete binary tree & its creation
- Ternary Search Tree
- Segment Tree | Set 1 (Sum of given range)
- Largest Independent Set Problem
- Iterative Postorder Traversal | Set 1 (Using Two Stacks)
- Iterative Postorder Traversal | Set 2 (Using One Stack)
- Reverse Level Order Traversal
- Construct Complete Binary Tree from its Linked List Representation
- Convert a given Binary Tree to Doubly Linked List | Set 1
- Tree Isomorphism Problem
- Find all possible interpretations of an array of digits
- Iterative Method to find Height of Binary Tree
- Custom Tree Problem
- Convert a given Binary Tree to Doubly Linked List | Set 2
- Print ancestors of a given binary tree node without recursion
- Difference between sums of odd level and even level nodes of a Binary Tree
- Print Postorder traversal from given Inorder and Preorder traversals
- Find depth of the deepest odd level leaf node
- Check if all leaves are at same level
- Print Left View of a Binary Tree
- Remove all nodes which don’t lie in any path with sum>= k
- Extract Leaves of a Binary Tree in a Doubly Linked List
- Deepest left leaf node in a binary tree
- Find next right node of a given key
- Sum of all the numbers that are formed from root to leaf paths
- Convert a given Binary Tree to Doubly Linked List | Set 3
- Lowest Common Ancestor in a Binary Tree | Set 1
- Find distance between two given keys of a Binary Tree
- Print all nodes that are at distance k from a leaf node
- Check if a given Binary Tree is height balanced like a Red-Black Tree,
- Print all nodes at distance k from a given node
- Print a Binary Tree in Vertical Order | Set 1
- Construct a tree from Inorder and Level order traversals
- Find the maximum path sum between two leaves of a binary tree
- Reverse alternate levels of a perfect binary tree
- Check if two nodes are cousins in a Binary Tree
- Check if a binary tree is subtree of another binary tree | Set 2
- Serialize and Deserialize a Binary Tree
- Print nodes between two given level numbers of a binary tree
- closest leaf in a Binary Tree
- Convert a Binary Tree to Threaded binary tree
- Print Nodes in Top View of Binary Tree
- Bottom View of a Binary Tree
- Perfect Binary Tree Specific Level Order Traversal
- Convert left-right representation of a bianry tree to down-right
- Print level order traversal line by line
- Minimum no. of iterations to pass information to all nodes in the tree
- Clone a Binary Tree with Random Pointers
- Given a binary tree, how do you remove all the half nodes?
- Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree)
- Check whether a binary tree is a full binary tree or not
- Find sum of all left leaves in a given Binary Tree
- Remove nodes on root to leaf paths of length < K
- Iterative Search for a key ‘x’ in Binary Tree
- Find maximum (or minimum) in Binary Tree
Quiz on Binary Tree Traversals
- Search and Insert in BST
- Deletion from BST
- Minimum value in a Binary Search Tree
- Inorder predecessor and successor for a given key in BST
- Check if a binary tree is BST or not
- Lowest Common Ancestor in a Binary Search Tree.
- Sorted order printing of a given array that represents a BST
- Inorder Successor in Binary Search Tree
- Find k-th smallest element in BST (Order Statistics in BST)
- Print BST keys in the given range
- Sorted Array to Balanced BST
- Find the largest BST subtree in a given Binary Tree
- Check for Identical BSTs without building the trees
- Add all greater values to every node in a given BST
- Remove BST keys outside the given range
- Check if each internal node of a BST has exactly one child
- Find if there is a triplet in a Balanced BST that adds to zero
- Merge two BSTs with limited extra space
- Two nodes of a BST are swapped, correct the BST
- Construct BST from given preorder traversal | Set 1
- Construct BST from given preorder traversal | Set 2
- Floor and Ceil from a BST
- Convert a BST to a Binary Tree such that sum of all greater keys is added to every key
- Sorted Linked List to Balanced BST
- In-place conversion of Sorted DLL to Balanced BST
- Find a pair with given sum in a Balanced BST
- Total number of possible Binary Search Trees with n keys
- Merge Two Balanced Binary Search Trees
- Binary Tree to Binary Search Tree Conversion
- Transform a BST to greater sum tree
- Inorder predecessor and successor for a given key in BST
- K’th Largest Element in BST when modification to BST is not allowed
- How to handle duplicates in Binary Search Tree?
Quiz on Balanced Binary Search Trees
- Binary Heap
- Binomial Heap
- Heap Sort
- K’th Largest Element in an array
- Sort an almost sorted array/
- Sort an almost sorted array/
- Tournament Tree (Winner Tree) and Binary Heap
- Hashing Introduction
- Print a Binary Tree in Vertical Order
- Find whether an array is subset of another array
- Union and Intersection of two Linked Lists
- Find a pair with given sum
- Check if a given array contains duplicate elements within k distance from each other
- Find Itinerary from a given list of tickets
- Find number of Employees Under every Employee
Introduction, DFS and BFS:
- Graph and its representations
- Breadth First Traversal for a Graph
- Depth First Traversal for a Graph
- Applications of Depth First Search
- Applications of Breadth First Traversal
- Detect Cycle in a Directed Graph
- Detect Cycle in a an Undirected Graph
- Detect cycle in an undirected graph
- Longest Path in a Directed Acyclic Graph
- Topological Sorting
- Check whether a given graph is Bipartite or not
- Snake and Ladder Problem
- Minimize Cash Flow among a given set of friends who have borrowed money from each other
- Boggle (Find all possible words in a board of characters)
- Assign directions to edges so that the directed graph remains acyclic
Minimum Spanning Tree:
- Prim’s Minimum Spanning Tree (MST))
- Applications of Minimum Spanning Tree Problem
- Prim’s MST for Adjacency List Representation
- Kruskal’s Minimum Spanning Tree Algorithm
- Boruvka’s algorithm for Minimum Spanning Tree
Shortest Paths:
- Dijkstra’s shortest path algorithm
- Dijkstra’s Algorithm for Adjacency List Representation
- Bellman–Ford Algorithm
- Floyd Warshall Algorithm
- Johnson’s algorithm for All-pairs shortest paths
- Shortest Path in Directed Acyclic Graph
- Some interesting shortest path questions,
- Shortest path with exactly k edges in a directed and weighted graph
Connectivity:
- Find if there is a path between two vertices in a directed graph
- Connectivity in a directed graph
- Articulation Points (or Cut Vertices) in a Graph
- Biconnected graph
- Bridges in a graph
- Eulerian path and circuit
- Fleury’s Algorithm for printing Eulerian Path or Circuit
- Strongly Connected Components
- Transitive closure of a graph
- Find the number of islands
- Count all possible walks from a source to a destination with exactly k edges
- Euler Circuit in a Directed Graph
- Biconnected Components
- Check if a given graph is tree or not
- Karger’s algorithm for Minimum Cut
Hard Problems:
- Graph Coloring (Introduction and Applications)
- Greedy Algorithm for Graph Coloring
- Travelling Salesman Problem (Naive and Dynamic Programming)
- Travelling Salesman Problem (Approximate using MST)
- Hamiltonian Cycle
- Vertex Cover Problem | Set 1 (Introduction and Approximate Algorithm)
- K Centers Problem | Set 1 (Greedy Approximate Algorithm)
Maximum Flow:
- Ford-Fulkerson Algorithm for Maximum Flow Problem
- Find maximum number of edge disjoint paths between two vertices
- Find minimum s-t cut in a flow network
- Maximum Bipartite Matching
- Channel Assignment Problem
Quiz on Graph Minimum Spanning Tree
Advanced Lists:
- Memory efficient doubly linked list
- XOR Linked List – A Memory Efficient Doubly Linked List | Set 1
- XOR Linked List – A Memory Efficient Doubly Linked List | Set 2
- Skip List | Set 1 (Introduction)
- Self Organizing List | Set 1 (Introduction)
Trie:
- Trie | (Insert and Search)
- Trie | (Delete)
- Longest prefix matching – A Trie based solution in Java
- Print unique rows in a given boolean matrix
Suffix Array and Suffix Tree:
- Suffix Array Introduction
- Suffix Array nLogn Algorithm
- Suffix Tree Introduction
- Ukkonen’s Suffix Tree Construction – Part 1
- Ukkonen’s Suffix Tree Construction – Part 2
- Ukkonen’s Suffix Tree Construction – Part 3
- Ukkonen’s Suffix Tree Construction – Part 4,
- Ukkonen’s Suffix Tree Construction – Part 5
- Ukkonen’s Suffix Tree Construction – Part 6
- Generalized Suffix Tree
- Build Linear Time Suffix Array using Suffix Tree
- Substring Check
- Searching All Patterns
- Longest Repeated Substring,
- Longest Common Substring, Longest Palindromic Substring
AVL Tree:
Splay Tree:
B Tree:
Segment Tree:
Red-Black Tree:
- Red-Black Tree Introduction
- Red Black Tree Insertion.
- Red-Black Tree Deletion
- Program for Red Black Tree Insertion
Others:
- Ternary Search Tree
- Interval Tree
- Implement LRU Cache
- Sort numbers stored on different machines
- Find the k most frequent words from a file
- Given a sequence of words, print all anagrams together
- Tournament Tree (Winner Tree) and Binary Heap
- Decision Trees – Fake (Counterfeit) Coin Puzzle (12 Coin Puzzle)
- Spaghetti Stack
- Data Structure for Dictionary and Spell Checker?
- KD Tree
- Binomial Heap
- KD Tree
- Binary Indexed Tree
- Given an array A[] and a number x, check for pair in A[] with sum as x
- Majority Element
- Find the Number Occurring Odd Number of Times
- Largest Sum Contiguous Subarray
- Find the Missing Number
- Search an element in a sorted and pivoted array
- Merge an array of size n into another array of size m+n
- Median of two sorted arrays
- Write a program to reverse an array
- Program for array rotation
- Reversal algorithm for array rotation
- Block swap algorithm for array rotation
- Maximum sum such that no two elements are adjacent
- Leaders in an array
- Sort elements by frequency | Set 1
- Count Inversions in an array
- Two elements whose sum is closest to zero
- Find the smallest and second smallest element in an array
- Check for Majority Element in a sorted array
- Maximum and minimum of an array using minimum number of comparisons
- Segregate 0s and 1s in an array
- k largest(or smallest) elements in an array | added Min Heap method
- Maximum difference between two elements
- Union and Intersection of two sorted arrays
- Floor and Ceiling in a sorted array
- A Product Array Puzzle
- Segregate Even and Odd numbers
- Find the two repeating elements in a given array
- Sort an array of 0s, 1s and 2s
- Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
- Find duplicates in O(n) time and O(1) extra space
- Equilibrium index of an array
- Linked List vs Array
- Which sorting algorithm makes minimum number of memory writes?
- Turn an image by 90 degree
- Next Greater Element
- Check if array elements are consecutive | Added Method 3
- Find the smallest missing number
- Count the number of occurrences in a sorted array
- Interpolation search vs Binary search
- Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
- Maximum of all subarrays of size k (Added a O(n) method)
- Find whether an array is subset of another array | Added Method 3
- Find the minimum distance between two numbers
- Find the repeating and the missing | Added 3 new methods
- Median in a stream of integers (running integers)
- Find a Fixed Point in a given array
- Maximum Length Bitonic Subarray
- Find the maximum element in an array which is first increasing and then decreasing
- Count smaller elements on right side
- Minimum number of jumps to reach end
- Implement two stacks in an array
- Find subarray with given sum
- Dynamic Programming | Set 14 (Maximum Sum Increasing Subsequence)
- Longest Monotonically Increasing Subsequence Size (N log N)
- Find a triplet that sum to a given value
- Find the smallest positive number missing from an unsorted array
- Find the two numbers with odd occurrences in an unsorted array
- The Celebrity Problem
- Dynamic Programming | Set 15 (Longest Bitonic Subsequence)
- Find a sorted subsequence of size 3 in linear time
- Largest subarray with equal number of 0s and 1s
- Dynamic Programming | Set 18 (Partition problem)
- Maximum Product Subarray
- Find a pair with the given difference
- Replace every element with the next greatest
- Dynamic Programming | Set 20 (Maximum Length Chain of Pairs)
- Find four elements that sum to a given value | Set 1 (n^3 solution)
- Find four elements that sum to a given value | Set 2 ( O(n^2Logn) Solution)
- Sort a nearly sorted (or K sorted) array
- Maximum circular subarray sum
- Find the row with maximum number of 1s
- Median of two sorted arrays of different sizes
- Shuffle a given array
- Count the number of possible triangles
- Iterative Quick Sort
- Find the number of islands
- Construction of Longest Monotonically Increasing Subsequence (N log N)
- Find the first circular tour that visits all petrol pumps
- Arrange given numbers to form the biggest number
- Pancake sorting
- A Pancake Sorting Problem
- Tug of War
- Divide and Conquer | Set 3 (Maximum Subarray Sum)
- Counting Sort
- Merge Overlapping Intervals
- Find the maximum repeating number in O(n) time and O(1) extra space
- Stock Buy Sell to Maximize Profit
- Rearrange positive and negative numbers in O(n) time and O(1) extra space
- Sort elements by frequency | Set 2
- Find a peak element
- Print all possible combinations of r elements in a given array of size n
- Given an array of of size n and a number k, find all elements that appear more than n/k times
- Find the point where a monotonically increasing function becomes positive first time
- Find the Increasing subsequence of length three with maximum product
- Find the minimum element in a sorted and rotated array
- Stable Marriage Problem
- Merge k sorted arrays | Set 1
- Radix Sort
- Move all zeroes to end of array
- Find number of pairs such that x^y > y^x
- Count all distinct pairs with difference equal to k
- Find if there is a subarray with 0 sum
- Smallest subarray with sum greater than a given value
- Sort an array according to the order defined by another array
- Maximum Sum Path in Two Arrays
- Check if a given array contains duplicate elements within k distance from each other
- Sort an array in wave form
- K’th Smallest/Largest Element in Unsorted Array, K’th Smallest/Largest Element in Unsorted Array in Expected Linear Time,
- K’th Smallest/Largest Element in Unsorted Array in Worst Case Linear Time
- Find Index of 0 to be replaced with 1 to get longest continuous sequence of 1s in a binary array
- Find the closest pair from two sorted arrays
- Given a sorted array and a number x, find the pair in array whose sum is closest to x
- Count 1’s in a sorted binary array
- Print All Distinct Elements of a given integer array
- Construct an array from its pair-sum array
- Find common elements in three sorted arrays
- Find the first repeating element in an array of integers
- Find the smallest positive integer value that cannot be represented as sum of any subset of a given array
- Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’
- Find position of an element in a sorted array of infinite numbers
- Can QuickSort be implemented in O(nLogn) worst case time complexity?
- Check if a given array contains duplicate elements within k distance from each other
- Find the element that appears once
- Replace every array element by multiplication of previous and next
- Check if any two intervals overlap among a given set of intervals
- Delete an element from array (Using two traversals and one traversal)
- Given a sorted array and a number x, find the pair in array whose sum is closest to x
- Find the largest pair sum in an unsorted array
- Online algorithm for checking palindrome in a stream
- Find Union and Intersection of two unsorted arrays
- Pythagorean Triplet in an array
- Maximum profit by buying and selling a share at most twice
- Search in a row wise and column wise sorted matrix
- Print a given matrix in spiral form
- A Boolean Matrix Question
- Print unique rows in a given boolean matrix
- Maximum size square sub-matrix with all 1s
- Print unique rows in a given boolean matrix
- Inplace M x N size matrix transpose | Updated
- Print Matrix Diagonally
- Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)
- Strassen’s Matrix Multiplication
- Create a matrix with alternating rectangles of O and X
- Find the row with maximum number of 1s
- Print all elements in sorted order from row and column wise sorted matrix
- Given an n x n square matrix, find sum of all sub-squares of size k x k
- Count number of islands where every island is row-wise and column-wise separated
- Find a common element in all rows of a given row-wise sorted matrix
- Given a matrix of ‘O’ and ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’
- Commonly Asked Data Structure Interview Questions | Set 1
- A data structure for n elements and O(1) operations
You can create a new Data Structure topic and discuss it with other geeks using Geeksforgeeks Q&A page. See already discussed Data Structure questions on forum.