pranaypratap
BAN USER
Comments (4)
Reputation 20
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 vote
find the median of the two sorted arrays. Divide the two arrays based on values greater and larger than the median. Merge the two distinct sets on two threads. Merge is straightforward = result(thread1).Append(result(thread2))
 pranaypratap September 24, 2017Comment hidden because of low score. Click to expand.
0
of 0 vote
public static int FindMaxSubSquareMatrix(int[,] arr)
{
if (null == arr)
{
throw new ArgumentNullException();
}
if (arr.GetLength(0) == 0  arr.GetLength(1) == 0)
{
return 1;
}
int[,] map = new int[arr.GetLength(0), arr.GetLength(1)];
for (int i =0; i<map.GetLength(0); i++)
{
for (int j =0; j<map.GetLength(1); j++)
{
map[i,j] = 1;
}
}
DoFindMaxSubSquareMatrix(arr, 0, 0, map);
int max = 0;
for (int i = 0; i < map.GetLength(0); i++)
{
for (int j = 0; j < map.GetLength(1); j++)
{
if (map[i,j] > max)
{
max = map[i,j];
}
}
}
return max;
}
private static int DoFindMaxSubSquareMatrix(int[,] arr, int i, int j, int[,] map)
{
if (i >= arr.GetLength(0)  j >= arr.GetLength(1))
{
// out of bounds
return 0;
}
if (map[i,j] != 1)
{
// already visited
return map[i,j];
}
int right = DoFindMaxSubSquareMatrix(arr, i + 1, j, map);
int down = DoFindMaxSubSquareMatrix(arr, i, j + 1, map);
int diagonalDown = DoFindMaxSubSquareMatrix(arr, i + 1, j + 1, map);
int subSquareSize = right == down && right == diagonalDown ? right : Math.Min(right, Math.Min(down, diagonalDown));
int result = arr[i, j] == 1 ? 1 + subSquareSize : subSquareSize;
map[i, j] = result;
return result;
}
static void Main(string[] args)
{
int[,] matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 0 },
{ 0, 1, 1, 0 },
{ 1, 0, 0, 0 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 0 },
{ 0, 0, 1, 0 },
{ 1, 0, 0, 0 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 1, 1 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 5]
{
{ 1, 1, 0, 0, 1 },
{ 0, 1, 1, 1, 1 },
{ 0, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
}

pranaypratap
August 31, 2017 Comment hidden because of low score. Click to expand.
0
of 0 vote
Why not try the following (nlogn):
1. sort the list
2. find the "sum so far" at each index. i.e. a[i] = Sum(a0...ai)
3. Find the item for which a[n1]  a[i] = a[i]
e.g.
1 1 1 2 2 5
Sums:
1 0 1 3 5 10
105 = 5. we have a winner
e.x2:
1 1 1 2 2 2 3 5 6 7
Sums:
1 2 1 1 3 5 13 19 26
2613 = 13, we have a winner
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
Use a Queue to do level order traversal. When putting nodes in Q, also put the levels.
 pranaypratap October 04, 2017Every time we pop from the Queue, push to the stack along with the level. Next, push the right child in the Queue (node.right, level+1) and THEN push the left child in the Queue.
In the end, stack has the data we need.