vstudio
BAN USERMy solution uses state machine that can change direction of move based on current direction
public enum Direction
{
Right,
Down,
Up,
Left
}
public class MatrixSpiral
{
int[,] _matrix;
bool[,] _visited;
int _rowCount, _columnCount, _cellCount;
public MatrixSpiral(int[,] matrix)
{
_matrix = matrix;
_rowCount = _matrix.GetUpperBound(0) + 1;
_columnCount = _matrix.GetUpperBound(1) + 1;
_cellCount = _rowCount * _columnCount;
}
Direction _currentDirection;
public void PrintSpiral()
{
_currentDirection = Direction.Right;
_visited = new bool[_rowCount, _columnCount];
int row = 0;
int col = 0;
Console.WriteLine(_matrix[0, 0]);
_visited[0, 0] = true;
for (int i = 1; i < _cellCount; i++)
{
MoveNext(ref row, ref col);
Console.WriteLine(_matrix[row, col]);
_visited[row, col] = true;
}
}
public void MoveNext(ref int row, ref int column)
{
int newRow, newCol;
switch (_currentDirection)
{
case Direction.Right: newRow = row; newCol = column + 1;
if (!IsValidPosition(newRow, newCol))
{
_currentDirection = Direction.Down;
MoveNext(ref row, ref column);
}
else
{
row = newRow;
column = newCol;
}
break;
case Direction.Down: newRow = row + 1; newCol = column;
if (!IsValidPosition(newRow, newCol))
{
_currentDirection = Direction.Left;
MoveNext(ref row, ref column);
}
else
{
row = newRow;
column = newCol;
}
break;
case Direction.Left: newRow = row; newCol = column - 1;
if (!IsValidPosition(newRow, newCol))
{
_currentDirection = Direction.Up;
MoveNext(ref row, ref column);
}
else
{
row = newRow;
column = newCol;
}
break;
case Direction.Up: newRow = row - 1; newCol = column;
if (!IsValidPosition(newRow, newCol))
{
_currentDirection = Direction.Right;
MoveNext(ref row, ref column);
}
else
{
row = newRow;
column = newCol;
}
break;
}
}
public bool IsValidPosition(int row, int column)
{
if (row >= _rowCount
|| row < 0
|| column >= _columnCount
|| column < 0
|| _visited[row, column])
return false;
else
return true;
}
}
int[,] matrix = new int[,]{ {1,2,3}, {10,11,4}, {9,12,5}, {8,7,6} };
MatrixSpiral spiral = new MatrixSpiral(matrix);
spiral.PrintSpiral();
As many have pointed already, we can use a solution that uses any in-place sort algorithm to individually sort the 2 arrays and then find the median using merge step (of merge sort) like comparisons without using an additional array.
However, since the objective is only to find the median element and not actually sort, we can achieve this objective using "Order Statistic" algorithm. If n and m are the array sizes, then this problem reduces to finding the (n+m)/2th order statistic.
I too thought of using the stack but realized it is not doing anything better than just keeping a count variable and without the stack it is more space efficient.
bool IsBalanced(char[] code)
{
int count = 0;
foreach(char c in code)
{
if (c == '{')
count++;
else if (c == '}')
{
if (count < 0)
return false;
}
}
return (count == 0);
}
This problem reduces to the standard BFS algorithm with the only difference being the edges are not present! Instead of going out from the source square following the adjacent edges we need to follow the knight move pattern and find the adjacent squares that are reachable from any square by the knight.
[DebuggerDisplay("{ToString()}, Visited = {Visited}")]
public class ChessSquare
{
private readonly int _row;
private readonly int _column;
public ChessSquare(int row, int column)
{
_row = row;
_column = column;
Visited = false;
Parent = null;
}
public int Row { get { return _row; } }
public int Column { get { return _column; } }
public ChessSquare Parent { get; set; }
public bool Visited { get; set; }
public static bool IsValid(int row, int column)
{
return (row >= 0 && row < 8 && column >= 0 && column < 8);
}
public override string ToString()
{
return string.Format("{0}{1}", (char)((int)'a' + _row), _column + 1);
}
}
public class Chess
{
ChessSquare[,] _board;
public Chess()
{
_board = new ChessSquare[8, 8];
InitializeSquares();
}
private void InitializeSquares()
{
for (int row = 0; row < 8; row++)
{
for (int col = 0; col < 8; col++)
{
_board[row, col] = new ChessSquare(row, col);
}
}
}
public void DiscoverKnightMoves(int row, int column)
{
var queue = new Queue<ChessSquare>();
var sourceSquare = _board[row, column];
sourceSquare.Visited = true;
queue.Enqueue(sourceSquare);
while (queue.Count > 0)
{
var current = queue.Dequeue();
var adjacentSquares = GetAdjacentSquares(current.Row, current.Column);
foreach (var square in adjacentSquares)
{
square.Visited = true;
square.Parent = current;
queue.Enqueue(square);
}
}
PrintPaths();
}
private List<ChessSquare> GetAdjacentSquares(int row, int col)
{
var adjacentSquares = new List<ChessSquare>();
//north-east quadrant
CheckAdd(row - 1, col + 2, adjacentSquares);
CheckAdd(row - 2, col + 1, adjacentSquares);
//south-east quadrant
CheckAdd(row + 1, col + 2, adjacentSquares);
CheckAdd(row + 2, col + 1, adjacentSquares);
//north-west quadrant
CheckAdd(row - 1, col - 2, adjacentSquares);
CheckAdd(row - 2, col - 1, adjacentSquares);
//south-west quadrant
CheckAdd(row + 1, col - 2, adjacentSquares);
CheckAdd(row + 2, col - 1, adjacentSquares);
return adjacentSquares;
}
private void CheckAdd(int row, int column, List<ChessSquare> adjacentSquares)
{
if (ChessSquare.IsValid(row, column) && !_board[row, column].Visited)
adjacentSquares.Add(_board[row, column]);
}
private void PrintPaths()
{
foreach (var square in _board)
{
//only if square has been visited it is reachable from the source square
if (square.Visited)
{
PrintPath(square);
Console.WriteLine();
}
}
}
private void PrintPath(ChessSquare square)
{
if (square != null)
{
Console.Write("{0}", square);
if (square.Parent != null)
Console.Write(" <- ");
PrintPath(square.Parent);
}
}
}
We can do this by using the Connected Components algorithm that uses the Union-Find data structure. To account for different shades of same color we can define a function that will return true if difference between color attributes of neighbouring pixels are within some configurable threshold.
- vstudio December 01, 2012public void FindPythagoreanTriples(int[] numbers)
{
int n = numbers.Length;
//This would take O(N log N)
Sort(numbers);
int[] squares = new int[n];
//This would take O(N)
for (int i = 0; i < n; i++)
{
squares[i] = numbers[i] * numbers[i];
}
//Outer loop
for (int i = 0; i < n - 2; i++)
{
//Inner loop
for (int j = i+1; j < n - 1; j++)
{
int sum = squares[i] + squares[j];
//If the number corresponding to the hypotenuse * hypotenuse exists
//in the remaining array we have found a pythagorean triplet
//This would take O(log N)
int k = BinarySearch(squares, j+1, n);
if (k != -1)
{
Console.Writeline("{0}^2 + {1}^2 = {2}^2", numbers[i], numbers[j], numbers[k]);
}
}
}
}
Since BinarySearch will run in O(log N) and for every iteration of Inner loop we will be calling the BinarySearch on a smaller array then previous iteration it should take total time according to the sum of the following series:
log (N-1) + log (N-2) + ... + log 1
I'm not sure what's the summation of the above series.
public void FindPythagoreanTriples(int[] numbers)
{
int n = numbers.Length;
//This would take O(N log N)
Sort(numbers);
int[] squares = new int[n];
//This would take O(N)
for (int i = 0; i < n; i++)
{
squares[i] = numbers[i] * numbers[i];
}
//Outer loop
for (int i = 0; i < n - 2; i++)
{
//Inner loop
for (int j = i+1; j < n - 1; j++)
{
int sum = squares[i] + squares[j];
//If the number corresponding to the hypotenuse * hypotenuse exists
//in the remaining array we have found a pythagorean triplet
//This would take O(log N)
int k = BinarySearch(squares, j+1, n);
if (k != -1)
{
Console.Writeline("{0}^2 + {1}^2 = {2}^2", numbers[i], numbers[j], numbers[k]);
}
}
}
}
Since BinarySearch will run in O(log N) and for every iteration of Inner loop we will be calling the BinarySearch on a smaller array then previous iteration it should take total time according to the sum of the following series:
log (N-1) + log (N-2) + ... + log 1
I'm not sure what's the outcome of the above series. But if it is less than N then combined with the Outer loop overall it should be better than O(N ^2).
What do you think?
- vstudio September 01, 2013