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
This question is asking the first missing positive integer from the list of n integers. (Total n1 integers given and return value should be an integer missing (m) from this list. So, it is implied that 1<=m<=n.
#include<iostream>
#include<vector>
using namespace std;
int missingInt(vector<int> v) {
int cnt=0, tmp=v[0],n=v.size(),i=0;
while(cnt<=n) {
if(v[i] != i+1 && v[i]<=n) {
tmp = v[v[i]1];
v[v[i]1] = v[i];
v[i]=tmp;
}
else i++;
cnt++;
}
int j=0;
for( j=0;j<n;++j)
if(v[j]!=j+1) return j+1;
return j+1;
}
int main() {
vector<int> v = {4,1,5,3}; // Don't sort it. Otherwise it will be n log(n).
int ret = missingInt(v);
cout<<ret;
return 0;
}

alanturing06022014
August 03, 2019 // can be implemented CPP using STL as below:
1. set<person_id> f_frnds = get_friends(person_id)
2. map<person_id,int> mp;
for f in f_frnds:
do
set<person_id> f_frnd_list = get_friends(f);
set<person_id> diff_set = set_difference(f_frnd_list, set_union(f_frnds,p));
for element in diff_set:
do
mp[element]++;
done
done
3. Now, this mp contains all the persons who are friends of all friends of p but not in his friend list yet. You can sort this list based on second field (count of common friends), and publish the results in descending order.

alanturing06022014
August 03, 2019 #include<iostream>
using namespace std;
int main() {
bool pack[4][13] = {{0,0}};
bool play=false;
int pack_type=0,number = 0,cnt=0;
cout<<"\nEnter pack_type (1spade, 2diamond, 3heart, 4club (0 for break):"; cin>>pack_type;
cout<<"Enter number (Ace1, 22,33..., J11, Q12, K13 (0 for break):"; cin>> number;
while (pack_type !=0 && number !=0) {
if(pack_type <1  pack_type>4  number<1 number >13)
return 1;
if (pack[pack_type1][number1]==true) {
cout<<"Dup entry";
return 1;
}
pack[pack_type1][number1]=true;
cnt++;
cout<<"\nEnter pack_type (1spade, 2diamond, 3heart, 4club (0 for break):"; cin>>pack_type;
cout<<"Enter number (Ace1, 22,33..., J11, Q12, K13 (0 for break):"; cin>> number;
}
if(cnt<3) cout<<"Can't play!!";
for(int i=0;i<4;i++) {
for (int j=0;j<11;j++) {
if (pack[i][j] && pack[i][j+1] && pack[i][j+2]) {
cout<<"Trace1: I can continue to play!!";
printf("Combo :\n %d>%d \n %d>%d \n%d>%d \n",i+1,j+1,i+1,j+2,i+1,j+3);
play=true;
break;
}
}
if(play) {
return 0;
}
}
for(int i=0;i<2;i++) {
for (int j=0;j<13;j++) {
if(pack[i][j] &&pack[i+1][j] &&pack[i+2][j]) {
cout<<"Trace 2:I can continue to play!!";
printf("Combo :\n %d>%d \n %d>%d \n%d>%d \n",i+1,j+1,i+2,j+1,i+3,j+1);
play=true;
break;
}
}
if(play) {
return 0;
}
}
for(int i=0;i<4;i++) {
for (int j=0;j<11;j++) {
cout<<pack[i][j];
}
cout<<'\n';
}
cout<<"I cannot continue to play!!";
return 1;
}

alanturing06022014
August 02, 2019 #include <iostream>
using namespace std;
int findPeri(int apples) {
int sum=0;
int x[] = {1,1,1,0,0,1,1,1};
int y[] = {1,0,1,1,1,1,0,1};
for (int i=0;i<8;++i) {
x[i]<0?(x[i]*=1):x[i];
y[i]<0?(y[i]*=1):y[i];
}
int factor=1;
while(sum<apples) {
for (int i=0;i<8;++i){
sum += x[i]+y[i];
}
if(sum>=apples) break;
++factor;
for (int i=0;i<8;++i) {
x[i]*=factor; y[i]*=factor;
}
}
cout<<endl<<"Sum:"<<sum;
return factor<<3;
}
int main() {
int a; cin>>a;
int p = findPeri(a);
cout<<endl<<"Perimeter:"<<p;
return 0;
}

alanturing06022014
July 30, 2019 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:
int getMinCost(int a[], int n)
{
1. Create min heap (lets say pq) and push all elements of array into min heap (STL priority queue acts like min heap so you can use that).
2. int sum=0;
// heap size is n initially (number of array elements)
while(n>1) {
top1= pq.top(); top2 =pq.top();
sum+=top1+top2;
pq.push_back(top1+top2);
// priority queue runs heapify() itself.
n;
}
return sum;
}

alanturing06022014
May 14, 2019 @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
Things to note (to save space) is:
 alanturing06022014 August 03, 20191. If a char (e.g.) occurs just once, there is no need to write its count. That will save 1 byte:
2. Count of chars = largestNumber built from digits following it. (If a char is followed by another char, that means first char occurred just once).