All posts by admin

Selection sort

https://en.wikipedia.org/wiki/Selection_sort

Worst-case performance О(n2) comparisons, О(n) swaps
Best-case performance О(n2) comparisons, О(n) swaps

The idea is that we latch onto the first element and deem it being the minimum.
We then go through the rest of the array, and look for anything that is smaller. If so, we swap. This is 1 pass.

At this point, after the 1st pass, we deem first element as minimum. Then we move on
to the next element and call it the minimum. We do another pass and look in the leftover array
to see if there’s anything smaller than our minimum. If so, swap.

We keep doing this, pulling minimum numbers from the array and pushing it towards the front, until
all the elements are sorted from smallest to largest.

selectionsort-outer-inner

So there’s 2 loops: outer and inner.

Outer simply goes through the array.

The inner goes through the remaining elements AFTER the outer via a loop and compares it to the outer.

if the inner element is smaller than the outer element, then we swap. Essentially what is happening is that we are bringing in the smallest element to the front.

Example

Given an array, we make passes on it where:

– we select the starting value to be the minimum.
– we then make (length of array – 1) passes over it. (through all of our passes, the last element will be automatically sorted, so no need to do anything on it)
– For every pass, we need to do the very important action of pulling the minimum from the array and swapping it with the first value.

Example

…continuing on in the same fashion…

Eventually all the smallest number will be swapped to the front, resulting in the list being sorted.

full source

Create sync method around async operation

async method

sync version

Bubble Sort

http://www.geeksforgeeks.org/bubble-sort/

“Bubble” up the largest number in the array. Once that’s done, we “Bubble” again to the array-1 for the next largest number. We keep doing it until we have “Bubbled” every number in the array.

Think of it as looping through the array and looking at each tuple. If a tuple is where element1 > element2, then we swap. This way, the largest element of this run will “Bubble” up to the end. (very right side).

Due to us checking every tuple, we need to makes sure we check from 1..length-1 and NOT 1..length:

(5 1) 4 2 8 –> [1 5] 4 2 8, Here, algorithm compares the first two elements, and swaps since 5 > 1.
1 (5 4) 2 8 –> 1 [4 5] 2 8, Swap since 5 > 4
1 4 (5 2) 8 –> 1 4 [2 5] 8, Swap since 5 > 2
1 4 2 (5 8) –> 1 4 2 [5 8], Now, since these elements are already in order (8 > 5), algorithm does not swap them.

As tuples, the last index should be
element[last-1], element[last]

Therefore, we only need to check from (index 0) to (< lastIndex-1) because it does not make sense at all to swap the very last element of the array to its next element because the next element does not exist. The last swap we do should be data[lastIndex-1], data[lastIndex]. That is why we give outer - 1 into bubbleUpLargest.

Example

Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Numerical example

Given: 6 8 0 7 6 4 3 1 5 10

We compare tuples, so we loop a total of length – 1 times.

[6 8] 0 7 6 4 3 1 5 10

is 6 > 8? no

6 [8 0] 7 6 4 3 1 5 10

is 8 > 0? yes, swap

6 0 [8 7] 6 4 3 1 5 10

is 8 > 7? yes, swap

6 0 7 [8 6] 4 3 1 5 10

is 8 > 6? yes, swap

6 0 7 6 [8 4] 3 1 5 10

is 8 > 4? yes, swap

6 0 7 6 4 [8, 3] 1 5 10

is 8 > 3? yes, swap

6 0 7 6 4 3 [8, 1] 5 10

is 8 > 1? yes, swap

6 0 7 6 4 3 1 [8, 5] 10

is 8 > 5? yes, swap

6 0 7 6 4 3 1 5 [8 10]

is 8 > 10? no

pass 1 finished, so as you can see 8 “bubbles up”, until it meets 10.

Since we’re done, we are confident that the last number is largest. 10 is done, so we move our lastIndex down and process the leftover array for the 2nd pass.

[6 0] 7 6 4 3 1 5 8 (10)

is 6 > 0? yes, swap

0 [6 7] 6 4 3 1 5 8

is 6 > 7? no, move on

0 6 [7 6] 4 3 1 5 8

is 7 > 6? yes, swap

0 6 6 [7 4] 3 1 5 8

is 7 > 4? yes, swap

