CareerCup

yep, this code is very similar to the one I produced in the interview:

static void ChangeCoinsModified(int sum, int n, int[] d, int start, List<int> combination)
{
	if(n==0 && sum == 0)
	{
		PrintArray(combination);
	}
	if(n==0)
	{
		return;
	}
	for(var i=start;i<d.Length;i++)
	{
		if (d[i] > sum) continue;
		var newCombination = new List<int>(combination) {d[i]};
		ChangeCoinsModified(sum-d[i], n-1,d, i, newCombination);
	}
}

Hi,
I probably didn't make it clear..but the input has the number of coins that should sum up to n. i.e. in your sample:
coins = 1,5,10,25, amount=27
There should be one more input parameter - number of coins. I.e. if number of coins = 3 then the output should be:
1,1,25
and no other combinations.
but if number of coins = 5 then the output would be
1, 1, 5, 10, 10 and no others
Another example:
coins = [1,5,10,25] sum = 30 n = 6
Output:
1,1,1,1,1,25
5,5,5,5,5,5

btw - the interviewer said "binary tree contains integers", so this solution is perfectly fine. It also the same as interviewer suggested in the end )

The question does not say that you can't use divide. So I guess 1/a/b solution might be OK.

this problem turned out to be much easier to solve than using dp. There is the polynomial solution with the recursive calls + some logic to cut off the calls that lead to the already inspected combinations.

cool way to find the sign !

I am not sure whether it works for negative numbers..I.e. try Mul(-11, -11), expected result is 121...

don't forget about handling negative numbers..

yeah, that's right

i would ask - what specific type of DFS you are looking for - in-order, pre-order, post-order?

Find the rotation point first, then choose the binary search bounds based on a value to be found and then just do a binary search.

static int? FindElemInRotatedSorted(int[] input, int subject)
{
	var rotationStart = 0;
	int? nullableInt = null;
	while (input[rotationStart] <= input[rotationStart + 1])
		rotationStart++;
	rotationStart++;
	var left = 0;
	var right = rotationStart - 1;
	if(subject < input[input.Length - 1])
	{
		left = rotationStart;
		right = input.Length - 1;
	}
	while(left<=right)
	{
		if(left == right)
		{
			return input[left] == subject ? input[left] : nullableInt;
		}
		var mid = left + (right - left)/2;
		if (input[mid] == subject)
			return input[mid];
		if(input[mid]<subject)
		{
			left = mid + 1;
		}
		else if(input[mid]>subject)
		{
			right = mid - 1;
		}
	}
	return null;
}

does this code handle the arrays of different length? like:
{1, 3, 5, 6, 7, 8, 9}
{ 1, 4, 5, 5, 17, 81, 88, 99 }

I am wondering - which output is expected for the following 2 arrays:
1,1,1
1,1,1,1,1,1,1,1,1

I imagine that the interviewer asks:
Yes, hash map solution works for more general problem : finding the common element in N unsorted arrays, but here we have 2 Sorted arrays. Is there a solution that does not requires the additional space?

sample of c# code:

