RKD
BAN USER1. The undirected graph can be represented as:
class Vertex { List<Vertex> Adjacents; }
2. Traverse the undirected graph as BFS
- Use a queue to traverse
- Use a hash to track the vertices already visited
3. if current = current vertex
- get all adjacent vertices to current
- count the number of common vertices in current.adjacents
(I remove the processed adjacent node to avoid counting the same vertex twice)
.
class Vertex { List<Vertex> Adjacents; }
public static int GetNumberOfTriangles(Vertex source)
{
int count = 0;
Queue<Vertex> queue = new Queue<Vertex>();
HashSet<Vertex> visited = new HashSet<Vertex>();
queue.Enqueue(source);
while (!queue.IsEmpty())
{
Vertex current = queue.Dequeue();
// get all non-visited adjacent vertices for current vertex
List<Vertex> adjacents = current.Adjacents
.Where(v => !visited.Contains(v))
.ToList();
while (!adjacents.IsEmpty())
{
Vertex curr = adjacents.First();
// count the number of common vertices
// adjacents.Contains(c) => common vertex
// c != curr => avoid counting itself */
// !visited.Contains(c) => we haven't counted this yet
count += curr.Adjacents
.Select(c => adjacents.Contains(c)
&& c != curr
&& !visited.Contains(c)
).Count();
// remove the vertex to avoid counting it again in next iteration
adjacents.Remove(curr);
queue.Enqueue(curr);
}
// Mark the vertex as visited
visited.Add(current);
}
return count;
}
@Anonymous - Swapping is far more costlier since it involves actual data movement compared to just integer arithmetic operations. Here for example, we considered data to be int, but in real scenarios, it could be documents, videos, anything. So, each swap matter. 4th solution has a best case of O(k), which is more efficient than reversing the elements which is O(3*n).
(k = number of elements to be shifted, n = array length)
Here are the possible solutions:
Solution #1 (brute force)
1. temp = first element of array
2. Shift all the remaining array elements left by 1
3. last element of array = temp
4. Continue for n steps
Time complexity: O(n * k)
Solution #2 (with a temp array)
1. Copy the first n bits to a temp array.
2. Move the remaining arrayLength - n bits to front
3. Copy the temp array to the end
Space complexity: O(k), Time complexity: O(n)
Solution #3 (with reverse):
FrickinHamster solution - reverse the strings. But reversing a string takes O(n) and this will need 3 reverse. Good but not the best.
Solution #4 (most efficient solution and I think the interviewer is looking for this one)
Circular left shift the entire array with each element moved to right position at first iteration itself. This will utilize mod operation to compute next position. I could explain more, but the following link does a far better job. Time Complexity: O(k) Best case, O(n) average case
stackoverflow.com/questions/11893053/circular-left-shift-of-an-array-by-n-positions-in-java
PS: k = number of elements, n = array length
1. v = Pop top one element from s
2. Push all remaining element to t
3. Push v to s
4. Push all t elements back to s
This will get first element of s in correct reverse position.
Continue for all other elements by keeping a count of how many elements are reversed.
public static Stack<int> ReverseStack(Stack<int> s)
{
int count = s.Count;
Stack<int> t = new Stack<int>();
while (count-- > 0)
{
int v = s.Pop();
int n = 0;
while(n++ < count) t.Push(s.Pop());
s.Push(v);
while (!t.IsEmpty()) s.Push(t.Pop());
}
return s;
}
Algorithm:
Find all the sub-arrays of length = input length and compute the product of each. Sub-arrays can be generated by generating all binary numbers from 0 to 2^arrays.length.
For example:
all subarrays of an array {2,5} can be generated in binary as:
00 = {}
01 = {,5}
10 = {2,}
11 = {2,5}
in below code: 1 << array.Length = 1 << 2 = 2 ^ 2 = 4 max subsets can be generated
Now, get all subsets of input length and find the max product.
public static void MaxProductOfSubArray(int[] array, int length)
{
if (array == null || array.Length == 0 || length < 0 || length > array.Length)
throw new ArgumentException();
int maxProduct = int.MinValue;
int[] output = new int[length];
int maxSubsets = 1 << array.Length;
for (int i = 0; i < maxSubsets; ++i)
{
List<int> set = new List<int>();
for (int j = 0, k = i; k > 0; j++, k >>= 1)
if ((k & 1) > 0) set.Add(array[j]);
if (set.Count() == length)
{
int product = 1;
set.ForEach(n => product *= n);
if (product > maxProduct)
{
maxProduct = product;
output = set.ToArray();
}
}
}
output.ToList().ForEach(n => Console.Write(n + " "));
Console.WriteLine(":" + maxProduct);
}
If the tree is huge - the recursive inorder traversal will put heavy load on the system stack!
I would prefer BFS traversal using an Arraylist - the size of the arraylist will be close to (2^height of the tree).
At each iteration - you save a level in arrayList and then you compare with the other tree to check if its a mirror!
1=white / 0=black
I create 5 masks of size 2x2 - 1 row, 2 cols, 2 diagonals
(I skipped one row bcz it will be considered in next iteration)
I loop through the entire matrix and at each cell visited, I check if there is a corresponding mask match.. if it is then it is a component.
Time complexity: O(nxnx2x2) = O(nxn)
public static int countComponents(int[][] matrix)
{
int count = 0;
int[][] mask1 = {{0,0},{1,1}};
int[][] mask2 = {{0,1},{0,1}};
int[][] mask3 = {{1,0},{1,0}};
int[][] mask4 = {{0,1},{1,0}};
int[][] mask5 = {{1,0},{0,1}};
for(int i=0; i<matrix.length-1; i++)
for(int j=0; j<matrix[0].length-1; j++)
{
if(isComponent(matrix, i,j,mask1)) count++;
if(isComponent(matrix, i,j,mask2)) count++;
if(isComponent(matrix, i,j,mask3)) count++;
if(isComponent(matrix, i,j,mask4)) count++;
if(isComponent(matrix, i,j,mask5)) count++;
}
return count;
}
public static boolean isComponent(int [][]matrix, int i, int j, int[][] mask)
{
for(int m=i, p=0; p<mask.length; m++, p++)
for(int n=j, q=0; q<mask[0].length; n++, q++)
if(mask[p][q]==0 && matrix[m][n]!=0) return false;
return true;
}
1. Hash all the input array values as input, List<index>
(I use list of index to consider repeated numbers in the input array)
2. Traverse the array
For each number in array
if hash has any value in the range (number + 0 to number + 2)
we have found a pair
(additional steps could be added to remove duplicate pairs if needed)
Time complexity: see below comment for time complexity (thanks to Anonymous)
- RKD April 11, 2014