sigkill
BAN USER- 1of 3 votes
AnswersGive efficient implementation of the following problem.
- sigkill in India
An item consist of different keys say k1, k2, k3. User can insert any number of items in database, search for item using any key, delete it using any key and iterate through all the items in sorted order using any key. Give the most efficient way such that it supports insertion, search based on a key, iteration and deletion.| Report Duplicate | Flag | PURGE
Google Intern Algorithm
sorry a minute correction its i + l2 -1 < l1
bool isSubstr(string s, string sub)
{
int l1 = s.length();
int l2 = sub.length();
if(l2 > l1)
return false;
string alpha2 = "00000000000000000000000000";
string alpha1 = "00000000000000000000000000";
for(int i = 0;i < l2;i++)
{
alpha1[sub[i] - 'a']++;
alpha2[s[i]-'a']++;
}
if(alpha2 == alpha1)
return true;
for(int i = 1;i +l2 -1 < l1;i++)
{
alpha2[s[i-1]-'a']--;
alpha2[s[i+l2-1]-'a']++;
if(alpha2 == alpha1)
return true;
}
return false;
}
An easy solution assuming alphabets from 'a' to 'z' allowed.
Time O(N)
Space O(1)
bool isSubstr(string s, string sub)
{
int l1 = s.length();
int l2 = sub.length();
if(l2 > l1)
return false;
string alpha2 = "00000000000000000000000000";
string alpha1 = "00000000000000000000000000";
for(int i = 0;i < l2;i++)
{
alpha1[sub[i] - 'a']++;
alpha2[s[i]-'a']++;
}
if(alpha2 == alpha1)
return true;
for(int i = 1;i +l2 < l1;i++)
{
printf("here\n");
alpha2[s[i-1]-'a']--;
alpha2[s[i+l2-1]-'a']++;
if(alpha2 == alpha1)
return true;
}
return false;
}
For any balanced BST, maintain a count of number of nodes in its left sub-tree and number of nodes in right subtree + 1 (for itself). This can be maintained in constant time during insertion and deletion. Now finding a median is just finding the key with rank n/2 where n is total number of elements.
Time complexity - O(log n) in worst case.
Space Complexity - O(1)
Using Ternary Search :
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <cassert>
using namespace std;
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define repe(i,a,b) for(long long i=a;i<=b;i++)
#define vi vector<int>
#define vll vector<long long>
#define ll long long
#define vll vector<long long>
#define s(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pb push_back
#define mp make_pair
vi arr;
int ts(int left, int right)
{
// printf("left = %d right = %d\n",left, right);
if(right - left <1)
{
return arr[(left + right)/2];
}
int leftThird = left + (right - left)/3;
int rightThird = right - (right - left)/3;
if(arr[leftThird] < arr[rightThird])
ts(leftThird+1,right);
else if(arr[leftThird] > arr[rightThird])
ts(left,rightThird-1);
else
ts(leftThird, rightThird);
}
int main()
{
int n;
cin>>n;
arr.resize(n);
rep(i,0,n)
{
s(arr[i]);
}
int ans = ts(0,n-1);
printf("%d\n",ans);
}
node* mirrorBST(node *bst1 , node *bst2)
{
if(bst1 != NULL)
{
bst2 = (node*)malloc(sizeof(node));
bst2->val = bst1->val;
bst2->left = NULL;
bst2->right = NULL;
//printf("v = %d\n",root2->val );
bst2->right = mirrorBST(bst1->left,bst2->right);
bst2->left = mirrorBST(bst1->right,bst2->left);
return bst2;
}
else
{
return NULL;
}
}
RepEileenBaker, Applications Developer at ABC TECH SUPPORT
I am an experienced and dedicated professional with a track record of effective mentorship. Nowaday most people search for Ambani ...
Isn't this solution looks analogous to bucket sort, where instead of buckets you are using bitsets.
- sigkill July 11, 2014