class Node<T> where T : IComparable<T>
	{
		public T Value { get; set; }
		public Node<T> Next { get; set; }
		public Node<T> Prev { get; set; }
	}
	class O1DataStructure<T> where T:IComparable<T>
	{
		private readonly Stack<Node<T>> _mins = new Stack<Node<T>>();
 		private readonly  Stack<Node<T>> _maxes = new Stack<Node<T>>();
		private Node<T> _head;
		private Node<T> _tail;
		public void Delete(Node<T> node)
		{
			
			var prev = node.Prev;
			var next = node.Next;

			if (prev != null)
			{
				prev.Next = next;
				if (next != null)
				{
					next.Prev = prev;
				}

			}
			else
			{
				_head = node.Next;
			}
			if (_maxes.Peek() == node)
				_maxes.Pop();
			if (_mins.Peek() == node)
				_mins.Pop();
		} 
		
		public T Max
		{
			get
			{
				if (_maxes.Count == 0)
 					throw new InvalidOperationException("no values exist");
				return _maxes.Peek().Value; }
		}
		public T Min
		{
			get
			{
				if(_mins.Count == 0)
					throw new InvalidOperationException("no values exist");
				return _mins.Peek().Value;
			}
		}
		
		public void RemoveMax()
		{
			if(_maxes.Count == 0)
				throw new InvalidOperationException("unable to delete the max");
			Delete(_maxes.Peek());
		}
		
		public void RemoveMin()
		{
			if (_mins.Count == 0)
				throw new InvalidOperationException("unable to delete the min");
			Delete(_mins.Peek());
		}

		public Node<T> Insert(T value)
		{
			var node = new Node<T> {Value = value, Prev=_tail, Next = null};
			if (_head == null)
			{
				_head = _tail = node;
			}
			else
			{
				_tail.Next = node;
				_tail = node;
			}
			if (_maxes.Count == 0 || _maxes.Peek().Value.CompareTo(value) < 0)
			{
				_maxes.Push(node);
			}
			if (_mins.Count == 0 || _mins.Peek().Value.CompareTo(value) > 0)
			{
				_mins.Push(node);
			}
			return node;
		} 
	}

the min and max are preserved in aux stacks..the logic is the same as for pop operation of the stack that has min/max functions..the example of implementation can be found at stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1

The job has the following attributes:
- start time(dd-mm-yyyy hh:mm:ss)
- occurrence rule: once, daily, monthly, weekly, etc.
- the pointer to the job working process. For example it’s command string consists of the program name and arguments.
The jobs list has 10M entities..seems to be too large to keep in the memory all the time, so save it in DB or in distributed DB.

Once per day the agent performs the following:
going through all the jobs in DB
select the jobs which should start before the next day. The next job’s start time can be calculated by using the current time, job’s start and time and occurrence rule.
for each found job:
start the new thread that sleeps until the next job start time and then run the job and terminates the thread.

The agent should intercept the new jobs insertion and if it should be started before the next day then start the thread for it.

The agent should intercept the jobs deleting and cancel the thread for the corresponding job it it was started..

There is system limit for the threads that an app may run. if there are too many jobs to start today the agent may partition then in the X hrs long intervals and start the new threads several times per day..

sort array by using merge sort which is stable. the next steps are obvious..insert the 1st item in the resulting array, for each next item insert it in the resulting array if the key is not equal to the key of the previous value in the sorted array...

linked list where the nodes have the previous and next link to guarantee O(1) delete and insert if delete(Node) is meant by delete operation
combined with
stack of references to the nodes with min values and stack of references to the nodes with max values(the same algorithm as for stack with min function) to guarantee O(1) find/delete max/min

mea culpa, nevermind

I am using this comment to post the quick-union-based solution that requires O(M) space and has O(M log M) complexity where M = rows * cols.. hope it will be useful..

class Shapes
{
	private readonly int[] _aux;
	private readonly int[] _sizes;
	private readonly int _rows;
	private readonly int[,] _input;
	private readonly int _cols;
	private readonly Dictionary<int, bool> _components = new Dictionary<int, bool>();  
		
	private int GetAuxIndex(int ri, int ci)
	{
		return ri*_cols + ci;
	}
		
	private int Find(int index)
	{
		while (_aux[index] != index)
			index = _aux[index];
		return index;
	}
		
	private void Union(int s1, int s2)
	{
		var c1 = Find(s1);
		var c2 = Find(s2);
		if (c1 == c2)
			return;
		if (_sizes[c1] < _sizes[c2])
		{
			_aux[c1] = _aux[c2];
			_sizes[c2] += _sizes[c1];
			_components[c2] = true;
		}
		else
		{
			_aux[c2] = _aux[c1];
			_sizes[c1] += _sizes[c2];
			_components[c1] = true;
		}
			
	}
		
