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 non-repeated 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
one small addition: before looking for LCA by using the standard algorithm(find a node with a value that is greater than first node value and less than 2nd node value) check if node1.left = node2 or node1.right = node2 or node2.left = node1 or node2.right = node1 and return 1 if it is true
- S.Abakumoff February 08, 2013The sample given in the problem description implies the output should list all the pairs that sum to s. The code returns only one pair, doesn't it?
- S.Abakumoff February 08, 2013Your code does spent O(n) to find the middle of the list because fast pointer goes until the end of the list:
while (fast && fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
so 1. is invalid, down voted the answer.
- S.Abakumoff February 08, 2013Graph represented by ajacency list
- S.Abakumoff February 07, 2013didn't get the question, subscribing to the thread.
- S.Abakumoff February 07, 2013I've posted the solution that is using stack, it can be found in the very last comment on this page. This solution is O(n) because insert and remove operations in linked list implementation of C# are O(1). However, the same level of complexity can be supported manually with small additions to the same algorithm.
- S.Abakumoff February 05, 2013If extra space is allowed, then :
static void ArrangeLinkedList<T>(LinkedList<T> list) where T : IComparable<T>
{
var stack = new Stack<LinkedListNode<T>>();
var current = list.First;
while (current != null)
{
stack.Push(current);
current = current.Next;
}
current = list.First;
while (current!=null && stack.Peek()!=current)
{
var node = stack.Pop();
list.Remove(node);
list.AddBefore(current, node);
current = current.Next;
}
}
can think only about n^2 logn solution, subscribing to the thread.
- S.Abakumoff February 04, 2013static int[] SortIndices(int[] input)
{
var output = new int[input.Length];
for (var i = 0; i < output.Length; i++)
{
output[i] = i;
}
Comparison<int> comp = (i, i1) => input[i].CompareTo(input[i1]);
Array.Sort(output, comp);
return output;
}
static int Dyno(int[] input)
{
var indicesSorted = SortIndices(input);
var maxLen = 0;
for (var i = 0; i < indicesSorted.Length; i++)
{
if (indicesSorted[i]%2 != 0) // death date
{
var beginEraIndex = Array.BinarySearch(indicesSorted, 0, i, indicesSorted[i] - 1); //find birth date
double l = (i - beginEraIndex + 1)/2.0f;
maxLen = Math.Max(maxLen, (int)Math.Ceiling(l));
}
}
return maxLen;
}
dp solution code:
static void SubsetSum(int[] input, int sum)
{
int rows = sum + 1;
var cols = input.Length + 1;
var dMatrix = new byte[rows,cols];
for (var ci = 0; ci < cols; ci++)
dMatrix[0, ci] = 1;
for (var ri = 1; ri < rows; ri++)
{
for (var ci = 0; ci < cols; ci++)
{
dMatrix[ri, ci] = 0;
if (ci > 0 && dMatrix[ri, ci - 1] == 1)
{
dMatrix[ri, ci] = 1;
}
if (ci > 0)
{
var restSum = ri - input[ci - 1];
if (restSum >= 0 && dMatrix[restSum, ci - 1] == 1)
{
dMatrix[ri, ci] = 1;
}
}
}
}
var solution = rows - 1;
if(dMatrix[rows-1, cols - 1] == 1)
{
Console.WriteLine("yes");
}
else
{
Console.WriteLine("no");
}
}
agree this task seems to be very easy...
- S.Abakumoff February 02, 2013I think that all the known solutions have been discussed here:
1. heap
2. track the minimum
3. ascending minima
static void RemoveChars(ref string s, char c)
{
int index;
while (( index = s.IndexOf(c)) >= 0)
{
s = s.Substring(0, index) + s.Substring(index + 1);
}
}
static void ModifyString(string s)
{
RemoveChars(ref s, 'A');
RemoveChars(ref s, 'L');
Console.WriteLine(s);
}
forgot to note that the root of max bst is LCA of start node and end node, it's trivial to find it
- S.Abakumoff January 31, 2013do we really need the recursion for such a simple task? the iterative approach is pretty trivial to implement.
- S.Abakumoff January 31, 2013found the drawback in the algo
- S.Abakumoff January 31, 2013okay, I missed the fact that we need to find the element in the heap before removing it...thanks for correction
- S.Abakumoff January 31, 2013Okay, let's say that it's not just the priority queue, but the binary heap. The complexity of insert and delete operations of binary heap is O(log N), right?
- S.Abakumoff January 30, 2013PriorityQueue in this implementation "provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add);" - i copied it from the documentation
- S.Abakumoff January 30, 2013love this solution
- S.Abakumoff January 30, 2013could you post the code? not sure what "start from diagonal" means as the matrix is N*w, not N*N
- S.Abakumoff January 30, 2013Since the windows are intersected with each other, I think that using previous min element to get the next one might be good idea, see my reply for more details...
- S.Abakumoff January 30, 2013private static int FindMinElementIndex(int[] input, int startIndex, int endIndex)
{
var index = -1;
for (var i = startIndex; i <= endIndex; i++)
{
if (index == -1 || input[i] < input[index])
index = i;
}
return index;
}
private static void PrintMinimumElements(int[] input, int windowSize)
{
var minElementIndex = -1;
for (var i = 0; i <= input.Length - windowSize; i++)
{
if (minElementIndex != -1 && minElementIndex >= i)
{
minElementIndex = input[minElementIndex] < input[i + windowSize - 1] ? minElementIndex : i + windowSize - 1;
}
else
{
minElementIndex = FindMinElementIndex(input, i, i + windowSize - 1);
}
if(i>0)
Console.Write(", ");
Console.Write(input[minElementIndex]);
}
Console.WriteLine();
}
static void Main()
{
var array = new[] {51, 23, 47, 89, 123, 12, 78, 90, 32};
PrintMinimumElements(array, 3);
}
empty class can be used as the marker using inheritance:
class Marker{
}
class C : Marker{
}
and later the code can call something like:
var c = new C();
if(c is Marker){
}
We sometimes use empty marker interfaces, not classes.
- S.Abakumoff January 30, 2013If the input is unicode string, then this algorithm will have hard times calculating the next prime number to cover all the possible characters. This is why I down voted it. Hash map approach is more uniform one(up voted the 2nd answer).
- S.Abakumoff January 30, 2013I agree, there should be something missing in the problem description..like "the coordinates of restaurants are sorted by x coordinate", or something like that..
- S.Abakumoff January 30, 2013this problem and the idea for solution can be found in the famous book "Etudes for Programmers" by Charles Wetherell. The book suggests 4-man-weeks estimate to write the completed code for the solution + 1 week for graphics output O_o
Minor note: The problem input description that was sent here is missing the direction of to-be-filled word(horizontal or vertical)
does the code produces correct output for input
[
[1, 2, 3, 25],
[4, 23, 20, 90],
[7, 82, 95, 96],
[8, 97, 99, 101]
]
and k = 6 which is 90 ?
posted wrong solution
- S.Abakumoff January 27, 2013what if additional space is not allowed?
- S.Abakumoff January 26, 2013This code fills the array values during traversing, but the array is filled before traversing, for example it might be a[][3] = { 10,22,31, 490,513,690 ,7777,81,9}
- S.Abakumoff January 26, 2013Javascript, assuming we have LinkedList class with head property:
LinkedList.prototype.insertNode = function(value){
var prev = {
data: null,
next: this.head
};
var current = this.head;
while(current!==null && current.data < value){
prev = current;
current = current.next;
}
prev.next={
data:value,
next:current
};
if(prev.data === null)
this.head = prev.next;
};
go in-order and track the previous and current elements until end, sample of the code in Javascript:
var prev=null, current = null;
tree.inOrderTraversal(function(node){
if(!prev){
prev = current = node;
}
else{
prev = current;
current = node;
}
});
console.log(prev.data);
the problem definition does not mention ascii, it might be Unicode words
- S.Abakumoff January 20, 2013+1 to previous comment :)
- S.Abakumoff January 20, 2013do we really need to sort the data? can't we use the function that converts a word to the hash map where the key is the character code and the value is the number of occurrences? we would initially convert 5 words to 5 hash maps and then convert each word from the queue to such hash map and compare it with the 5 input hash maps. comparing means comparing the keys and their values. the complexity is O(5 + n + n * 5) = O(n * 6 + 5) = O (n) for large n values.
- S.Abakumoff January 20, 2013maybe the solution only exist for balanced bst where number of nodes = 2^(h+1) - 1 where h is the tree height. the height can be found for log N time by traversing to the left until null node. then we found the subtree which has nth smallest elem( if n <= h+1 then it is in the left subtree we go in order to the left and stop on (h+1 - n) step.
the performance is O(lgN + (h + 1 - n)) = O (lg N * 2 - n) = O(lg N)
so, for example BST has 8 nodes and it is unbalanced(node "1" in the root, root.right = 2, root.right.right=3, etc..).
the algorithm should find the kth smallest element(i.e. 6th smallest element which is 6) for logN steps(for 3 steps). Mission seems to be impossible..if the nodes are repeated then it become even more difficult..Does the solution even exist?
ah I see, I read it as nlogn :( okay, then my solution is incorrect, I voted it down
- S.Abakumoff January 19, 2013can't we solve it by run in order traversal and return on nth step, something like
var step = 0;
var value;
var prevvalue;
var n = 5;
tree.inOrderTraversal(function(node){
if(prevvalue != node.data)
step++;
if(step==n)
value = node.data;
prevvalue = node.data;
});
if(!value)
console.log('not enough nodes');
else
console.log(value);
?
it requires O(n)
could you specify the notation you are referring to? is it C notation?
- S.Abakumoff January 18, 2013javascript version:
function atoi(str, base){
var sign=1;
if(str[0]=='-'){
sign = -1;
str = str.substring(1);
}
var length = str.length - 1;
if(!base)
base = 10;
var res = 0;
var zeroCode ='0'.charCodeAt(0);
for(var i=length;i>=0;i--){
var factor = length - i;
res+=Math.pow(base, factor) * (str.charCodeAt(i) - zeroCode);
}
return res * sign;
}
I think that to address the hex and oct concerns the function might have parameter "base" that is 10 by default;
this parameter value can be also used for the input string validation.
the algorithm is simpler for bst : finding the first node that is not greater than both of the given nodes and that is not less than both of the given nodes..It does not need recursion and additional memory
- S.Abakumoff January 16, 2013Wanted to add the solution that does not involve the recursion and requires a bit of additional space(2 strings):
Tree.prototype.lowestCommonAncestor = function(data1, data2){
var root = this.root;
function getPath(data){
return (function find(node, path){
if(!node)
return null;
if(node.data == data)
return path;
var left = find(node.left, path+'0');
var right = find(node.right, path+'1');
if(left)
return left;
if(right)
return right;
return null;
})(root, '');
}
var path1 = getPath(data1);
var path2 = getPath(data2);
if(!path1 && !path2)
return null; //nodes do not exist
var lca = this.root;
var i = 0;
while(i<path1.length && i<path2.length && path1[i]==path2[i]){
if(path1[i]==='0')
lca = lca.left;
else
lca = lca.right;
i++;
}
return lca;
};
posted wrong solution, deleted
- S.Abakumoff January 13, 2013Javascript:
function work(list){
var current = list.head, secondHalf;
while(current && current.next){
if(current.data > current.next.data){
secondHalf = current;
break;
}
current = current.next;
}
while(secondHalf.next){
var data = secondHalf.next.data;
current = list.head;
var prev = {data:null, next:current};
while(current && current.data < data){
prev = current;
current = current.next;
}
var newNode = secondHalf.next;
prev.next = newNode;
secondHalf.next = newNode.next;
newNode.next =current;
if(!prev.data)
list.head = prev.next;
}
}
JavaScript, Ascii characters:
function work(str){
if(!str || !str.length)
return null;
var output='';
var upperACode= 'A'.charCodeAt(0);
var upperZCode = 'Z'.charCodeAt(0);
for(var i=0;i<str.length;i++){
var c = str.charCodeAt(i);
if(c>=upperACode && c<=upperZCode){
var prefix = i===0 ? '' : '_';
output += (prefix + str.charAt(i).toLowerCase());
}
else{
output += str.charAt(i);
}
}
return output;
}
JavaScript:
function work(array){
var zeroIndex = 0;
for(var i=0;i<array.length;i++){
if(array[i]===0 && i!=zeroIndex){
array[i] = array[zeroIndex];
array[zeroIndex] = 0;
zeroIndex++;
}
}
return array;
}
probably some set of the math formulas can be used for the O(1) solution and wide range of integers, subscribing to the thread
- S.Abakumoff February 11, 2013