berkaypamir
BAN USERThis is working.
public static int FindDuplicate(int[] arr)
{
int val = 0;
for (int i = 0; i < arr.Length; i++)
{
val = Math.Abs(arr[i]);
if (arr[val] < 0)
return val;
else arr[val] = (-1) * arr[val];
}
return -1;
}
I think this is the most elegant solution presented here.
- berkaypamir November 04, 2012Here is an implementation in C#. Note that since it is not a BST, worst case running time is O(n).
public static TNode LeastCommonAncestor(TNode root, TNode first, TNode second)
{
if (root == null)
return null;
if (root == first || root == second)
return root;
TNode left = LeastCommonAncestor(root.left, first, second);
TNode right = LeastCommonAncestor(root.right, first, second);
if (left != null && right != null)
return root;
if (left != null)
return left;
if (right != null)
return right;
return null;
}
Here is an implementation in C#. head of linked list is passed by ref because head may be deleted and so it may change.
public static void Delete(ref Node head, int data)
{
if (head != null)
{
Node curr = head;
if (curr.data == data)
head = head.next;
else
{
while (curr.next != null)
{
if (curr.next.data == data)
{
curr.next = curr.next.next;
return;
}
curr = curr.next;
}
}
}
}
If you sort the array you lost the initial index information. So you cannot sort the array.
- berkaypamir November 03, 2012Here is my solution in C# using two lists, one is for the current level being examined and the other one is for the next level. Length of the lists are not dependent on the depth of the tree. Actually it traverses the tree level by level like BFS.
public static int GetDifference(TNode node)
{
int minHeight = Int32.MaxValue;
int level = 0;
List<TNode> list = new List<TNode>();
list.Add(node);
List<TNode> next = new List<TNode>();
while (list.Any())
{
level++;
next.Clear();
foreach (TNode n in list)
{
if (n.left != null)
next.Add(n.left);
if (n.right != null)
next.Add(n.right);
if (n.left == null && n.right == null)
{
if (minHeight > level)
minHeight = level;
}
}
list.Clear();
list.AddRange(next);
}
return level - minHeight;
}
Here is my solution in C#. GetHeight method is used to calculate the height of the tree and called once before PrintXY method to calculate the height input.
static int xcoord = 0;
public static int GetHeight(TNode root)
{
if (root == null)
return -1;
else return Math.Max(GetHeight(root.left), GetHeight(root.right)) + 1;
}
public static void PrintXY(TNode node, int level, int height)
{
if (node != null)
{
PrintXY(node.left, level+1, height);
Console.WriteLine(node.data + "," + xcoord++ + "," + (height - level));
PrintXY(node.right, level+1, height);
}
}
Here is my solution in C#, using two lists.
public static void PrintEvenOdd(TNode root)
{
bool isOdd = false;
List<TNode> prevNodes = new List<TNode>();
prevNodes.Add(root);
PrintNodes(prevNodes);
List<TNode> currNodes = new List<TNode>();
while (prevNodes.Count > 0)
{
isOdd = !isOdd;
currNodes.Clear();
foreach (TNode node in prevNodes)
{
if (node.left != null)
currNodes.Add(node.left);
if (node.right != null)
currNodes.Add(node.right);
}
if (isOdd)
currNodes.Reverse();
PrintNodes(currNodes);
prevNodes.Clear();
if (isOdd)
currNodes.Reverse();
prevNodes.AddRange(currNodes);
}
}
private static void PrintNodes(List<TNode> list)
{
foreach (TNode node in list)
{
Console.Write(node.data + " ");
}
Console.WriteLine();
}
My solution is in C#
public static void SwapConsecutive(ref Node head) // ref because head will change
{
if (head == null || head.next == null)
return;
Node current = head;
Node tmp = head.next;
if (tmp != null)
head = tmp;
Node next;
Node last = null; // that is from the previous swap
while (current != null && current.next != null)
{
tmp = current.next;
next = tmp.next;
tmp.next = current;
if (last != null)
last.next = tmp;
current.next = next;
last = current;
current = next;
}
}
- berkaypamir November 03, 2012