alanturing06022014
BAN USER 0of 0 votes
AnswersFind whether a number (which is less than 10000) is a perfect square or not. If it is perfect square, calculate square root in O(1) without using sqrt function.
 alanturing06022014 in United States
Example : 1024 => 32
1025=> not perfect square. Report Duplicate  Flag  PURGE
Microsoft SDE1 Algorithm  0of 0 votes
AnswersYou are to concatenate n strings (concatenate in any order) and a function:
 alanturing06022014 in United States
int strCat(str1, str2); // returns the concatenated str length
Concatenate all strings in any order so that total cost is minimum.
Example: Strings A="abc", B="wxyz", C="a"
Cost of strCat(A,B) = (3+4) = 7
Cost of strCat(AB,C) = 7+1 = 8
Total cost = 7+8 =15
Other way:
Cost of strCat (A,C) = 3+1 = 4,
Cost of strCat (AC,B) = 4+4 = 8
Total Cost = 4+8 = 12
In this case, min(12,15) = 12 so Ans=12. Report Duplicate  Flag  PURGE
Amazon SDE2 Algorithm
@animageofmine
This is infact a 20min question. You just need to increase the number of room when start time of next meeting is before endtime of previous meeting and keep track of global max.
Suppose meeting structure is: meet (ST, ET) (ST: start time and ET: end time)
1. sort the meetings in order of start time
2. initially, number of meeting room rooms=1, max_rooms=1;
3.
from (j=0,i=1; i<n;i++) (when order starts from 0) {
while (meeting[i].ST < meeting[j].ET)
{ rooms++; i++;}
if (rooms > max_rooms)
max_rooms = rooms;
j++;
}
return max_rooms;
 alanturing06022014 January 15, 2019Decorator and Visitor seem relevant here. Decorator looks more suited out of the 2... as type of taxes can vary in nature.
// Abstract class Tax
Class Item {
String Category;
String Name;
double Price;
public:
Item () { Category="default"; Name="item"; Price=0.0; }
Item (String ct, String nm, double pr) { Category=ct; Name=nm; Price=pr; }
virtual double getPrice() { return Price;}
virtual double setPrice(double d) { this.Price = d;}
};
virtual double applyTax (Tax taxType) { };
}; // End of Item class
// Abstract class Tax
class Tax {
double rate;
public:
Tax () { }
Tax (double rt) { rate = rt;}
virtual Item getPriceAfterTax(Item& item) {
item.setPrice(item.getPrice*(1+(rate/100)));
return item;
}
};

alanturing06022014
June 21, 2018 L N O
There is a skipped letter after each 2.
Open Chat in New Window
This is very famous problem asked by Amazon thousand number of times. It is a minheap problem.
They also presented once to me like this:
We have a strcat(s1,s2) that is 3rd party function. Every time you run this function, you need to pay cost s1.length()+s2.length() to 3rd party. You have to minimize this cost.
Suppose you have arrayp[ = {3,4,6,9},
If you start adding bigger numbers first, the cost is (9+6) + ((9+6)+4) + ((9+6+4)+3). You can see that 9 occurred most number of times. So, cost is more. Instead, if you start with 2 smallest numbers, cost will be calculated like this:
1. (3+4=7), now we have {7,6,9}
2. Take min 2 from these (6+7)=13, now we have (13,9)
3. Take min. 2 from these. and final sum is 22.

So, every time it is about taking minimum 2 numbers, adding them and putting the resultant sum back in set (or array). Again find 2 min. numbers, add them...
Repeat this process until you have a single element (or let's say you have 2 elements and sum them.).
So, algo goes like this:
 alanturing06022014 May 14, 2019