0 6 6 4 [7 3] 1 5 8

is 7 > 3? yes, swap

0 6 6 4 3 [7 1] 5 8

is 7 > 1? yes, swap

0 6 6 4 3 1 [7 5] 8

is 7 > 5? yes, swap

0 6 6 4 3 1 5 [7 8]

is 7 > 8? no

pass 2 finished, so as you can see, 7 “bubbles up”.

0 6 6 4 3 1 5 7 (8) (10) so now, 8, 10 done. We need to process 0 6 6 4 3 1 5 7.

We move our lastIndex down and process the leftover array for the 3rd pass.

..this keeps going until all numbers are sorted from smallest to largest.

the bubble sort

bubbleUpLargest

Then in here, we simply go through all the elements and do its swapping. Think of it as
looping through tuples and swapping them.

The swap function is just a standard swap

Worst-case performance O(n^2)
Best-case performance O(n)
Average performance O(n^2)

The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted efficiently is built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex.

However, not only does insertion sort have this mechanism too, but it also performs better on a list that is substantially sorted (having a small number of inversions).

Bubble sort should be avoided in the case of large collections. It will not be efficient in the case of a reverse-ordered collection.

source code

Promise (js)

http://javascript.info/promise-basics
https://scotch.io/tutorials/javascript-promises-for-dummies
https://www.toptal.com/javascript/asynchronous-javascript-async-await-tutorial
https://stackoverflow.com/questions/39988890/do-javascript-promises-block-the-stack

Why do we need promises?

Say you have a url, when given two numbers, will return you the sum.
You give the url two numbers in its parameter, and issue a remote call to get the result.
Naturally, you need to wait for the result.

Sometimes, its slow in response, etc. You don’t want your entire process to be blocked while waiting for the result.

Calling APIs, downloading files, reading files are among some of the usual async operations that you’ll perform.

The Promise object represents the eventual completion (or failure) of an asynchronous operation and its resulting value.

So this means once your Promise starts running (whether executing a timer or downloading from the internet) execution will continue on down the code. Once your Promise finishes (resolve or reject), then execution returns to the callback that you give to your Promise.

In this tutorial, we use setTimeout to simulate this server request response time.

The problem happens when we want to do callbacks in succession

say we want to add 1, 2, then get the result, and add 3. The get that
result and add 4.

If the calculation functionality is on a server, and we do this through this via callbacks, it would look like this:


result
info: querying url http://www.add.com
result1: 6
info: querying url http://www.add.com
result2: 9
info: querying url http://www.add.com
result3: 17

The syntax is less user friendly. In a nicer term, It looks like a pyramid, but people usually refer this as “callback hell”, because the callback nested into another callback. Imagine you have 10 callbacks, your code will nested 10 times!

Solution – Promise

Promises were the next logical step in escaping callback hell. This method did not remove the use of callbacks, but it made the chaining of functions straightforward and simplified the code, making it much easier to read.

Using promises in our previous example would make it simple.

First, we declare a function addAsync with two numbers to add.

We create a Promise object. Within our new created Promise object, we have a callback function parameter. We provide code that we want to execute within this callback. The callback function itself, has two parameters: resolve, and reject. Once the code has been executed and result is received, it will call resolve/reject in our code. This is so that a ‘then’ can be chained later on.

How is it a then() can be chained later on? The Promise object is returned from our addAsync function, for others to use. In other words, when they execute this addAsync, they will be returned the Promise object.

The reason why we want to return the promise object is so that others can call then on it. Calling then on a Promise object means that you’ll get notified when a resolve or reject is called within the Promise. The first parameter callback of our then() will be triggered if its a resolve. 2nd parameter callback of our then() will be triggered if it’s a reject.

The then function simply waits for the resolve or reject to happen.
If its a resolve, the first callback parameter of the then will be executed. If reject, the 2nd callback parameter will be executed.

Within setup of a Promise instance, we do a setTimeout to simulate a remote request that takes 2 seconds just like our previous example. Notice
that we don’t deal with custom callbacks. We now use resolve and then for the results.

Promise object’s resolve will trigger then()

Further Chaining…

ref – https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise/then

Once a Promise is fulfilled or rejected, the respective handler function (onFulfilled or onRejected parameters of then() ) will be called asynchronously (scheduled in the current thread loop). The behavior of the handler function follows a specific set of rules.

