S.Abakumoff
BAN USER 0of 0 votes
AnswersDiscuss the design of the following game:
 S.Abakumoff in United States
The board consists of the cells of 3 kinds:
ant,
water,
food
if the ant moves to the cell that has ant then both ants are destroyed
if the ant moves to the cell that has water, ant disappears
if the ant moves to the cell that has food, food cell become ant cell.
there are two players, game server. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Object Oriented Design  2of 2 votes
AnswersWrite a method that multiplies two integers without using multiply operator
 S.Abakumoff in United States Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm  0of 0 votes
AnswersWhat are the common problems in multithreading programming? Lock, Dead Lock
 S.Abakumoff in United States Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Knowledge Based  0of 0 votes
AnswerDiscuss IEnumarable/IEnumerator pattern. WAP that implements the pattern for the collection with elements that are collections as well, i.e.:
 S.Abakumoff in United States
((1,3,4), (4,5,6), (7,8,9)) Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Knowledge Based  2of 2 votes
Answersinput:
 S.Abakumoff in United States
sum  the integer amount
n  the number of coins
d  the array contains the coins denominations
WAP that prints all the possible nonrepeated combinations of n coins of denominations from d that sum up to n.
Sample of input:
d={1,5,10,15}
sum = 30
n = 6
The expected output:
1,1,1,1,1,25
5,5,5,5,5,5 Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm  1of 1 vote
Answersdiscuss restaurant reservation system design
 S.Abakumoff in United States Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Object Oriented Design  1of 1 vote
AnswersSerialize in a file and deserialize a binary tree.
 S.Abakumoff in United States Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm
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 )
 S.Abakumoff February 27, 2013The question does not say that you can't use divide. So I guess 1/a/b solution might be OK.
 S.Abakumoff February 27, 2013this 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.
 S.Abakumoff February 26, 2013cool way to find the sign !
 S.Abakumoff February 25, 2013I am not sure whether it works for negative numbers..I.e. try Mul(11, 11), expected result is 121...
 S.Abakumoff February 25, 2013don't forget about handling negative numbers..
 S.Abakumoff February 25, 2013yeah, that's right
 S.Abakumoff February 22, 2013i would ask  what specific type of DFS you are looking for  inorder, preorder, postorder?
 S.Abakumoff February 22, 2013Find 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;
}

S.Abakumoff
February 22, 2013 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;
}
}

S.Abakumoff
February 21, 2013 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/designastacksuchthatgetminimumshouldbeo1
 S.Abakumoff February 21, 2013The job has the following attributes:
 start time(ddmmyyyy 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...
 S.Abakumoff February 21, 2013linked 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
 S.Abakumoff February 20, 2013I am using this comment to post the quickunionbased 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, ci1);
}
if (ri > 0)
{
TryUnion(nextIndex, ri1, 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);
}
}

S.Abakumoff
February 19, 2013 what is the initial min value of the min heap?
 S.Abakumoff February 19, 2013since 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,j1);
}
}
}
}

S.Abakumoff
February 19, 2013 agree, the question is not very clear..
 S.Abakumoff February 19, 2013for 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.
 S.Abakumoff February 19, 2013seems to be right solution!
 S.Abakumoff February 19, 2013@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();
}

S.Abakumoff
February 19, 2013 it's all very, very unclear without the code, can you provide it?
 S.Abakumoff February 18, 2013I have the same question, will watch the thread..so far the reply of Asaf Nachmany seems to be more accurate
 S.Abakumoff February 17, 2013so, 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())} );
?
 S.Abakumoff February 17, 2013agree, that would sole the general problem..
 S.Abakumoff February 16, 2013basically 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 topdown and downpaths...
 S.Abakumoff February 16, 2013I 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.
 S.Abakumoff February 16, 2013It's not my problem, this just the example of the input that the algo we have been discussing should solve :)
 S.Abakumoff February 16, 2013Does 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 updown and downup paths are the subject to search? For example can the path start in the left subtree of the root node and end in the right subtree of the root node? Or we consider updown 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:)
 S.Abakumoff February 15, 2013ok.
 S.Abakumoff February 15, 2013the 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 topN algorithm to build the the minheap 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
 S.Abakumoff February 14, 2013this 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..
 S.Abakumoff February 14, 2013class 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);
}
}
}
}

S.Abakumoff
February 13, 2013 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);
 S.Abakumoff February 12, 2013why 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...
 S.Abakumoff February 12, 2013here 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);
}
}
}

S.Abakumoff
February 12, 2013 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.
 S.Abakumoff February 12, 2013found a mistake in the algo
 S.Abakumoff February 11, 2013store 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.
yep, this code is very similar to the one I produced in the interview:
 S.Abakumoff March 01, 2013