spring1843 / go-dsa

Go Data Structures and Algorithms is an open source tool for learning and rehearsing data structures and algorithms in Go.

Data Structures and Algorithms in Go 🚀

Welcome to Data Structures and Algorithms in Go! 🎉 This project is designed as a dynamic, hands-on resource for learning and practicing data structures and algorithms in the Go programming language.

• More than one hundred rehearsal problems, at least six problems for each of the fifteen topics
• Executable and comes with 100% test coverage, ensuring correctness and quality
• Completely free, community-editable, and continuously evolving
• Ability to study and practice in your favorite IDE, editor, or web browser

📚 Table of Contents

• Preface
• Complexity Analysis
• Data Structures
  • Arrays
    • Reverse Array In-place
    • Add Two Numbers Represented as Slices
    • Find Duplicate in Array
    • Zero Sum Triplets
    • Product of All Other Elements
    • Equal Sum Sub-arrays
    • Rotate K Times
    • Bubble Sort
    • Insertion Sort
  • Strings
    • The Longest Dictionary Word Containing Key
    • Look and Tell
    • In Memory Database
    • Number in English
    • Reverse Vowels in a String
    • Longest Substring of Two Unique Characters
    • Roman Numerals
  • Linked Lists
    • Linked List Serialization
    • Reverse Linked List In-place
    • Join Two Sorted Linked Lists
    • Keep Repetitions
    • Copy Linked List with Random Pointer
    • LRU Cache
  • Stacks
    • Max Stack
    • Balancing Symbols
    • Infix to Postfix Conversion
    • Evaluate Postfix
    • Basic Calculator
    • Longest Valid Parentheses
  • Queues
    • Queue Using Stacks
    • Circular Queue Array
    • Symmetrical Binary Tree
    • Generate Binary Numbers
    • Max Sub-array of size K
    • String Permutations
  • Hash Tables
    • Find Missing Number
    • List Elements Summing Up to K
    • Fastest Way to Cut a Brick Wall
    • Smallest Missing Positive Integer
    • Find Anagrams
    • Find Max Points on the Same Line
  • Trees
    • Serialize Binary Tree
    • Evaluate A Binary Expression Tree
    • Sorted Array to Balanced BST
    • Traverse Binary Tree
    • Reverse Binary Tree
    • Autocompletion
  • Heaps
    • Kth Largest Element
    • Merge Sorted Lists
    • Median in a Stream
    • Regular Numbers
    • Kth Closest Points to the Center
    • Sliding Max
    • Heap Sort
• Algorithms
  • Recursion
    • Reverse an integer recursively
    • Palindrome
    • Climbing Stairs
    • Exponentiation
    • Multiplication
    • Regular Expression Matching
    • Expression Operators
  • Divide and Conquer
    • Binary Search
    • Square Root with Binary Search
    • Rate Limit
    • Towers of Hanoi
    • Merge Sort
    • Quick Sort
  • Bit Manipulation
    • Division Without Multiplication or Division Operators
    • Middle Without Division
    • Addition Without Arithmetic Operators
    • Power of Two
    • Max Without Comparison Operators
    • Oddly Repeated Number
  • Backtracking
    • Permutations
    • Generate Parentheses
    • Phone Letter Combinations
    • Maze
    • Sudoku
    • N Queens
  • Graphs
    • Iteratively BFS and DFS
    • DAG Graphs
    • Topological Sort
    • Employee Headcount
    • Remove Invalid Parentheses
    • Cheapest Flights
    • Dijkstra's Algorithm
    • Word Ladder
    • Network Delay Time
    • Number of Islands
    • Dependency Order
  • Greedy Algorithms
    • Max Stock Profit
    • Activity Selector
    • Knapsack
    • Jump Game
    • Max Number
    • Task Scheduling
  • Dynamic Programming
    • Rod Cutting
    • Sum Up to Number
    • House Robber
    • Interleaving String
    • Min Deletions to Make a Palindrome
    • Word Distance

📋 Outline

All topics are discussed in README.md files in the corresponding directory. Each topic includes the following sections:

• 💡 Implementation: Overview of implementing the data structure or algorithm in Go.
• 📊 Complexity: Analysis of the time and space complexity of the data structure or algorithm.
• 🎯 Application: Discuss problems commonly solved using the data structure or algorithm.
• 📝 Rehearsal: Practice problems with links to tests that provide 100% coverage and example inputs and outputs.

go-dsa's Issues

Solution to product_of_all_other_elements.go is not in O(n)

I could be being really stupid. If so please correct me.

I believe that it's impossible to solve product_of_all_other_elements without either using division or going beyond the O(n) requirement.

The solution given in product_of_all_other_elements.go is basically O(2n) which goes against your requirements.

Am I wrong?

Why is the space complexity O(1)?

Describe the problem

In zero-sum triplets solution it says it's O(1) space complexity is that correct?

Expected behavior

There is memory allocation going on for output. So what would be the actual space complexity?

Wrong space complexity

Describe the problem

In the file array/product_of_all_other_elements.go - Line 9 - You initialised an array of length n.
Doesn't it make space complexity O(N). But you have written it O(1) in Line 3.

Redundant condition

https://github.com/spring1843/go-dsa/blob/main/array/reverse_inplace.go

i <= start+end/2 && i < end-i+start

The 2nd condition is redundant, I think

Comparison issue

https://github.com/spring1843/go-dsa/blame/adc15f7574794bfed14bc10c1689415323fa619c/array/bubble_sort.go#L7

the implementation is comparing the elements in a inefficient way

please see the comparison bellow

func bubbleSort(input []int) []int {
    swapped := true
    for swapped {
        swapped = false
        for i := 1; i < len(input); i++ {
            if input[i-1] > input[i] {
                input[i], input[i-1] = input[i-1], input[i]
                swapped = true
            }
        }
    }
    return input
}