If a handler function:

returns a value, the promise returned by then gets resolved with the returned value as its value

// much later…

output of aPromise is:

Promise {: 3}
__proto__: Promise
[[PromiseStatus]]: “resolved”
[[PromiseValue]]: 3

doesn’t return anything

the promise returned by then gets resolved with an undefined value

output of aPromise is:

Promise {: undefined}
__proto__: Promise
[[PromiseStatus]]: “resolved”
[[PromiseValue]]: undefined

throws an error

So if we only call the reject, it’ll only hit the reject handler like so:

output: REJECTED : Booo…less than 8.

Note that if you DO NOT HAVE a reject handler, the reject will automatically be taken care of in the catch handler.

Normally, the catch handler catches any thing throw in the Promise object.


output:

REJECTED : Ooopssiiie

There is a situation where where you have an async operation inside of your Promise object. As a result, you throw 1 second later. It won’t catch because the Promise object has already been executed.

The only thing that works is reject, which naturally gets caught, given there is no reject handler.

catch is not like then(), where then() waits for the resolve/reject. Catch DOES NOT WAIT for the throw

The idea here is that you use resolve/reject in your Promise to take care of any async operations so that the then() gets triggered when the async operation is done. Then, you go on with your throw/catches.

Never use async callbacks in your Promise object. Use resolve/reject first.

This is basically why you should not put async callbacks inside of promises.

Promise object returned at then() over-rides previous Promises.

Chaining the Promise

Let’s chain multiple Promises together.
1) The first promise is that if mom is happy she’ll give you the phone
2) Given 1), you then promise to show your friend the phone.

1)
Create the promise. If mom is happy, call resolve with the phone object.
If not happy, then call the reject with the error object.

2) Create the 2nd Promise

Chain em together

Let’s Chain the promises together. First, WillIGetNewPhone is the first promise. It runs, and when it resolves via .then, it will pass the phone object to the 2nd promise in obj showOff.

Once showOff resolves, it will then go to its resolve function definition and do the display.

finally, don’t forget to call askMom().

Mom, Dad example

Similarly

Waiting for all tasks to be done

Promise All

Promise All runs all its promises parallel. When all of its promises are done, it will then run its resolve.

Usages

https://medium.com/@ivantsov/promises-in-js-one-more-interview-question-6d59634a3463

Given:

Example 1

output:

foo start
new Promise in foo
foo Promise created and returned
foo resolved…!
bar start
new Promise in bar
bar Promise created and returned
bar resolved…!
result: bar resolved
finalResult: undefined

The reason why finalResult is undefined is due to:

Thus, bar() returns an object that resolves. The then() captures it and then at this point, there is nothing. Hence, we need to return another Promise object like so:

in order to propagate data further onto the next then().

Errors

Handling errors is basically the 2nd parameter. Just implement a callback for it and handle the parameter of your callback.

await vs then

ref – https://dev.to/masteringjs/using-then-vs-async-await-in-javascript-2pma

await is simply syntactic sugar that replaces a .then() handler with a bit simpler syntax. But, under the covers the operation is similar.

The code that comes after the await (that is within the async function) is basically put inside an invisible .then() handler.

JavaScript will pause the async function’s execution until the promise settles. All code that is after the await will wait (block) until the await settles.

With then(), the rest of the function will continue to execute just like how async/await lets all code below the async function run. When the Promise settles, the then() will then executes. So in other words, all code below await, is very similar to having a then.

Therefore, await is just an internal version of .then() (doing basically the same thing). The reason to choose one over the other doesn’t really have to do with performance, but has to do with desired coding style or coding convenience. Certainly, the interpreter has a few more opportunities to optimize things internally with await, but it’s unlikely that should be how you decide which to use. If all else was equal, I would choose await for the reason cited above. But, I’d first choose which made the code simpler to write and understand and maintain and test.

Used properly, await can often save you a bunch of lines of code making your code simpler to read, test and maintain. That’s why it was invented.

There’s no meaningful difference between the two versions of your code. Both achieve the same result when the axios call is successful or has an error.

Where await could make more of a convenience difference is if you had multiple successive asynchronous calls that needed to be serialized. Then, rather than bracketing them each inside a .then() handler to chain them properly, you could just use await and have simpler looking code.

