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]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]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]Remove duplicate characters in a string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Given a string, Write a program to remove duplcate characters from the string.
Input String : kodeknight
Output String : kodenight
Solution Method 1 : Brute force
void removeDuplicates(char \*str) { if (!str) return; int len = strlen(str); if (len < 2) return; int tail = 1; for (int i = 1; i < len; ++i) { int j; for (j = 0; j < tail; ++j) if (str\[i\] == str\[j\]) break; if (j == tail) { str\[tail\] = str\[i\]; ++tail; } } str\[tail\] = '\\0'; } Time Complexity : O(N^2)
[Read More]Reverse a c-style string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
For example if a user enters a string “kodeknight” then on reversing the string will be “thginkedok“.
The basic approach here is to swap the first half of the string, with the next half.
Method 1 - Iterative using string length
#include<stdio.h> int string\_length(char\*); void reverse(char\*); int main() { char string\[100\]; printf("Enter a string\\n"); gets(string); reverse(string); printf("Reverse of entered string is \\"%s\\".\\n", string); return 0; } void reverse(char \*string) { int length, i; char \*begin, \*end, temp; length = string\_length(string); begin = string; end = string; for ( i = 0 ; i < ( length - 1 ) ; i++ ) end++; // swap the chars till half of the length of the string //begin with the end char and so on for ( i = 0 ; i < length/2 ; i++ ) { temp = \*end; \*end = \*begin; \*begin = temp; begin++; end--; } } int string\_length(char \*ptr) { int len = 0; while( \*(ptr+len) !
[Read More]Replace all spaces in a string with “%20″ in c-style string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem Write a C program that will replace all spaces with ‘%20′
Example
Input: “Mr John Smith "
Output: “Mr%20John%20Smith
Solution The algorithm is as follows:
Count the number of spaces during the first scan of the string. Parse the string again from the end and for each character:
If a space is encountered, store “%20”.
Else, store the character as it is in the newly shifted location.
[Read More]