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[i1]'a'];
alpha2[s[i+l21]'a']++;
if(alpha2 == alpha1)
return true;
}
return false;
}

sigkill
July 07, 2014 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[i1]'a'];
alpha2[s[i+l21]'a']++;
if(alpha2 == alpha1)
return true;
}
return false;
}

sigkill
July 07, 2014 For any balanced BST, maintain a count of number of nodes in its left subtree 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,rightThird1);
else
ts(leftThird, rightThird);
}
int main()
{
int n;
cin>>n;
arr.resize(n);
rep(i,0,n)
{
s(arr[i]);
}
int ans = ts(0,n1);
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;
}
}
Open Chat in New Window
Isn't this solution looks analogous to bucket sort, where instead of buckets you are using bitsets.
 sigkill July 11, 2014