Find if there is a path between two vertices in a directed graph
Posted on February 9, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Why do you need to have 3 states (“Visited, &… Anonymous - Aug 4, 2016Why do you need to have 3 states (“Visited, “Unvisited”, and “Visiting”)? It seems like we do the same thing - adding the node to the queue - if it’s unvisited, but there is no functional distinction between visited and visiting (in either state we skip it - we won’t enqueue it and we won’t check against it).
[Read More]Find if there is a path between two vertices in a directed graph
Posted on February 9, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second.
Solution We have already seen solution to connectivity in undirected graph via bfs. Now lets see it on directed graph.
BFS to check the connectivity
public enum State { Unvisited, Visited, Visiting; } public static boolean search(Graph g, Node start, Node end) { LinkedList<Node> q = new LinkedList<Node>(); // operates as Stack for (Node u : g.
[Read More]How to check whether a given number n belongs to fibanocii series?
Posted on February 9, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The standard way (other than generating up to N) is to check if (5N2+4) or (5N2−4) is a perfect square.
Had discussion with my friend, on this and hence I thought its a good information to share via blog.
More -
http://math.stackexchange.com/questions/9999/checking-if-a-number-is-a-fibonacci-or-not
Find next higher number using exact same digits
Posted on February 9, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem Given a number X find the number Y which is next higher number than X using the exact same digits as in X.
Example
For example: given 38276 return 38627
Solution
Method 1 - Brute force
The brute-force method is to generate the numbers with all digit permutations and consider all the higher numbers than the given number and return the minimum number from those higher numbers.
[Read More]Stack of plates
Posted on February 8, 2014
(Last modified on August 11, 2020)
| 3 minutes
| Kinshuk Chandra
**Question **
Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
[Read More]Implementing 2 stacks in an array
Posted on February 7, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem: How can you implement two stacks in a single array, where no stack overflows until no space left in the entire array space?
Lets denote the stacks by suffix 1 and 2. Now we have to implement the following methods :
push1(int x) –> pushes x to first stack
push2(int x) –> pushes x to second stack
pop1() –> pops an element from first stack and return the popped element
[Read More]Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0
Posted on February 6, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0
Example **Input : **
1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Output :
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Solution Method 1 - Using the extra space and O(n^2) solution
[Read More]Rotate n * n matrix by 90 degrees
Posted on February 5, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
#include void main() { int mat1[3][3],ma… Anonymous - Jan 2, 2015#include
void main()
{
int mat1[3][3],mat2[3][3],i ,j;
static int k=0;
printf(“Enter the values for the matrix \n”);
for(i=0;i<3;i++)
{
printf("\n”);
for(j=0;j<3;j++)
{
scanf("%d”,&mat1[i][j]);
}
}
printf(“Printing the given matrix”);
for(i=0;i<3;i++)
{
printf("\n”);
for(j=0;j<3;j++)
{
printf("%d “,mat1[i][j]);
}
}
printf(“Rotating the given matrix by 90 degrees”);
for(i=2;i>=0;–i)
{
// printf("\n”);
for(j=0;j<3;j++)
{
mat2[j][k]=mat1[i][j];
}
k=k+1;
}
printf(“Printing the rotated matrix “);
[Read More]Rotate n * n matrix by 90 degrees
Posted on February 5, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem Rotate the n*n matrix by 90 degrees.
**Another way to ask the same problem **
Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
Example
Example 1 Example 2 INPUT >> OUTPUT | INPUT >> OUTPUT | 4 | 4 | 1 2 3 4 1 1 1 1 | 11 12 13 14 41 31 21 11 | 1 2 3 4 2 2 2 2 | 21 22 23 24 42 32 22 12 | 1 2 3 4 3 3 3 3 | 31 32 33 34 43 33 23 13 | 1 2 3 4 4 4 4 4 | 41 42 43 44 44 34 24 14 Solution Consider the array
[Read More]Determine if a string has all unique characters
Posted on February 4, 2014
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem:
Implement an algorithm to determine if a string has all unique characters.
Solution
Solution1 - My first algorithm is a straightforward, brute force approach. Basically, we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2) because of the nested loop.
bool uniqueChars(string myString) { for (int x = 0; x < myString.
[Read More]