Hello people! In this post we will talk about Bidirectional Search, a powerful search strategy which can be used if you have a goal directed agent in a (possibly infinite) search space. The idea behind Bidirectional search is to run two simultaneous searches, one forward from the source state and the other backward from the […]
Hello people! In this post we will talk about another search algorithm Iterative deepening depth first search (IDDFS) or Iterative deepening search (IDS). This algorithm is used when you have a goal directed agent in an infinite search space (or search tree). Why do Breadth First Search (BFS) and Depth First Search (DFS) fail in […]
N-ary tree is defined as a rooted tree which has at most N children for any node. So, a binary tree is a special case of the N-ary tree, where N = 2. We ca implement an N-ary tree using structures or using arrays.
Problem statement – Given an array of N rows and N columns (square matrix), rotate the matrix by 90° in clockwise direction. Solution – This is an implementation based problem, which means that when asked in an interview, the interviewer is mainly testing your skill to write a program which follows some set of rules. […]
Problem statement – Given a 2D array (or matrix) of N rows and M columns, print it in a spiral order. Example, for the below matrix – The output is – Solution – When an interviewer asks you this question, he/she is just testing your implementation skills. This question isn’t tough because it doesn’t have […]
Problem statement – Given a non-negative integer in the form of an array of digits, add one to digit array. The digits are stored such that the most significant digit is at the head of the list. Eg. – A = {1, 3, 5}, answer = {1, 3, 6} Solution – When an interviewer asks […]
Hello people..! This is a special extension for my discussion on Graph Theory Basics. Here, I give you the code for implementing the Adjacency List using C++ STL where each vertex is a string instead of and integer. This code has been requested many times, so I decided to create a separate page for it. […]
Improve the performance of Minimax algorithm by applying Alpha-Beta Pruning. Alpha-beta pruning is based on the Branch and bound algorithm design paradigm where we discard any decision which cannot possibly yield a better solution than the one we have so far.
Problem statement – Given an unsorted integer array, find the first missing positive integer. Example, If A = [-1, 4, 2, 3, 5], missing integer = 1. If A = [1, 5, 2, 3, 4, 7], missing integer = 6. If A = [-1, -2, -3, -4], missing integer = 1. Clues – Your solution […]
Find a contiguous sub-array whose sum is maximum. Using the dynamic programming based Kadane’s Algorithm, we can solve this in O(N) time.