Shawn

Must know things about Data Structure and Algorithms.

Published by

Traveller

on

The coding interview is hard because We have to remember the basic data structures and algorithms. For me, I received masters degree of computer science seven years ago. Most of the tech companies require the coding interview when you apply for a job. So I decided to summarize the data structure and algorithm.

Here is the list, and I’ll write the basic concept and will be solving problems using Swift

Complexity

  • Time Complexity

  • Space Complexity

Data Structures

  • Stack

  • Queue

  • Circular Queue

  • Linked List

  • Doubly Linked List

    1. Reverse Linked List

  • Hash Table

  • Tree

  • Binary Tree

    1. BFS

    2. DFS

      1. Pre-Order

        1. In-Order

        2. Post-Order

    3. Binary Search Tree [Ordered Binary Tree]

  • Dictionary

  • Set

  • Graph

  • Directed

    1. Undirected

    2. Graph using an Adjacency Matrix

    3. Graph using an Adjacency List and Set

    4. Depth First

    5. Breath First

    6. Topological Sort

    7. Weighted Graph

    8. Negative Weighted Graph

Algorithms

  • Stack

    • Match parenthesis in an expression

    • find the minimum element in a expression

    • stack in constant time

  • Sorting

    • Selection Sort

    • Insertion Sort

    • Bubble Sort

    • Shell Sort

    • Merge Sort

    • Quick Sort

  • Search

    • Linear Search [Brute Force]

    • Binary Search [Sorted List]

  • Binary Tree

    • Find the minimum value in a Binary Search Tree

    • Find the maximum depth of a Binary Tree

    • Mirror a Binary Tree

    • Count the number of structurally unique binary tree possible

    • print all nodes within a range in a binary search tree

    • check if a binary tree is a binary search tree

    • check if a path from toot to leaf node sums up to a certain value

    • print all paths from the root to the leaf nodes

    • find the least common ancestor for 2 nodes

  • Heap [Priority Queue]

    • The Binary Heap

      1. Minimum Heap

      2. Maximum Heap

      3. Balanced Binary Search Tree

      4. An array or A list

      5. Insert and remove from a Heap

      6. Heapify

      7. Heap Sort

      8. Merge K sorted lists into one sorted array

      9. maximum element in a minimum heap and K largest elements in a stream

      10. Find the median In a stream of elements

  • Graph

    • Shortest path algorithm

    • Shortest path in a weighted graph

    • Dijkstra’s Algorithm [Greedy Algorithm]

    • Bellman Ford Algorithm [Shortest path in negative weighted graph] [Greedy Algorithm]

    • Dealing with negative cycles in the weighted graph [Bellman Ford Algorithm]

    • Prim’s Algorithm for a Minimal Spanning Tree [Undirected Graph] [Greedy Algorithm]

    • Kruskal’s Algorithm for a Minimal Spanning Tree for Forest [Priority Queue] [Connected / Unconnected]

    • Find the shortest path In a weight graph

    • Design A course schedule considering pre request for courses

General Programming Problem

  • Basic Operation

  • Bit Manipulation

    • Set and Get n-th Bit

    • Print bits in Integer

    • Count the number of 1 bits

    • Reverse the bits in an Integer

  • Recursion

    • Find All subsets of A given set

    • Check whether 2 binary tree are the same

    • Paint Fill

    • Build A car given tasks and dependencies

    • Find all anagrams of a given word

    • Find a path a rat can travel through a maze

    • place 8 queens on a chess board

  • Palindrome

  • Find Distance

  • Run Length Encoding and Decoding

  • Game of Life

  • Break A Document Into Chunks

  • Add Two Numbers Represented by their Digits

  • Sudoku Validator

  • Incrementing A Number

 

Thanks for reviewing my post

Divjjot Singh ( 신승훈 )

Previous Post
Next Post