Problem: Given a string, check if any permutations of that string are a palindrome
Solution 1: Use a hashtable to count each time a character is used
public bool IsPalindrome(string str)
{
var hash = new Dictionary<char, int>();
foreach (char c in str)
{
if (hash.ContainsKey(c))
{
hash[c]++;
}
else
{
hash.Add(c, 1);
}
}
if (hash.Values.Count(v => v % 2 != 0) > 1)
{
return false;
}
return true;
}
Problem: Calculate the angle between clock hands when given the number that each cock hand is at (ie. hour hand is at the 12, minute hand is at the 3, result should be 90°).
Solution 1: Calculate Angle with inputs as clock face number
public int GetAngle(int a, int b)
{
if (a == 12) a = 0;
if (b == 12) b = 0;
if (a > b)
{
var angleTo12 = 12-a;
var totalSections = angleTo12 + b;
return totalSections * 30;
}
return (b-a)*30;
}
Solution 2: Calculate smaller angle for precise time
public int GetAngle2(int h, int m)
{
if (h == 12) h = 0;
var mAngle = m * 6;
var hAngle = (h * 30) + (m * .5);
return (int)Math.Abs(hAngle - mAngle);
}
Problem: Implement a queue using stacks.
Solution 1: Use a helper stack
public class Queue<T>
{
private readonly Stack<T> _front;
private readonly Stack<T> _helper;
public Queue()
{
_helper = new Stack<T>();
_front = new Stack<T>();
}
public void Enqueue(T data)
{
_front.Push(data);
}
public T Dequeue()
{
while (_front.Any())
{
_helper.Push(_front.Pop());
}
T data = _helper.Pop();
while (_helper.Any())
{
_front.Push(_helper.Pop());
}
return data;
}
public T Peek()
{
while (_front.Any())
{
_helper.Push(_front.Pop());
}
T data = _helper.Pop();
_front.Push(data);
while (_helper.Any())
{
_front.Push(_helper.Pop());
}
return data;
}
}
Problem: Implement a stack using queues.
Solution 1: Use a helper queue
public class Stack<T>
{
private Queue<T> _topOfStack;
private Queue<T> _helperStack;
public Stack()
{
_helperStack = new Queue<T>();
_topOfStack = new Queue<T>();
}
public void Push(T data)
{
SwitchQueues(data);
}
public T Pop()
{
return _topOfStack.Dequeue();
}
public T Peek()
{
var data = _topOfStack.Dequeue();
SwitchQueues(data);
return data;
}
private void SwitchQueues(T data)
{
while (_topOfStack.Any())
{
_helperStack.Enqueue(_topOfStack.Dequeue());
}
_topOfStack.Enqueue(data);
while (_helperStack.Any())
{
_topOfStack.Enqueue(_helperStack.Dequeue());
}
}
}
Problem: Get the height of a binary tree.
Solution 1: Iterate
public class Node<T>
{
public T Val;
public Node<T> Left;
public Node<T> Right;
}
public void GetHeight(Node n)
{
Queue q = new Queue<Node>();
q.Enqueue(n);
int height = 0;
while (q.Any())
{
var countInLevel = q.Count;
height++;
while (countInLevel > 0)
{
var current = q.Dequeue();
if (current.Left != null) q.Enqueue(current.Left);
if (current.Right != null) q.Enqueue(current.Right);
count--;
}
}
return height;
}
Solution 2: Recursive
public class Node<T>
{
public T Val;
public Node<T> Left;
public Node<T> Right;
}
public void GetHeight(Node n)
{
if (n == null) return 0;
var left = GetHeight(n.Left);
var right = GetHeight(n.Right);
if (left > right){
return left + 1;
}
else
{
return right + 1
}
}
Problem: Traverse a given binary tree, depth first.
Solution 1: Iterate via a Stack
public class Node<T>
{
public T Val;
public Node<T> Left;
public Node<T> Right;
}
public void DepthTraversal(Node n)
{
Stack s = new Stack<Node>();
s.Push(n);
while (s.Any())
{
var current = s.Pop();
if (current.Right != null) s.Push(current.Right);
if (current.Left != null) s.Push(current.Left);
Console.WriteLine(current.Val);
}
}
Problem: Traverse a given binary tree, breadth first.
Solution 1: Iterate via a Queue
public class Node<T>
{
public T Val;
public Node<T> Left;
public Node<T> Right;
}
public void BreadthTraversal(Node n)
{
Queue q = new Queue<Node>();
q.Enqueue(n);
while (q.Any())
{
var current = q.Dequeue();
if (current.Left != null) q.Enqueue(current.Left);
if (current.Right != null) q.Enqueue(current.Right);
Console.WriteLine(current.Val);
}
}
do: code; while(true)