Borrowing Methods (js)

http://javascriptissexy.com/javascript-apply-call-and-bind-methods-are-essential-for-javascript-professionals/

The slice() method returns a shallow copy of a portion of an array into a new array object selected from begin to end (end not included). The original array will not be modified.

apply, bind, call

https://hangar.runway7.net/javascript/difference-call-apply
https://javascript.info/bind

call

When invoking functions with call:

1) the 1st object is used as the ‘this’
2) additional arguments used with call will act as the function’s parameters.

Note that the first argument to call () sets the ‘this’ value. The other arguments after the first argument are passed as parameters to the avg () function.

another example for call

The functions sayHello, sayGoodybye are run with the ‘this’ context set to objects person1 and person2. The ‘this’ in the function will reference those objects.

The apply and call methods are almost identical when setting the this value except that you pass the function parameters to apply () as an array, while you have to list the parameters individually to pass them to the call () method.

In other words, both call and apply perform very similar functions: they execute a function in the context, or scope, of the first argument that you pass to them. Also, they’re both functions that can only be called on other functions.

The difference is when you want to seed this call with a set of arguments. Say you want to make a say() method that’s a little more dynamic:

call would be:

It runs the function in the context of the first argument, and subsequent arguments are passed in to the function to work with. So how does it work with more than one argument?

difference between call and apply

Both can be called on functions, which they run in the context of the first argument. In call the subsequent arguments are passed in to the function as they are, while apply expects the second argument to be an array that it unpacks as arguments for the called function.

Bind

Problem: Losing “this”

We already know that in JavaScript it’s easy to lose this. Once a method is passed somewhere separately from the object – ‘this’ is lost.

Here’s how it may happen with setTimeout:

As we can see, the output shows not “John” as this.firstName, but undefined!

That’s because f got the function user.sayHi, separately from the object. The last line can be rewritten as:

solution:

REMEMBER that functions bind objects. Hence, we get the function, bind an object to it, and run that function with ().

Here func.bind(user) as a “bound variant” of func, with fixed this=user.

parameters are passed as usual

Now let’s try with an object method. The object is user, its method is sayHi:

In the line (*) we take the method user.sayHi and bind it to user. The sayHi is a “bound” function, that can be called alone or passed to setTimeout – doesn’t matter, the context will be right.

Here we have the object ‘user’, its function ‘say’. ‘say’ has 1 argument ‘phrase’ which can be passed in normally after the bind.

Binding all functions in an object

If an object “user” has many methods and we plan to actively pass it around, then we could bind them all in a loop.

We use a for loop to go through all the keys in the object user. When the typekey is a function, it means we have stepped up to a function object. That means we have the reference to the function object. In turn, we then use the bind method to bind it to the object we want.

A function cannot be re-bound

The exotic bound function object returned by f.bind(…) remembers the context (and arguments if provided) only at creation time.

Note that the bind from a function to an object will always hold. It’s the returned object that CANNOT be bind again.

In the below example, we see that we try to bind var bound again, but the output is still John. However, calling bind on a function will always give you a successful bind.

callback (js)

http://javascriptissexy.com/understand-javascript-callback-functions-and-use-them/
http://javascript.info/callbacks

Asynchronous JavaScript with Callbacks

Callbacks are reference to function that gets passed around like variables.

When we pass a callback function as an argument to another function, we are only passing the function definition. We are not executing the function in the parameter. In other words, we aren’t passing the function with the trailing pair of executing parenthesis () like we do when we are executing a function.

Note that the callback function is not executed immediately. It is “called back” (hence the name) at some specified point inside the containing function’s body.

So why is this useful? Async execution + callback

Say you send off an HTTP request and you need to do something with the response. Instead of holding up your browser, you can use a callback to handle the response whenever it arrives. In the code example above, the async execution simulated by setTimeout first counts to 3 seconds, then it executes the callback after the 3 seconds.

The only reason setTimeout is used is to simulate an async operation that takes a certain time. Such operations could be reading from a text file, downloading things or performing an HTTP request.

Callbacks are closures. As we know, closures have access to the containing function’s scope, so the callback function can access the containing functions’ variables, and even the variables from the global scope.

