Algorithmist
BAN USER- 0of 0 votes
AnswersScenario : Multi Seller E-commerce Website
- Algorithmist in India
Given a list of products in a customer basket find the minimum number of seller required to deliver his order,so as to optimise shipping part.
Assuming you have already have below data
Customer orders products : P1,P2,P3,P4,P5,P6
Products and seller mapping
P1 = [1,2,3,4]
P2=[2,4,5,6]
where 1,2,3 etc denotes seller_ids.
p1| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
Hi Amit H is a HashMap not an array.And I believe you already know searching for an element in an HashMap takes O(1) time.
- Algorithmist September 02, 2013Your approach to problem is correct,but time complexity analysis is wrong.Above is an O(N^2) algorithm(consider when all elements all in descending order then you would do swap for every new element to be inserted in you linked list).It is better to construct an Heap of Size K if you may be required to return k'th smallest element from file.
- Algorithmist September 01, 2013There are two solutions
1. Naive O(n^3) approach
Use three for loops and check for Pythagorean property.
2. Better O(N^2) approach
A.Convert original array into an array containing square of all the elements. Call it A.
B.Put all elements of A into an HashMap say H.
C. Do below steps
For each element in A
{
required sum=A[i]
call printSum(required_sum,A,H)
}
void printSum(required_sum,A,H)
{
for each element in A say x
check if sum-x is present in H
if yes print square root of required_sum,x and required_sum -x.
}
Thus the overall complexity of this approach is O(n^2)
Note:
Some Special handling also needs to be done if array contains duplicate,else you will return the same triplets again and again.
@Guru Please read the question carefully,it has been clearly mentioned in the last line that both the threads are created on the same object.
- Algorithmist August 10, 2013@Mahanth Even if you change the code as below it would not result in any change
class Test
{
public void m1(StringBuffer arg1){
arg1 = "Am I going to disappear?";
}
public static void main (String[] args)
{
Test test = new Test();
StringBuffer iAmOfAnArgumentativeNature = new StringBuffer("I am born new");
m1(iAmOfAnArgumentativeNature);
System.out.print(iAmOfAnArgumentativeNature);
}
}// end class
only if you would have called append method on StringBuffer in m1() its value would have been changed in the main method.
- Algorithmist July 21, 2013Sorry I didn't saw the update :).it would print I am born new ,mainly because it is arg1 which has started to reference other string ,original reference variable "iAmOfAnArgumentativeNature " still points to the string "I am born new".
And 10x for sharing the question :).
If both the threads are created on the same object(which is the case in above), then only one of the thread would be able to enter any synchronized methods in that class. Reason being that non-static synchronized methods obtain lock on Object ,and thus say if T1 enters m1() it means it has acquired lock on Object a1 and now if T2 tries to enter m2() it would fail to obtain the lock on a1 and thus would go in wait state.
Note:If both Threads would have been created on different objects then both threads would have executed m1() and m2() simultaneously.
Above Code would result in Compile time error. In Java you cannot call a non-static method from a static method.
- Algorithmist July 11, 2013but using inorder traversal you cannot decide whether two trees are equal or not.
- Algorithmist June 17, 2013I thought for a while and said it is not possible without extra space for iterative solution.
- Algorithmist June 17, 2013But wouldn't that be time consuming...
- Algorithmist June 14, 2013Ok..so instead of using captcha, some other advertisement should be displayed in between and a click button saying "skip to Advertisement".. only a human user would be able to click and identify this.
- Algorithmist June 14, 2013Probably before redirecting to actual add website ..use some sort of captcha.This captcha would come into picture once user clicks on add.
- Algorithmist June 14, 2013Some of the matrices i can think of
1.Determine the capacity of motor first..
2. How many people at once are currently travelling in lift.
Say if employees want it to reach the top-most floor after x seconds, then based on above two data we can set a limit on the number of people that should go inside the lift at once/per floor. Maybe because more no of people are travelling at once its speed is less.
3.Average age of employees.. Say if most people are young encourage them to use stairs rather than lift.
4.Time duration at which lift is mostly used...so at time of rush we can allow more people to travel but with info that lift would take more time..so either wait outside the lift or inside the lift :)
This can be easily solved using Zig-Zag level order traversal of the given tree.Use 2 stacks to do the zig zig level order traversal.
For More detail explanation just google "leetcode : printing-binary-tree-in-zig-zag-level".
Below is a small working code for the same. TreeNode represents our Tree.
void printExtremeNodes(TreeNode root) {
if (root == null)
return;
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
Stack<TreeNode> tempStack = null;
stack1.push(root);
TreeNode temp = null, left, right;
int i = 0, level = 0;
while (!stack1.isEmpty()) {
i = 0;
while (!stack1.isEmpty()) {
temp = stack1.pop();
if (i == 0)
System.out.println(temp.data);
left = temp.left;
right = temp.right;
if (level % 2 == 0) {
if (left != null)
stack2.push(left);
if(right!=null)
stack2.push(right);
} else {
if (right != null)
stack2.push(right);
if (left != null)
stack2.push(left);
}
++i;
}
tempStack = stack1;
stack1 = stack2;
stack2 = tempStack;
++level;
}
}
As given in the example test case itself, consider root as the extreme left.
- Algorithmist June 10, 2013For Tracking unique elements we can use one of the implementations of Set Interface say HashSet to store final elements that match the given criteria.
- Algorithmist June 04, 2013Above Query is wrong.It would also return students studying more than 2 subjects.We need to return students studying either DS or Networking and not any other subjects, else the query is pretty easy.
So we can do concatenation of all the subjects and check that it is either DSNetworking or NetworkingDS. This would do the job.
Create an Empty HashTable.. Iterate through given array and check if currentElement is already there in Map. If yes then do not add this element in map, else add this element to map. In the end the map would contain only unique elements. So done in O(N) space and O(N) time.
- Algorithmist April 10, 2013You Must have Asked regarding the Type of Operations/Queries that would be performed on above Data..Then only can decide the DS to be used.
- Algorithmist March 31, 2013In this approach,lots of unnecessary swaps are being done.. Say I have array as 0,0,1,0,1,1,0,1. Now as per above logic I would swap when i=2 and j=n-1 , but this swap is not required actually(Swapping 1 with 1 doesn't make any sense). So better approach is already posted by amritaansh123 .Please see below that answer.
- Algorithmist March 25, 2013It is much better then using two pointer approach. No Swaps required.
- Algorithmist March 25, 2013Below is a simple approach to solve this problem
int minWeightedNode(TreeNode node)
1. if node is null return Integer.max;
2.else
a.currentSum=node.val;
b.if node.left is not null then
currentSum+=node.left.val
c. if node.right is not null then
currentSum+=node.right.val
return min(current,min(minWeighedNode(node.left),min(minWeighedNode(node.right));
If you are creating an array of size 50k, then what is the purpose of this statement given in the question "there are 10000 numbers between 1 and 50000". Is there any possible solution which uses only 10k size array.
- Algorithmist March 19, 2013Using level Order Traversal we can determine the maximum depth of the Tree. The lowest level we can reach is the height of the tree. This involves the use of 2 stacks. For current level all the nodes are pushed on a temporary stack and then at the end of iteration put into Main Stack. We continue till main stack is not empty.
import java.util.Iterator;
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public int maxDepth(TreeNode root) {
if(root==null)
return 0;
int depth=0;
Stack<TreeNode>elements=new Stack<TreeNode>();
Stack<TreeNode>curElements=new Stack<TreeNode>();
elements.push(root);
TreeNode temp=null;
while(!elements.isEmpty())
{
++depth;;
while(!elements.isEmpty())
{
temp=elements.pop();
if(temp.left!=null)
curElements.push(temp.left);
if(temp.right!=null)
curElements.push(temp.right);
}
elements.addAll(curElements);
}
return depth;
}
}
- Algorithmist February 27, 2013
Repnancyhfloress, Computer Scientist at AMD
Hey there, I’m Nancy. I’m a small business owner living in Sunrise, FL 33323. I am a fan ...
Hey Abhinav,Can you explain the same in detail.
- Algorithmist February 27, 2015