.Net, Rails, and other stuff: algorithms

Showing posts with label algorithms. Show all posts

Monday, August 19, 2024

DSA - Leetcode - Some patterns

Tuesday, December 12, 2023

Leetcode type problem - Sub-Arrays problem

Generate number of sub arrays with a particular sum: E.g. nums = [1,1,1] with sum 2

arr = [1,1,1]
SUM =2
#arr = [1,2,2,3,4,5]
#SUM = 5

sub_arrays = []
arr = arr.sort

arr.each_with_index do |n, index|
  if n == SUM
    sub_arrays << [n]
    next
  end
  rest_of_array = arr[(index+1)..-1]
  temp_arr = [n]

  rest_of_array.each do |m|
    temp_arr << m
    if temp_arr.sum == SUM
      # We found a sub_array!
      sub_arrays << temp_arr
      # There might be duplicates of m, so let us remove m from temp_arr and continue
      temp_arr = temp_arr[0..temp_arr.length-2]
    end
    if temp_arr.sum < SUM
      # do nothing; we can continue to add more elements
    end
    if temp_arr.sum > SUM
      # discard all elements except n
      temp_arr = [n]
    end
  end
end

puts sub_arrays.to_s

Friday, September 8, 2023

'Nested set model' data structure - ChatGPT discussion

https://chat.openai.com/c/14a54f06-d8e7-42af-b60e-402d821412be

Adjacency List Model vs Nested Set Model - https://www.youtube.com/watch?v=0G58ot8obFs

Saturday, July 8, 2023

Algorithms Illuminated Omnibus Edition (September 2022)

https://www.algorithmsilluminated.org/

Wednesday, November 23, 2022

System Design Primer

https://github.com/donnemartin/system-design-primer

Tuesday, September 20, 2022

Courses suggested by Javinpaul (Twitter)

Best Software Architecture and Design Pattern Courses

1. Design Patterns in Java - bit.ly/3nYGrYR

2. Grokking the OOP Design - bit.ly/3pA4wFD

3. Master Microservices - bit.ly/2FNlleF

4. Software Architecture Patterns - bit.ly/38Ixqg5

5 Free Courses for Data Structure and Algorithms

1. Data Structure - bit.ly/3l4VxMj

2. Algorithms - bit.ly/3P45Gqi

3. A Visual Intro to Algorithms - bit.ly/3NcwIKx

4. Data Structures Java - bit.ly/2F5V1uW

5. more - bit.ly/3w2YQJY

5 Best Courses for Microservices

1. Microservice Architecture - bit.ly/3w1zGva

2. Principles - bit.ly/3ruSCR7

3. Scalable Microservices - bit.ly/3MaP7GS

4. Microservice with Java - bit.ly/2FNlleF

5. more - bit.ly/3PQzR3v

Thursday, September 1, 2022

Algorithms Books

https://github.com/GauravWalia19/Free-Algorithms-Books

Friday, August 12, 2022

Prerequisites for Algorithms by Jeff Erickson

Author lists below as the prerequisites for reading his book: (Below content has been copied from the Prerequisites pages of his book)

• Discrete mathematics: High-school algebra, logarithm identities, naive set theory, Boolean algebra, first-order predicate logic, sets, functions, equivalences, partial orders, modular arithmetic, recursive definitions, trees (as abstract objects, not data structures), graphs (vertices and edges, not function plots).

• Proof techniques: direct, indirect, contradiction, exhaustive case analysis, and induction (especially “strong” and “structural” induction). Chapter 0 uses induction, and whenever Chapter n−1 uses induction, so does Chapter n.

• Iterative programming concepts: variables, conditionals, loops, records, indirection (addresses/pointers/references), subroutines, recursion. I do not assume fluency in any particular programming language, but I do assume experience with at least one language that supports both indirection and recursion.

• Fundamental abstract data types: scalars, sequences, vectors, sets, stacks, queues, maps/dictionaries, ordered maps/dictionaries, priority queues.

• Fundamental data structures: arrays, linked lists (single and double, linear and circular), binary search trees, at least one form of balanced binary search tree (such as AVL trees, red-black trees, treaps, skip lists, or splay trees), hash tables, binary heaps, and most importantly, the difference between this list and the previous list.

• Fundamental computational problems: elementary arithmetic, sorting, searching, enumeration, tree traversal (preorder, inorder, postorder, levelorder, and so on).

• Fundamental algorithms: elementary algorism, sequential search, binary search, sorting (selection, insertion, merge, heap, quick, radix, and so on), breadth- and depth-first search in (at least binary) trees, and most importantly, the difference between this list and the previous list.

• Elementary algorithm analysis: Asymptotic notation (o, O, Θ, Ω, ω), translating loops into sums and recursive calls into recurrences, evaluating simple sums and recurrences.

• Mathematical maturity: facility with abstraction, formal (especially recursive) definitions, and (especially inductive) proofs; writing and following mathematical arguments; recognizing and avoiding syntactic, semantic, and/or logical nonsense.

Books:

Margaret M. Fleck. Building Blocks for Theoretical Computer Science, unpublished textbook, most recently revised January 2013. Available from http://mfleck.cs.illinois.edu/building-blocks/.

• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer. Mathematics for Computer Science, unpublished lecture notes, most recent (public) revision June 2018. Available from https://courses.csail.mit.edu/6.042/spring18/. (I strongly recommend searching for the most recent revision.)

• Pat Morin. Open Data Structures, most recently revised January 2016 (edition 0.1Gβ). A free open-content textbook, which Pat maintains and regularly updates. Available from http://opendatastructures.org/.