Data Structures and Algorithm

Jumping frog problem

Jumping frog problemProblemThere were n stones across a river. Each stone was places 1 meter apart. A frog can jump in steps of 1 meter, 2 meters, 3 meters and so on. The first jump is always 1 meter. The typical behavior of the frog is such that if it goes k meters in one…

Read More

Draw a binary tree with ASCII

Draw a binary tree with ASCIIProblemWrite a program to draw a binary tree with fixed width fonts. Represent left links with a ‘/‘ and right link with ‘’. For example like this.

SolutionUse the post order traversal of the binary tree to know the width required to represent the subtree rooted at a particular node. The…

Read More

Remove duplicate subtree

Remove duplicate subtreeProblemCompact a binary tree by removing the duplicate subtrees. For example the binary tree given in figure 1 has two duplicate subtrees. The duplicate parts are circled in figure 2. Wherever such duplication occurs, we should remove that duplicate subtree and point the link to the existing subtree as described in figure 3…

Read More

Algorithms Design – Chapter 2, Exercise 8

I’m having a hard time trying to find the solutions for this book on the web, so, to help others interested, i’m sharing what i’ve managed to solve at the moment =). This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this…

Read More

Algorithms Design – Chapter 2, Exercise 7

I’m having a hard time trying to find the solutions for this book on the web, so, to help others interested, i’m sharing what i’ve managed to solve at the moment =). This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this…

Read More

Algorithms Design – Chapter 2, Exercise 6

I’m having a hard time trying to find the solutions for this book on the web, so, to help ohers interested, i’m sharing what i’ve managed to solve at the moment =). This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this…

Read More

Algorithms Design – Chapter 2, Exercise 5

I’m having a hard time trying to find the solutions for this book on the web, so, to help others interested, i’m sharing what i’ve managed to solve at the moment =). This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this…

Read More

Algorithms Design – Chapter 2, Exercise 4

I’m having a hard time trying to find the solutions for this book on the web, so, to help ohers interested, i’m sharing what i’ve managed to solve at the moment =). This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this…

Read More

Algorithms Design – Chapter 2, Exercise 3

I’m having a hard time trying to find the solutions for this book on the web, so, to help ohers interested, i’m sharing what i’ve managed to solve at the moment =). This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this…

Read More

Algorithms Design – Chapter 2, Exercise 2

I’m having a hard time trying to find the solutions for this book on the web, so, to help ohers interested, i’m sharing what i’ve managed to solve at the moment =). This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this…

Read More

Algorithms Design – Chapter 2, Exercise 1

I’m having a hard time trying to find the solutions for this book on the web, so, to help ohers interested, i’m sharing what i’ve managed to solve at the moment =). This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this blog…

Read More

Find loop in linked list

Find loop in linked list Problem Given a linked list find whether the list is looped or not. A linked list is looped when one of the nodes point to any one of its previous nodes or itself. Also find the length of the loop and the starting point of the loop. Solution We take…

Read More

Linked list Y shape

Linked list Y shape Problem Given two linked lists find out whether they are converged to a single linked list or not, if yes, find there point of convergence. Solution If the linked lists are convergent, then their last node will be same. So we traverse along both the nodes and find the last node…

Read More

Find shortest path in a maze

Find shortest path in a maze Problem Given a maze some of whose the cells are blocked. The left top cell is the entry point and right bottom cell is the exit point. Find the shortest path, if possible, from entry to exit through non blocked cells. For example Given maze _|_|_|_|_|#|_|_|_|_| _|_|#|_|#|_|_|_|#|#| _|#|_|_|_|#|#|#|_|#| _|#|_|_|_|#|_|_|#|_|…

Read More

Find all possible paths in a maze

Find all possible paths in a maze Problem Given a maze where some of the cells are blocked, where left top cell is the entry point and right bottom cell is the exit point, find all possible paths from entry to exit which goes through the non blocked cells. Solution For finding all possible paths…

Read More