	private void TryUnion(int index, int ri, int ci)
	{
		if (_input[ri, ci] == 0)
			return;
		var index2 = GetAuxIndex(ri, ci);
		Union(index, index2);
	}
		
	public Shapes(int[,] input)
	{
		_rows = input.GetLength(0);
		_cols = input.GetLength(1);
		var n = _rows*_cols;
		_input = input;
		_aux = new int[n];
		_sizes = new int[n];
		for (int i = 0; i < _aux.Length; i++)
		{
			_aux[i] = i;
			_sizes[i] = 1;
		}
		for (var ri = 0; ri < _rows; ri++)
		{
			for (var ci = 0; ci < _cols; ci++)
			{
				var next = input[ri, ci];
				var nextIndex = GetAuxIndex(ri, ci);
				if (next == 0)
					continue;					
				if (ci > 0)
				{
					TryUnion(nextIndex, ri, ci-1);
				}
				if (ri > 0)
				{
					TryUnion(nextIndex, ri-1, ci);
				}
			}
		}
		var shapes = 0;
		for (var i = 0; i < _aux.Length; i++)
		{
			var ind = Find(i);
			var size = _sizes[ind];
			if (size==1 && _input[i/_cols, i%_cols] == 1)
				shapes++;
		}
		shapes += _components.Count;
		Console.WriteLine(shapes);
	}
}

what is the initial min value of the min heap?

since the problem is limited to the sum of the substrings we can do O(n^2) in any case, i.e.:

static void SubStringSum(int sum, int[] input)
{
	var suffixes = new int[input.Length];
	var curSum = 0;
	for(var i=input.Length - 1; i>=0;i--)
	{
		curSum += input[i];
		suffixes[i] = curSum;
	}
	for(var i=0;i<suffixes.Length;i++)
	{
		for(var j=i;j<suffixes.Length;j++)
		{
			if(suffixes[i] - suffixes[j] == sum)
			{
				Console.WriteLine("{0}-{1}",i,j-1);
			}
		}
	}
}

agree, the question is not very clear..

for the matrix that has all 1's your algo will return value = number of rows * number of columns, however, it should return 1 as the entire matrix is the single shape.

seems to be right solution!

@Srikanth
what result will be returned for the matrix?
1,1,1,1,1
1,1,1,1,1
1,1,1,1,1
1,1,1,1,1

expected: 1 because the entire matrix is the single shape

can we do without recursion?

static string Compress(string s)
{
	var ch = s[0];
	var count = 1;
	var output = new StringBuilder();
	for(var i=1;i<s.Length;i++)
	{
		if(s[i] == ch)
		{
			count++;
		}
		else
		{
			output.Append(count == 1 ? ch.ToString() : ch + count.ToString());
			count = 1;
			ch = s[i];
		}
	}
	output.Append(count == 1 ? ch.ToString() : ch + count.ToString());
	return output.ToString();
}

it's all very, very unclear without the code, can you provide it?

I have the same question, will watch the thread..so far the reply of Asaf Nachmany seems to be more accurate

so, instead of comparing the actual numbers in a sorting routine the code should compare the numbers converted to strings, like

Array.Sort(input, (n1, n2) =>{return string.Compare(n1.ToString(), n2.ToString())} );

?

agree, that would sole the general problem..

basically I agree, the general problem seems to be too tough for the phone interview, however the topic author claimed that the paths include both of the top-down and down-paths...

I though that we can turn the tree to the directed weight graph so that if NL is the left node of the node N then there are two edges N->NL and NL->L of weight = value of NL + value of N exist(the same for the right node). Then find the weights of the paths for each two pair of nodes and select the ones with value = K.

It's not my problem, this just the example of the input that the algo we have been discussing should solve :)

Does this solution work for the following case:
Tree:

5
 /   \
2   7
    /   \
   11 -4
           \
            3
              \
               1

K = 14
the answer should be the paths:
2,5,7
11,7,-4
2,5,7,-4,3,1

