# Simulating Tic Tac Toe

To Prove: In Tic Tac Toe, the probability of winning for the player who takes the first turn is more than the player who takes the second turn.

Proof: We try to simulate all the possible cases and find out the cases in which player First wins and the cases in which player two wins and the cases which results in a tie.

So, the probability of player1 winning is: 143856/255168 = 0.564 and the probability of player 2 winning is: 77904/255168 = 0.305 and the probability of a tie is: 127872/255168 = 0.501

# Function Currying

Implementation of lodash library’s _.curry method

Keep collecting all the arguments untill all the expected number of arguments(fnToCurry.length) aren’t received and at last call the fnToCurry with all the arguments.

# Amazon Frontend SDE interview question

Problem: define a sum function such that: sum(1,2,3)(4,10)() returns 20 and sum(1)(2)(3)() returns 6 and sum(1,2,3,4,5)(1,2,3)(1,10)() returns 32.

Note: last function call is always empty without any arguments passed in.

# Memoization in Javascript

Objective: Building a Higher Order function that returns the input function with memoization superpower.

This evolved version of the input function will cache the output corresponding to the given input, so that if in future we receive the same input then the corresponding output is not reevaluated but rather served from cache.

For example, if we have a function “add” which takes in numbers to add as input and returns the sum of those input numbers. So add(1,2,3) when called for the first time evaluates the sum 6, stores the result in the cache for the corresponding input and returns…

# Floyd Warshall’s All Pair Shortest Path Algorithm from Dynamic Programming Perspective.

Input: Given a weighted graph G with vertex set V and Edges E.

V represents the set of all vertices, E is a collection of pairs (i,j) representing an edge from i to j

Problem: Find the weight of the shortest path for all possible pair of vertices.

If we are having a graph with vertices V = {1,2,3….,n}.

If sp(i,j,k) = weight of the shortest path from vertex i to vertex j which can have vertices 1,2,3…k as intermediate nodes in that shortest path.

Then the final solution of the shortest path from vertex i to vertex j would…

# Bellman Ford’s Single Source Shortest Path algorithm from Dynamic Programming Perspective

Input: Given a weighted graph G with vertex set V and Edges E, a source vertex u ∈ V

V represents the set of all vertices, E is a collection of pairs (i,j) representing an edge from i to j

Problem: Find the weight of the shortest path from source vertex u to all the other vertices belonging to set V.

Shortest Path from source vertex u to any other vertex can have at most |V|-1 number of edges.

Given problem can be defined as:

if sp(i,e) represents weight of the shortest path from source vertex u to vertex i

# Bucket Sort Algorithm

Bucket sort is a non-comparison based sorting algorithm helpful in scenarios where your data to be sorted is uniformly distributed over a particular range.

Let’s say we are having an array with n elements. And all the elements in the range 0 to m-1.

Example: input arr: [23,15,21,9,2,10], here the range of elements is 0 to 23. So, n=6, m=24

To sort this array using bucket sort, we have to take the help of n buckets. Each bucket can store a list of elements from input array.

Note: here the Number of buckets we have taken is equal to the…

## Kapil Thukral

Get the Medium app