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
javascript:
//var input = ['abc', 'cde', 'edf','fga'];
var input = ['abc' , 'cba', 'dfg']
var result = true;
for(var i=0;i<input.length;i++){
var prevString = input[i];
var nextString = i==input.length  1 ? input[0] : input[i+1];
var c1 = prevString[prevString.length  1];
var c2 = nextString[0];
if(c1!=c2){
result = false;
break;
}
}
console.log(result);

S.Abakumoff
January 10, 2013 As I understand the Kadane's algorithm works only when the input array containing at least one positive number. The question does not tell anything about it..So I would start with clarifying..
 S.Abakumoff January 10, 2013Cool, one minor improvement would be just decreasing the number of recursive calls and getting rid of extra memory, here is my version(not working for a corner cases like "hello","*" but the idea seems to be right:
function match_internal(s1, s2, s1Index, s2Index){
if(s1Index==s1.length && s2Index==s2.length)
return true;
while(s2[s2Index]!='*' && s2[s2Index]!='?' && s1Index < s1.length && s2Index < s2.length){
if(s1[s1Index]!=s2[s2Index])
return false;
s1Index++;
s2Index++;
}
if(s2[s2Index]=='?')
return match_internal(s1, s2, s1Index, s2Index+1)  match_internal(s1,s2,s1Index+1, s2Index+1);
if(s2[s2Index]=='*'){
var zeroMatch = match_internal(s1, s2, s1Index, s2Index+1);
if(zeroMatch)
return true;
var match = false;
for(var i=s1Index+1; i<s1.length;i++){
match = match  match_internal(s1, s2, i, s2Index+1);
}
return match;
}
}

S.Abakumoff
December 29, 2012 Yeah maybe u are right, thanks again!
 S.Abakumoff December 28, 2012Thanks for your valuable comment, Mr. Artist, I am glad that someone is tracking my messages :) So good to not feel lonely.
 S.Abakumoff December 28, 2012Strictly speaking this code is invalid as well. The output should be the array, not the array list because the input is array. At least you should call output.toArray() or something like that.
Then, this code is ignoring the fact that all the elements of the input array are 10 bit integers and is using Integer type(32 bit), so 40Mb of extra memory instead of 10Mb(or 20Mb for 16bit integers) is being used.
Finally your code is 1) invalid 2) notoptimal. I would be shocked if you were hired with this level of answer :P
Okay, the code you have posted seems to be the 1st part of the counting sort(the code below copied from wikipedia article)
# allocate an array Count[0..k] ; THEN
# initialize each array cell to zero ; THEN
for each input item x:
increment Count[key(x)]
You didn't complete the code, so strictly speaking it IS invalid
Then, the counting algorithm analysis clearly stays that because it uses arrays of length k + 1 and n, the total space usage of the algorithm is also O(n + k).
okay. counting sort is not in place algorithm, it needs O(N) extra memory. shouldn't it be considered as the stop sign?
 S.Abakumoff December 27, 2012Sorting usually implies that all the data from the input exist in the output.
The problem says that there are 10 million integers but the solution Mike provided gives 1024 integers, so it just loses the data and therefore seems to be incorrect. Am I missing something?
Also, consider the input that consists of 5 million of number 512 and 5 millions of number 3. The proposed solution does not produce the correct answer, doesn't it?
For a fixed w_set, can't we just keep all the letters contained in w_set(in form of sorted string). It's fixed so we don't need to calculate it each time. Then merge c_set input to sorted string(O(n * log n) and check if wset sting starts with cset string?
 S.Abakumoff December 27, 2012just realized that we need to output the positions of elements, not their values.
var m = [
[1,4,7],
[2,5,8],
[3,6,9]
];
var rows = m.length;
var cols = m[0].length;
var maxColumnsInRows = []; // index = row num, value: col num
var minRowsInColumns = [];
for(var i=0; i<rows;i++){
maxColumnsInRows[i] = 0;
minRowsInColumns[i] = 0;
}
for(var ri=0;ri<rows;ri++){
for(var ci=0; ci<cols;ci++){
var currentRowMaxColumn = maxColumnsInRows[ri];
var currentColumnMinRow = minRowsInColumns[ci];
var currentValue = m[ri][ci];
if(currentValue > m[ri][currentRowMaxColumn])
maxColumnsInRows[ri] = ci;
if(currentValue < m[currentColumnMinRow][ci])
minRowsInColumns[ci] = ri;
}
}
for(ri=0; ri<rows;ri++){
var maxCol = maxColumnsInRows[ri];
var minRow = minRowsInColumns[maxCol];
if(ri == minRow){
console.log('row: ' + ri +' ,col: ' + maxCol);
}
}