Hello Ashok,
Does the problem definition specify whether the both of up-down and down-up paths are the subject to search? For example can the path start in the left sub-tree of the root node and end in the right sub-tree of the root node? Or we consider up-down paths only - the ones that start in some node(maybe not root) and end in the left or right subtree of this node?

_source.Value.CompareTo(n)!=0 it's not about Bst.
Read the code first, comment second.

ok, man, let's play this game:)

ok.

the naive way to sort the array in descending order, the best complexity would be O(n*log(n)), quick sort would be fine for that and then just return Kth element.
The second thought is using the standard top-N algorithm to build the the min-heap of size K+1 from the input array, the heap will contain K+1 largest elements from the input. Then return the heap top which is Kth largest.
The complexity is O(n*log(K) ), the space is O(K+1)

No O(1) solution exists

this solution assumes that we are looking for the exact match of the fraud pattern and the cheque number, however, it seems that we are looking for a partial match - whether the cheque number contains one of the fraud patterns..

class Permutation
{
	private bool[] _used;
	private int[] _input;
	private List<int> _temp;
	public void Permute(int input)
	{
		if(input<=0)
			throw new ArgumentException("input must be greater than 0");
		_input = new int[input];
		for (var i = 1; i <= input;i++ )
		{
			_input[i - 1] = i;
		}
		_temp = new List<int>();
		_used = new bool[_input.Length];
		Permute();
	}
	private void Permute()
	{
		if(_temp.Count == _input.Length)
		{
			foreach (var t in _temp)
			{
				Console.Write(t);
				Console.Write(" ");
			}
			Console.WriteLine();
		}
		else
		{
			for(var i=0;i<_input.Length;i++)
			{
				if(_used[i])
					continue;
				if (_temp.Count > 0 && _temp[_temp.Count - 1] + 1 == _input[i])
					continue;
				_temp.Add(_input[i]);
				_used[i] = true;
				Permute();
				_used[i] = false;
				_temp.RemoveAt(_temp.Count - 1);
			}
		}
	}
}

okay, got it. I checked the web and found O(log(n!)) solution that involves binary search, but it's not a way better than O(n);

why is it better than the regular search through all the elements? The complexity seems to be the same..Since the 2d array has all the rows and columns sorted, there should be algorithm that is using the binary search to solve the problem more efficiently...

here is the C# code:

class Dfs<T> where T : IComparable<T>
{
	private readonly Node<T> _source;
	private readonly Dictionary<T, T> _paths = new Dictionary<T, T>();
	private T _max = default(T);
	public Dfs(Tree<T> tree)
	{
		_source = tree.Root;
	}
	public void Solve()
	{
		Search(_source);
		var stack = new Stack<T>();
		stack.Push(_max);
		for(var n = _paths[_max]; _source.Value.CompareTo(n)!=0;n=_paths[n])
		{
			stack.Push(n);
		}
		stack.Push(_source.Value);
		while(stack.Count>0)
		{
			Console.WriteLine(stack.Pop());
		}
	}
	private void Search(Node<T> node)
	{
		if(node.Value.CompareTo(_max) > 0)
		{
			_max = node.Value;
		}
		if(node.Left!=null)
		{
			_paths.Add(node.Left.Value, node.Value);
			Search(node.Left);
		}
		if(node.Right!=null)
		{
			Search(node.Right);
			_paths.Add(node.Right.Value, node.Value);
		}
	}
}

consider the tree to be the directed graph, perform the regular DFS to find the paths between root and all the nodes and find the max value at the same time. Print the path to the max node in the end.

found a mistake in the algo

store in two tables like:

| Query Id | Query Body |
and
| Query Id | Query Date | Occurrence

initialize min heap of size 10;
for each query:
select sum(Occurrence) as qo where query date is in the given interval and query id = current query id
remove the heap min
place (qo, query id) node in the min heap

in the end the heap will contain top 10 queries made during the given dates interval.