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 SDE-2 Algorithm
Things to note (to save space) is:
1. 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).
This question is asking the first missing positive integer from the list of n integers. (Total n-1 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;
}
// 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.
#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 (1-spade, 2-diamond, 3-heart, 4-club (0 for break):"; cin>>pack_type;
cout<<"Enter number (Ace-1, 2-2,3-3..., J-11, Q-12, K-13 (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_type-1][number-1]==true) {
cout<<"Dup entry";
return -1;
}
pack[pack_type-1][number-1]=true;
cnt++;
cout<<"\nEnter pack_type (1-spade, 2-diamond, 3-heart, 4-club (0 for break):"; cin>>pack_type;
cout<<"Enter number (Ace-1, 2-2,3-3..., J-11, Q-12, K-13 (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;
}
#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;
}
This is very famous problem asked by Amazon thousand number of times. It is a min-heap 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;
}
@animageofmine
This is in-fact a 20-min question. You just need to increase the number of room when start time of next meeting is before end-time 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;
}
};
L N O
There is a skipped letter after each 2.
- alanturing06022014 July 08, 2020