Also notice there is no timeOut to simulate a HTTP request or a long standing operation, thus, it will process it as is.


output:

JavaScript Event Loop

Ok, now we know what functions and callbacks are, let’s see how they get used. Let’s look at a very simple asynchronous callback example:

If you’re used to procedural programs, this may seem a bit strange. JavaScript is based around something called the event loop. The simple version is that JavaScript runs a loop, and on each iteration (or tick) of this loop, one event will be processed. This event could be a timeout completing, an IO operation returning, an incoming HTTP request, etc. To help with this, JavaScript utilizes a message queue.

Certain operations will insert a message into the queue (e.g. setTimeout), and if there is a handler registered for the message, it will be executed.

In our above example, on tick 1, we do the following:

Log “before timeout”
Add a message handler (the message will be added to the message queue sometime after your timeout of 0 seconds)
Log “after timeout”

Now at some point in the future, JavaScript will insert a message into the queue to call your timeout handler. This will happen on a future “tick”, and that’s why “Timeout callback” is called after the other logs.

Asynchronous operations

Since JavaScript is single threaded using an event loop, we wouldn’t want to do blocking operations (e.g. reading a file) in the main loop. This would stop the loop until the blocking operation finished, meaning none of our other code could run. While this is how many languages work in their default configuration (e.g. Ruby), JavaScript & Node.js were designed to be run as a single process using non blocking operations only.

callback references global variables also

Notice how our callback also has access the global variables.

More Examples

let vs var vs const (js)

http://javascript.info/var
https://stackoverflow.com/questions/762011/whats-the-difference-between-using-let-and-var-to-declare-a-variable

How let and const are scoped in JavaScript


https://medium.com/javascript-scene/javascript-es6-var-let-or-const-ba58b8dcde75

var has no block scope

var variables are either function-wide or global, they are visible through blocks.

For instance:

If we used let test on the 2nd line, then it wouldn’t be visible to alert. But var ignores code blocks, so we’ve got a global test.

var HAS function scope

var cannot be block- or loop-local

vars are processed at the function start

var declarations are processed when the function starts (or script starts for globals).
In other words, var variables are defined from the beginning of the function, no matter where the definition is (assuming that the definition is not in the nested function).

So this code:

is same as:

..and same as this:

People also call such behavior “hoisting” (raising), because all var are “hoisted” (raised) to the top of the function.

So in the example above, if (false) branch never executes, but that doesn’t matter. The var inside it is processed in the beginning of the function, so at the moment of (*) the variable exists.

Assignments are not hoisted

Because all var declarations are processed at the function start, we can reference them at any place. But variables are undefined until the assignments.

In both examples above alert runs without an error, because the variable phrase exists. But its value is not yet assigned, so it shows undefined.

Let

let allows you to declare variables that are limited in scope to the block, statement, or expression on which it is used. This is unlike the var keyword, which defines a variable globally, or locally to an entire function regardless of block scope. An explanation of why the name “let” was chosen can be found here.

up vote
3526
down vote
accepted
The difference is scoping. var is scoped to the nearest function block and let is scoped to the nearest enclosing block, which can be smaller than a function block. Both are global if outside any block.

Also, variables declared with let are not accessible before they are declared in their enclosing block. As seen in the demo, this will throw a ReferenceError exception.

Block Visibility

Redeclaration

Assuming strict mode, var will let you re-declare the same variable in the same scope. On the other hand, let will not:

Global

They are very similar when used like this outside a function block.

More Examples

When using var, and there’s no function enclosed, the variable gets globally scoped. In other words, by definition,
var are function scoped. But since there is no function, it gets globally scoped.

let is blocked something

Any time you see a curly bracket, its a block. Functions are also blocks. Let and const are still going to be scoped to a function, but if inside of that function or if inside some other element that you have, it will be scoped to the closest set of curly brackets.

const

const is the same as let, the difference lies in that const cannot be reassigned. Let can.
However, keep in mind that properties of const can be reassigned.

const is a signal that the identifier won’t be reassigned.

let is a signal that the variable may be reassigned. i.e counter in a loop, value swap in algorithm.
It also signals that the variable will be used only in the block it’s defined in.

var is now the weakest signal available because it may or may not be reassigned. The variable may
or may not be used for an entire function, or just for the purpose of a block or loop.