S.Abakumoff
December 26, 2012 Javascript DP solution
var m = [
[1,1,0],
[0,1,1],
[1,0,1]
];
var cutRows = 1, cutCols = 1;
function getNumberOfPaths(ri,ci){
var paths = 0;
if(ri<=cutRows  1 && ci>=cols  cutCols)
return 0;
if(ri1>=0) paths += m[ri1][ci];
if(ci1>=0) paths += m[ri][ci1];
return paths;
}
var rows = m.length;
var cols = m[0].length;
m[0][0]=1;
for(var ri=0;ri<rows;ri++){
for(var ci=0;ci<cols;ci++){
if(ri===0 && ci===0) continue;
m[ri][ci] = getNumberOfPaths(ri,ci);
}
}
console.log(m[rows1][cols1]);

S.Abakumoff
December 24, 2012 This answer is correct, but this algorithm works for any input array, including the maxheap(minheap). I suppose that the ideal answer should use the fact that input array is the maxheap(minheap). The primitive optimization would be selecting the largest index from the two child because we know that they are both greater than(or less than) the parent item, so the code could be simplified, like:
maxChild = arr[left] > arr[right] ? left: right;
//swap values at rootIndex, maxChild

S.Abakumoff
December 23, 2012 right..thanks for the comment
 S.Abakumoff December 21, 2012Agree, but, I think that tree of heap guarantees that the values of the next level nodes are all greater than the values on the nodes of the previous level and this is the key point; Here is the example of the code(JavaScript):
var array = [];
tree.breadthWalk(function(node){
array.push(node);
});
var size = array.length;
for(var i=size1;i>=0;i){
var left = size  2  (size  1  i ) * 2;
var right = left  1;
array[i].left = left < 0 ? null : array[left];
array[i].right = right < 0 ? null : array[right];
}
tree.root = array[size1];

S.Abakumoff
December 21, 2012 Heap is binary tree where each child of a node has a value less than or equal to the node's own value(or greater or equal for min heap), so :
1. Perform breadth  first walk adding the heap values in the array. In the end you should get the sorted array.
2. Starting from the end of the array set the nodes value so that.
rootNode.Value = array[array.length1]
rootNode.left.Value = array[array.length  2];
rootNode.right.Value = array[array.length  3];
etc..
the efficiency is O(n).
Build CiDi array and find the element from which we should start summing of all the array items so that the current sum is always greater than 0:
var stationsCapacity = [1,4,4,7];
var distances = [2,3,5,6];
var remainingGas = [];
for(var i=0; i<stationsCapacity.length;i++)
remainingGas.push(stationsCapacity[i]  distances[i]);
var startStation;
for(var i=0; i<remainingGas.length;i++){
var sum = remainingGas[i];
if(sum < 0)
continue;
var fits = true;
for(var j=i+1;j<remainingGas.length;j++){
sum+=remainingGas[j];
if(sum < 0){
fits = false;
break;
}
}
if(sum>0){
for(j=0;j<i;j++){
sum+=remainingGas[j];
if(sum < 0){
fits = false;
break;
}
}
}
if(fits){
startStation = i;
break;
}
}
console.log(startStation);

S.Abakumoff
December 20, 2012 Javascript code:
function isBalanced(str){
var stack = new Stack();
for(var c=0;c<str.length;c++){
var chr = str[c];
if(isOpenBracket(chr)){
stack.push(chr);
}
else if(isCloseBracket(chr)){
var openBracket = stack.pop();
if(!bracketsMatch(openBracket, chr))
return false;
}
}
return true;
}

S.Abakumoff
December 19, 2012
right. somehow I did not consider the order of the strings in the set.
 S.Abakumoff January 11, 2013