This is a startup based in Bangalore, specializing in premium software development services. I have read a phase somewhere in a tech blog : Your first job is for you to learn not to earn. This is true for any kind of domain if this is your first job. Startup is best place if you believe on this although learning curve in big companies may be good too specially in product based companies. So anyway, few days ago, I gave a coding test for this startup : MountBlue Technologies pvt ltd.
There were two questions.
Level: Easy
Problem 1.
You have two arrays nums and maxes. You need to find out : for each ith element of maxes, how many elements in nums are less than or equal to that ith element of maxes. Store them into an array and print them out.
Ans: I think this is straightforward. Go to each ith element of maxes, compare it with all elements of nums, check the condition(s), if it satisfies, then counter++ and finally store the counter into an array.
This will take O(m*n) time in worst case (same for average case too). You will be forced to traverse all elements of nums.
But there is another way which won't traverse all elements of nums. First you need to store all elements of nums into a binary tree and now traverse through each ith element of maxes and compare that ith element with binary tree elements. In worst case, it will take O(m*n) but in average case, it will perform better than first algorithm.
Here is the code:
(Programming language I used: C++)
#include <iostream>
using namespace std;
int c=0;
class btree{
public:
int data;
btree* left;
btree* right;
btree* add(int d, btree* root){
if(root==NULL){
btree* b=new btree();
b->data=d;
b->left=NULL;
b->right=NULL;
root=b;
return root;
}
if(d<=root->data){
root->left=add(d, root->left);
}else{
root->right=add(d, root->right);
}
return root;
}
void print(btree* r){
if(r==NULL){
return;
}
cout << r->data << endl;
print(r->left);
print(r->right);
}
};
void getNum(btree* r, int x){
if(r==NULL){
return;
}
if(r->data>x){
getNum(r->left, x);
}else if(r->data<=x){
c++;
getNum(r->left, x);
getNum(r->right, x);
}
}
void ans(btree* root, int* maxes, int m){
vector<int> v;
for(int i=0;i<m;i++){
int x=maxes[i];
btree* r=root;
c=0;
getNum(r, x);
v.push_back(c);
}
cout << "ans: " << endl;
for(int i=0;i<v.size();i++){
cout << v[i] << " ";
}
}
int main(){
btree* b=new btree();
btree* root=NULL;
int n;
cout << "enter n: " << endl;
cin >> n;
int nums[n];
cout<< "enter nums: " << endl;
for(int i=0;i<n;i++){
cin >> nums[i];
root=b->add(nums[i], root);
}
//b->print(root);
int m;
cout << "enter m: " << endl;
cin >> m;
int maxes[m];
cout << "enter maxes: " << endl;
for(int i=0;i<m;i++){
cin >> maxes[i];
}
ans(root, maxes, m);
return 0;
}
Problem 2.
You have a list of original items and their respective original prices. You have a helper who sells your items(by decreasing/increasing or same original price). You need to find out how many items have been sold in different prices than original prices.
Ans: Again instead of looping through original items and sold items, which will take O(m*n) in average case, use hashing.
Hash each element of original items into a map and now traverse through each element of sold items and compare it with hashed original items, if found different prices, counter++, and finally print out counter.
Here is the code:
#include <iostream>
#include <map>
using namespace std;
int getFraud(string* items1, float* prices1, int n, string* items2, float* prices2, int m){
map<string, float> m1;
int c=0;
for(int i=0;i<n;i++){
m1[items1[i]]=prices1[i];
}
for(int i=0;i<m;i++){
string s2=items2[i];
float p2=prices2[i];
if(m1[s2]!=p2){
c++;
}
}
return c;
}
int main(){
int n;
cout << "enter n: " << endl;
cin >> n;
string origItems[n];
float origPrices[n];
cout << "enter original items and prices: " << endl;
for(int i=0;i<n;i++){
cin >> origItems[i] >> origPrices[i];
}
int m;
cout << "enter m: " << endl;
cin >> m;
string items[m];
float prices[m];
cout << "enter items and prices: " << endl;
for(int i=0;i<m;i++){
cin >> items[i] >> prices[i];
}
cout << "fraud found: " << getFraud(origItems, origPrices, n, items, prices, m) << endl;
return 0;
}
If anything found wrong, please let know.
There were two questions.
Level: Easy
Problem 1.
You have two arrays nums and maxes. You need to find out : for each ith element of maxes, how many elements in nums are less than or equal to that ith element of maxes. Store them into an array and print them out.
Ans: I think this is straightforward. Go to each ith element of maxes, compare it with all elements of nums, check the condition(s), if it satisfies, then counter++ and finally store the counter into an array.
This will take O(m*n) time in worst case (same for average case too). You will be forced to traverse all elements of nums.
But there is another way which won't traverse all elements of nums. First you need to store all elements of nums into a binary tree and now traverse through each ith element of maxes and compare that ith element with binary tree elements. In worst case, it will take O(m*n) but in average case, it will perform better than first algorithm.
Here is the code:
(Programming language I used: C++)
#include <iostream>
using namespace std;
int c=0;
class btree{
public:
int data;
btree* left;
btree* right;
btree* add(int d, btree* root){
if(root==NULL){
btree* b=new btree();
b->data=d;
b->left=NULL;
b->right=NULL;
root=b;
return root;
}
if(d<=root->data){
root->left=add(d, root->left);
}else{
root->right=add(d, root->right);
}
return root;
}
void print(btree* r){
if(r==NULL){
return;
}
cout << r->data << endl;
print(r->left);
print(r->right);
}
};
void getNum(btree* r, int x){
if(r==NULL){
return;
}
if(r->data>x){
getNum(r->left, x);
}else if(r->data<=x){
c++;
getNum(r->left, x);
getNum(r->right, x);
}
}
void ans(btree* root, int* maxes, int m){
vector<int> v;
for(int i=0;i<m;i++){
int x=maxes[i];
btree* r=root;
c=0;
getNum(r, x);
v.push_back(c);
}
cout << "ans: " << endl;
for(int i=0;i<v.size();i++){
cout << v[i] << " ";
}
}
int main(){
btree* b=new btree();
btree* root=NULL;
int n;
cout << "enter n: " << endl;
cin >> n;
int nums[n];
cout<< "enter nums: " << endl;
for(int i=0;i<n;i++){
cin >> nums[i];
root=b->add(nums[i], root);
}
//b->print(root);
int m;
cout << "enter m: " << endl;
cin >> m;
int maxes[m];
cout << "enter maxes: " << endl;
for(int i=0;i<m;i++){
cin >> maxes[i];
}
ans(root, maxes, m);
return 0;
}
Problem 2.
You have a list of original items and their respective original prices. You have a helper who sells your items(by decreasing/increasing or same original price). You need to find out how many items have been sold in different prices than original prices.
Ans: Again instead of looping through original items and sold items, which will take O(m*n) in average case, use hashing.
Hash each element of original items into a map and now traverse through each element of sold items and compare it with hashed original items, if found different prices, counter++, and finally print out counter.
Here is the code:
#include <iostream>
#include <map>
using namespace std;
int getFraud(string* items1, float* prices1, int n, string* items2, float* prices2, int m){
map<string, float> m1;
int c=0;
for(int i=0;i<n;i++){
m1[items1[i]]=prices1[i];
}
for(int i=0;i<m;i++){
string s2=items2[i];
float p2=prices2[i];
if(m1[s2]!=p2){
c++;
}
}
return c;
}
int main(){
int n;
cout << "enter n: " << endl;
cin >> n;
string origItems[n];
float origPrices[n];
cout << "enter original items and prices: " << endl;
for(int i=0;i<n;i++){
cin >> origItems[i] >> origPrices[i];
}
int m;
cout << "enter m: " << endl;
cin >> m;
string items[m];
float prices[m];
cout << "enter items and prices: " << endl;
for(int i=0;i<m;i++){
cin >> items[i] >> prices[i];
}
cout << "fraud found: " << getFraud(origItems, origPrices, n, items, prices, m) << endl;
return 0;
}
If anything found wrong, please let know.
