parag
BAN USER- -5of 7 votes
AnswersAlgorithm to find square root of an algorithm
- parag in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
The problem has two parts:
1. Identify the first number (number of digits it must have)
2. Using Arithmetic Progression find the missing number.
For 1.
i)Convert String into an array of single digit integers, "r". Set start_number as r[0]
ii) Iterate through array and check following:
1. If r[i+1] - r[1]== 1 go ahead and increment sum with this element
2. else if r[i+1] - r[i]<0 || r[i+1] - r[i] >2
Go to step i) and reform with next group of digits, i.e. if you had broken down strings with group of one digit, increment this grouping logic to 2 and so on. Reset sum variable to 0.
Missing number(if sequence is correct) = (r[0] + n(n-1)/2 ) - sum
where n is the length of array r.
JMX is your answer. You will create JMX agents in all servers, each agent to carry out those tasks and return status once complete. It has another function of cancelling the task. So each JVM node is configured with this agent as well as with other information as in how many worker threads each one should have etc. Then you create a central JVM with JMX manager to which all these agents report to. Manager initiates all agents and is reponsible for allocation of task to agents so that all jvms are equally occupied. Manager can also provide a function to cancel task which allows it to communicate with each other agent in cacelling and stopping execution of task.
- parag June 27, 2013TreeMap will have higher time complexity for search around O(logn). While hashtable has a complexity of O(1), compromising on search capability is not good. Ideally, implement a linked list wrapper over hashtable, so as in an element get inserted in hashtable, it also gets inserted in linked list, if it is removed from hashtable then it is also removed from linked list. Although an additional space is compromised. Also this question is about ordering of insertion and not about sorted order.
- parag June 27, 2013In interview, I also came up with similar algorithm, but this algorithm is in order of n. Interviewer was not impressed with it and he kept pushing me to come up with something better, he hinted me that i can use some sort of partitioning, but it didnt clicked to me. I think the answer I have posted above is ok, but looking forward if there are any issues in that or still if there is a better solution.
- parag June 27, 2013Lets say this number is n and given that n is a square, so simplest way to deal with it will be to iterate till n and see if i*i=n. However this was not acceptable, although interviewer hinted me a lot, but it clicked me only once the interview was over. It is basic school mathematics. The answer to this question lies on how we calculate square root mathematically. We divide the digits of the number in groups of two, if the number of digits is odd, then left most one is single member of group. And then we keep on finding closest square to the group and passing on remainder to next group. This way each group will be iterated by 9 digits (9*9=81, highest 2 digit square) and overall complexity will be order of the number of digits of number. Please let me know if this is correct approach or if there is a better way of achieving it.
- parag June 27, 2013
Replyndaander9, Analyst at A9
My name is Anderson and I am a 24 years old trader born and currently working in New York, USA ...
in that case missing number will be 0. yes that should be additional check. Please correct me if i am missing something.
- parag August 13, 2013