Stokastik

Machine Learning, AI and Programming

LeetCode : Smallest Rotation with Highest Score

Problem Statement Solution : As we can see that, we can easily come up with a solution. Rotate the array each time and compute the score. There are N possible rotations for an array of size N, and for each rotated position, computing the score for the array takes O(N) time complexity. Since the approach is very easy, we will not code this approach but will explore whether we can […]

Continue Reading →

LeetCode : Dungeon Game

Problem Statement Solution : This problem is probably towards high medium difficulty level but below the hard level of problems. At one glance, one can conclude that we can solve this problem using the dynamic programming technique and it is correct. The only difficulty is in identifying what value to memoize at each step during the King's journey towards the Princess. So this is how it works. The initial health […]

Continue Reading →

LeetCode : K Inverse Pairs Array

Problem Statement Solution : One of the strong heuristics that I generally use for solving counting problems in programming is that it is most likely a dynamic programming problem and most of the cases it is true, since most such counting problems can be defined recursively. In this problem, of counting the number of k-inverse pairs in an array of size 'n' (from 1 to n) can be defined recursively. […]

Continue Reading →

Dynamic Programming in NLP - Longest Common Subsequence

In this second part of the series on my posts on Dynamic Programming in NLP, I will be showing how to solve the Longest Common Subsequence problem using DP and then use modified versions of the algorithm to find out the similarity between two strings. LCS is a common programming question asked in many technical interviews. Given two strings (sequence of words, characters etc.) S1 and S2, return the number […]

Continue Reading →

Dynamic Programming in NLP - Skip Grams

In this series of posts, I will be exploring and showing how dynamic programming technique is used in machine learning and natural language processing. Dynamic programming is very popular in programming interviews. DP technique is used mainly in problems which has optimal substructure and can be defined recursively, which means that a problem of size N can be solved by solving smaller sub-problems of size m < N. Such problems […]

Continue Reading →

LeetCode : Cherry Pickup

Problem Statement Solution : This problem is probably one of the most difficult path traversal problem, I have seen on LeetCode and I will let you know the reason why. The most faulty assumption to begin with is that, this can be solved using a greedy approach, i.e. find the maximum possible cherries during the forward traversal (0,0) to (N-1, N-1) and then find the maximum possible cherries during the […]

Continue Reading →

LeetCode : Reaching Points

Problem Statement Solution : The obvious way is to go with a DFS or BFS like approach. Starting from the point (sx, sy), we can go in two possible directions (sx + sy, sy) and (sx, sx + sy) and then each of these points can go in two possible directions and so on. Note that the paths will form a tree like structure as we are going in either […]

Continue Reading →

LeetCode : Swim in Rising Water

Problem Statement Solution : One possible solution is to see whether for each water level, he can swim from (0, 0) to (N-1, N-1) without waiting anywhere in between. To check whether he can swim from (0, 0) to (N-1, N-1) i.e. there exists a path, we can use DFS or BFS to traverse the matrix. He can swim from point A to B if the height of B is less […]

Continue Reading →

Neural Networks as a Function Approximator

For the past few days, I have been reading quite a lot of research papers, articles and blogs related to artificial neural networks and its transition towards deep learning. With so many different methods of selecting the best neural network architecture for a problem, the optimal hyper-parameters, the best optimization algorithm and so on, it becomes a little overwhelming to connect all the dots together when we ourselves start to […]

Continue Reading →

Building a Neural Network from scratch in Python

In this post I am going to build an artificial neural network from scratch. Although there exists a lot of advanced neural network libraries written using a variety of programming languages, the idea is not to re-invent the wheel but to understand what are the components required to make a workable neural network. A full-fledged industrial scale neural network might require a lot of research and experimentation with the dataset. Building a simple […]

Continue Reading →