CareerCup

The math behind it is that the trailing zeros are produced from multiples of 5 multiplied by multiples of 2. lets say you want to count the number of trailing 0s in 12! (where it is 12*11*10*....*3*2*1).
The trailing zeros will be produced from 5*2 and 10*1 so you have 2 trailing zeros (corresponding to two multiples of 5).

Next when the number is larger than 25 the multiple of 25 produces two traling zeros instead of 1 (4*25 = 100) and accordingly 125(5*5*5) produce 1000 (three trailing zeros) if multiplied by 8.

So the final logic should count the multiples of 5 + number of multiples of 25 + number of multiples of 125 and so on till you reach 5^(n-1) where 5^(n-1) <= your number < 5^(n)

The simple answer is:
- Integer is an Object so when you use == or != it will compare reference. As they are two different instance, the first comparison is true.
- When you use >= or <= operators, the Integer is "unboxed" (meaning that it's value is compared instead of the reference) so both second and third cases would return true.

Thanks!

As far as I understand this is parenthesis matching problem:
1- If you just want to check if all parenthesis are matching, you can do that in O(n) time and O(1) space. Loop over all chars in the string, whenever you find "(" increase a counter and whenever you find ")" decrease the counter and the final result must equal to 0. Here is a sample C# code:

bool CheckMatchingParenthesis(string expression)
{
	int count = 0;
	for(int I=0; I < expression.Length; I++)
	{
		if( expression[I] == '(' )
			count++;
		else if (expression[I] == ')' )
			count--;
		if(count < 0)
			return false; //Closing ')' that is not matched
	}
	return count == 0;
}

2- If you want the index of all unmatched parenthesis, you need two stacks: one for opening '(' (say S1) and one for unmatched closing ')' (Say S2). Whenever you find an opening ( you add its index to the stack S1, whenever you find a closing ')' you remove the top element from S1, if S1 was already empty (unmatched closing tag), then add index of ')' to S2. Here is a sample code

int[] GetUnMatchedParenthesis(string expression)
{
	Stack opening = new Stack();
	Stack closing = new Stack();
	for(int I=0; I < expression.Length; I++)
	{
		if( expression == '(' )
		{
			opening.Push(I);
		}
		if( expression == ')' )
		{
			if(opening.IsEmpty())
			{
				closing.Push(I);
			}
			else
			{
				opening.Pop();
			}
		}
	}
	int[] res = new int[0];
	Array.AddRange(res, opening.ToArray());
	Array.AddRange(res, closing.ToArray());
	return res;
}

This will take O(n) time and worst case of O(n) space (if all parenthesis are opening or closing)

This algo is valid only for Binary Search Tree. You cannot assume that the tree is BST unless it is explicitly stated in the problem

There re multiple ways of doing that:
First way: Modify the Class Node and use DFS

class Node {
	Node left;
	Node right;
	object data;
	int inRoot; //represents the number of times the node is in root of a searched value
}

Node GetLCP(Node root, object val1, object val2)
{
	//Handle special case
	if(root == null)
		return null;

	//Clear inRoot value using any traversal technique
	ClearInRoot(root);	//Unimplemented here
	
	if(SearchValue(root, val1) && SearchValue(root, val2))
	{
		//Traverse from root as long as inRoot == 2 then return the point of separation
		Node current = root;
		while(current != null)
		{
			if(current.left != null && current.inRoot == current.left.inRoot)
			{
				current = current.left;
			}
			else if(current.right != null && current.inRoot == current.right.inRoot)
			{
				current = current.right;
			}
			else		//Found a separation point or reached one of the values
			{
				return current;
			}
		}
	}

	//One of the values doesn't exist in the tree, return null;
	return null;
}

bool SearchValue(Node treeNode, object val)
{
	if(treeNode == null)
		return false;
	if(treeNode.data == val)
	{
		treeNode.inRoot++;
		return true;
	}
	if(SearchValue(treeNode.left) || SearchValue(treeNode.right))
	{
		treeNode.inRoot++;
		return true;
	}
	return false;
}

A second technique, would be to get an array of all the nodes on the path to Val1 and another array of all the nodes on the path to Val2 and trace both arrays, as long as the elements are matching keep going, till either array is finished or you reach a non matching point

It's a backtracking algorithm and sure it's not the most optimal one. Starting with placing the most restricted number (n) into a place and checking if the placing will work for the rest of numbers (n-1, n-2, etc..).

At any step, if the placement of next numbers failed in all possible positions, change the placement of the current number to the next available placement

This code runs in O(n) time and O(1) space:

public int GetSequence(int[] arr, int sum)
        {
            if (arr.Length == 0)
                return -1;
            if (arr.Length == 1)
            {
                if (arr[0] < sum)
                    return -1;
                else
                {
                    return 1;
                }
            }
            int total = arr.Sum();
            if(total < sum)
            {
                return -1;
            }
            //Make a window initially with the full length of the array, then shrink it step by step
            int startIndex = 0;
            int lastIndex = arr.Length - 1;
            while (total > sum && lastIndex > startIndex)
            {
                if (arr[startIndex] > arr[lastIndex])
                {
                    if (total - arr[lastIndex] < sum)
                    {
                        return lastIndex - startIndex + 1;
                    }
                    total -= arr[lastIndex--];
                }
                else if (arr[startIndex] < arr[lastIndex])
                {
                    if (total - arr[startIndex] < sum)
                    {
                        return lastIndex - startIndex + 1;
                    }
                    total -= arr[startIndex++];
                }
                else
                {
                    if (total - arr[startIndex] < sum)
                    {
                        return lastIndex - startIndex + 1;
                    }
                    //Find the next minimum
                    if (lastIndex - startIndex > 1)
                    {
                        if (arr[lastIndex - 1] > arr[startIndex + 1])
                        {
                            total -= arr[startIndex++];
                        }
                        else
                        {
                            total -= arr[lastIndex--];
                        }
                    }
                }
            }
            return -1; //Error happened
        }

This is ambiguous:
There are two different IDs for each User record (one for Name Key and one for Age key).

Here is a basic assumption:
- Assuming we want to retrieve both keys (e.g. 1,2 in the prev example)
- Assuming each Name record is followed by Age record
- Assuming table name is Users

If the Ids are sequential with no Gaps. It is quiet easy:
SELECT t1.Id, t2.Id FROM
Users as t1 INNER JOIN Users as t2 ON t1.Id + 1=t2.Id AND t1.Key='name' AND t2.Key='age'
WHERE t1.Value LIKE 'h%' AND t2.Value >= 22 AND t2.Value <=35

If the IDs has gaps, you need to Select RowNumber two and Compare based on RowNumber instead of Id

public int[] GetNewOrder(int n)
        {
            int[] res = new int[n * 2];
            bool[] valid = new bool[n * 2];
            SetValid(valid);
            if(GetOrder(res, valid, n))
            {
                return res;
            }
            return null;
        }

        private bool GetOrder(int[] res, bool[] valid, int num)
        {
            if(num <= 0)
            {
                return true;
            }
            int start = 0;
            int[] validPositions = GetFirstValidPosition(start, num, valid);
            while(validPositions != null)
            {
                start = validPositions[0] + 1;
                valid[validPositions[0]] = false;
                valid[validPositions[1]] = false;
                if(GetOrder(res, valid, num-1))
                {
                    res[validPositions[0]] = num;
                    res[validPositions[1]] = num;
                    return true;
                }
                valid[validPositions[0]] = true;
                valid[validPositions[1]] = true;
                validPositions = GetFirstValidPosition(start, num, valid);
            }
            return false;
        }

        private void SetValid(bool[] valid)
        {
            for(int i=0; i < valid.Length; i++)
            {
                valid[i] = true;
            }
        }

        private int[] GetFirstValidPosition(int pos, int num, bool[] valid)
        {
            for(int i=pos; i < valid.Length; i++)
            {
                int shiftedPos = i + num + 1;
                if(shiftedPos >= valid.Length)
                    break;
                if(valid[i] && valid[i + num + 1])
                {
                    return new int[] { i, i + num + 1 };
                }
            }
            return null;
        }