Thursday 30 April 2020

SCALA


SCALA - Scalable Language

Scala Statically-Typed Language

 Scala is a Pure Object-Oriented Programming Language because in Scala, everything is an Object and everything is a value. Functions are values and values are Objects.
Scala does not have primitive data types and also does not have static members.

supports for
  • Pattern Matching
  • Function Currying
  • Implicits
  • Supports Closures

Advantages:
  • 100% Type-Safe Language
  • Immutability and No Side-Effects
  • Very Flexible Syntax - Simple and Concise Code
  • Supports all FP Features. Highly Functional.
  • Powerful Scala DSLs available
  • support for Akka Actor Model
  • Do More With Less Code
  • String interpolation
Drawbacks:
  • Backward Compatibility
  • Bit tough to Understand the Code for beginners

Type InferenceTypes can be inferred by the Scala Compiler at compile-time.


In Scala, “null” is an instance of type scala.Null type.


Advantages of case class:
  • By default, Scala Compiler adds toString, hashCode and equals methods. We can avoid writing this boilerplate code.
  • By default, Scala Compiler adds companion object with apply and unapply methods that’s why we don’t need new keyword to create instances of a case class.
  • By default, Scala Compiler adds copy method too.
  • We can use case classes in Pattern Matching.
  • By default, Case class and Case Objects are Serializable.
The following are the major advantages or benefits of a Case class over Normal Classes:
  • Avoids lots of boiler-plate code by adding some useful methods automatically.
  • By default, supports Immutability because it’s parameters are ‘val’
  • Easy to use in Pattern Matching.
  • No need to use ‘new’ keyword to create instance of Case Class.
  • By default, supports Serialization and Deserialization.
Scala Variance TypeSyntaxDescription
Covariant[+T]If S is subtype of T, then List[S] is also subtype of List[T]
Contravariant[-T]If S is subtype of T, then List[T] is also subtype of List[S]
Invariant[T]If S is subtype of T, then List[S] and List[T] are unrelated.
Arrays Vs List
Arrays are always Mutable where as List is always Immutable.
Once created, We can change Array values where as we cannot change List Object.
Arrays are Invariants where as Lists are Covariants.

“val” Vs “lazy val” 
“val” is used to define variables which are evaluated eagerly and 
“lazy val” is also used to define variables but they are evaluated lazily.
Lazy Evaluation means evaluating program at run-time on-demand that means when clients access the program then only its evaluated.

Scala solves Diamond Problem [Multiple Inheritance problem] using the rules defined is called Class Linearization.
Scala Compiler reads “extends B with C” from right to left and takes “display” method definition from lest most trait that is C.


A pure function is a function without any observable side-effects. That means it returns always same results irrespective how many times we call it with same inputs.


Scala’s for-comprehension


‘for/yield’ is used to iterate a collection of elements and generates new collection of same type. It does not change the original collection. It generates new collection of same type as original collection type.
For example, if we use ‘for/yield’ construct to iterate a List then it generates a new List only.
scala> for(l <- list) yield l*2 res0: List[Int] = List(2, 4, 6, 8, 10)

Option is a bounded collection in Scala, which contains either zero or one element. If Option contains zero elements that is None. If Option contains one element, that is Some.

A Monad can be described as an object that wraps another object. 
In Scala, a class object is covered with a monad. 
Monads wrap objects and offer two operations - Identity through units, and bind through flatMap.

Closure is a function in which the return value of a service is based on the amount of variables, which have been declared outside that function.
// defined the value of p as 10 
val p = 10  // p is a free variable
// define this closure. 
def example(a:double) = a*p / 100
Scala Closures are functions which uses one or more free variables and the return value of this function is dependent of these variable. 

Currying is a way to transform a role with multiple arguments into a series of different tasks with a single discussion each. This feature helps the developers when they are working with higher-order functions.

trait is a unique kind of Class that enables developers to use multiple inheritances. Although a trait can extend to only one class, a class can have many traits. However, unlike classes in Scala, you cannot instantiate traits.

“tail recursion” mechanism optimizes recursive functions so that they do not create new stack space and use the existing stack space.

 Scala-Based Frameworks to develop REST API

Play Framework In Play, we call REST API URLs as routes. We place all routes at once place in Play framework.
Scalatra Framework is very simple and easy Scala-based web framework to develop REST API
Spray Frameworkis very concise and built on top of Akka framework so it’s better to develop REST API using Actor Model.
Lift Frameworkallows routing using Pattern Matching concept.

ORM frameworks for Scala based applications:
  • Slick
  • Anorm
  • SORM(Scala ORM)
  • Squeryl
Testing Frameworks
  • Spec2
  • ScalaTest
  • ScalaCheck
  • Mokito















Friday 17 April 2020

Big O Notation

Big O Notation and Time Complexities



Time Complexity









Common Data Structure Operations

Data StructureTime ComplexitySpace Complexity
AverageWorstWorst
AccessSearchInsertionDeletionAccessSearchInsertionDeletion
ArrayΘ(1)Θ(n)Θ(n)Θ(n)O(1)O(n)O(n)O(n)O(n)
StackΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
QueueΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
Singly-Linked ListΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
Doubly-Linked ListΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
Skip ListΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n log(n))
Hash TableN/AΘ(1)Θ(1)Θ(1)N/AO(n)O(n)O(n)O(n)
Binary Search TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n)
Cartesian TreeN/AΘ(log(n))Θ(log(n))Θ(log(n))N/AO(n)O(n)O(n)O(n)
B-TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
Red-Black TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
Splay TreeN/AΘ(log(n))Θ(log(n))Θ(log(n))N/AO(log(n))O(log(n))O(log(n))O(n)
AVL TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
KD TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n)




Array Sorting Algorithms

AlgorithmTime ComplexitySpace Complexity
BestAverageWorstWorst
QuicksortΩ(n log(n))Θ(n log(n))O(n^2)O(log(n))
MergesortΩ(n log(n))Θ(n log(n))O(n log(n))O(n)
TimsortΩ(n)Θ(n log(n))O(n log(n))O(n)
HeapsortΩ(n log(n))Θ(n log(n))O(n log(n))O(1)
Bubble SortΩ(n)Θ(n^2)O(n^2)O(1)
Insertion SortΩ(n)Θ(n^2)O(n^2)O(1)
Selection SortΩ(n^2)Θ(n^2)O(n^2)O(1)
Tree SortΩ(n log(n))Θ(n log(n))O(n^2)O(n)
Shell SortΩ(n log(n))Θ(n(log(n))^2)O(n(log(n))^2)O(1)
Bucket SortΩ(n+k)Θ(n+k)O(n^2)O(n)
Radix SortΩ(nk)Θ(nk)O(nk)O(n+k)
Counting SortΩ(n+k)Θ(n+k)O(n+k)O(k)
CubesortΩ(n)Θ(n log(n))O(n log(n))O(n)