isandesh7
BAN USERIn a hash table you could lock on a particular key value pair, so that no one can delete that key when one thread is using it. but anything can happen to the rest of the keys you don't care. But in a tree map you can't do that since it's implemented as a red black tree during an insertion/deletion the whole data structure can change. due to the rotations performed in it. so if you lock one key you are basically locking the whole data structure.
- isandesh7 February 17, 2013if you have key value pairs ... It depends on the range of hash(keys) that you want to store... If the range of Hash(keys) is high. Then hash map will take more space. and you are better of with treemap.. Also if there are huge number of collisions then space of hasmap is same as tree map. But complexity is more
- isandesh7 February 17, 2013Just like normal variables, pointers can be declared constant. There are two different ways that pointers and const can be intermixed, and they are very easy to mix up.
To declare a const pointer, use the const keyword between the asterisk and the pointer name:
int nValue = 5;
int *const pnPtr = &nValue;
Just like a normal const variable, a const pointer must be initialized to a value upon declaration, and its value can not be changed. This means a const pointer will always point to the same value. In the above case, pnPtr will always point to the address of nValue. However, because the value being pointed to is still non-const, it is possible to change the value being pointed to via dereferencing the pointer:
*pnPtr = 6; // allowed, since pnPtr points to a non-const int
It is also possible to declare a pointer to a constant variable by using the const before the data type.
int nValue = 5;
const int *pnPtr = &nValue;
Note that the pointer to a constant variable does not actually have to point to a constant variable! Instead, think of it this way: a pointer to a constant variable treats the variable as constant when it is accessed through the pointer.
Thus, the following is okay:
nValue = 6; // nValue is non-const
But the following is not:
1
*pnPtr = 6; // pnPtr treats its value as const
Because a pointer to a const value is a non-const pointer, the pointer can be redirected to point at other values:
int nValue = 5;
int nValue2 = 6;
const int *pnPtr = &nValue;
pnPtr = &nValue2; // okay
To summarize:
A non-const pointer can be redirected to point to other addresses.
A const pointer always points to the same address, and this address can not be changed.
A pointer to a non-const value can change the value it is pointing to.
A pointer to a const value treats the value as const (even if it is not), and thus can not change the value it is pointing to.
Finally, it is possible to declare a const pointer to a const value:
const int nValue;
const int *const pnPtr = &nValue;
A const pointer to a const value can not be redirected to point to another address, nor can the value it is pointing to be changed.
Const pointers are primarily used for passing variables to functions. We will discuss this further in the section on functions.
Consider this matrix
0 1 1 0 0
0 0 0 1 1
0 1 0 1 1
0 1 1 1 0
0 1 1 1 0
1 0 1 1 0
At every row i will do a[i] && a[i+i]
Which will give me if i am able to form any new rectangles
Simultaneously i will maintain a max heap of rectangles
Rectangle = corner1, corner2, area.
Optional step
I will remove a rectangle if it is evident there can be no more 1's added to it and it is not the Max area rectangle.
I will then do a a[i] && a[i-1] and see if the any previous rectangles can be increased in size.
If so i will do so.
In the end i will output the max from heap.
here's how it will go
Just showing this for explanation i am not changing the array or taking extra array.
0 1 1 0 0
0 0 0 2 2
0 0 0 2 2
0 6 6 6 0
0 6 6/8 6/8 0
0 0 8 8 0
List of Rectangles
1 corner1,corner2 size=2
3 corner1,corner2 size=4
6 corner1,corner2 size=6
8 corner1,corner2 size=4
Max Size = 6
Complexity -- I am only scanning the array once. But each time i may have to look at all the previous rectangles which may be.
O( rows * (number of rectangles) )
This is giving the correct answer but is worst time possible
int TellSeq(int index) {
int i = 0, j = 0, k = 0;
for (; i < 10; i++) {
cout << "\n" << (i + 1) << " " << i;
if (i+1 == index)
return i;
}
index--;
for (i = 10; i <= 65532; i++) {
if (i % 2 == 0) {
cout << "\n" << (i + 1) << " " << (j++) % 10 << " ";
if (i + 1 == index)
return j % 10;
if (j % 10 == 0)
k++;
} else {
cout << "\n" << (i + 1) << " " << (k) % 10 << " ";
if (i + 1 == index)
return k % 10;
}
}
}
Naive Recursive approach Approach..
Scan the string.. At every point you find a word. check if you can form a sentence from the rest of the charactors. if yes return 1 and the string formed.
else move on to the next charactor.
If you move till the end of the charactor return 0. -- A sentence cannot be formed.
int CheckSentence(char c[], char rest[], int l) {
char sentence[2 * strlen(c)];
char rest[2*strlen(c)];
if(l>=strelen(c))
return 1;
for (int i = l; c[i]!=0; i++) {
sentence[j] = c[i];
if (isWord(toWord(c,l, i)) && CheckSentence(c, rest,i+1)) {
strapp(sentence, ' ');
strapp(sentence, rest);
strapp(sentence,'\0');
strcpy(rest,sentence);
return 1;
}
}
return 0;
}
/*
Lets imagine this as intervals of x and y.
At any given Year say 70. The number of dinasarus that lived at that time =
Number of dinasours that were born before 70 MINUS Number of dinasours that died before 70.
Sort the x and y co - ordinates separately in two arrays. O(n) this is our space complexity.
Sort both these arrays. == nlogn. This is our time complexity. If we get them already sorted then time complexity is O(n).
Start scanning the death array. for every death array element do -
Scan the birth array till you reach a year greater than the current death year.
Number of dinasours born before the death year = birth array index.
Number of dinasours died before the death year = death array index.
max = Max(max,(birth array index - death array index).
In the end you will get the max dinasours that lived together... then i guess they vanished.... leaving us.. .puzzled
void c15377680Dinasour(int bd[], int n) {
int b[n / 2], d[n / 2];
for (int i = 0; i < n - 1; b[i / 2] = bd[i], i += 2);
for (int i = 1; i < n; d[i / 2] = bd[i], i += 2);
quickSort(d, n / 2);
quickSort(b, n / 2);
int j = 0, max = 0;
for (int i = 0; i < n / 2; i++) {
while (b[j] < d[i] && j < n) j++;
max = max > (j - i) ? max : (j - i);
}
cout<<"\n"<<max;
}
/*
Lets imagine this as intervals of x and y.
At any given Year say 70. The number of dinasarus that lived at that time =
Number of dinasours that were born before 70 MINUS Number of dinasours that died before 70.
Sort the x and y co - ordinates separately in two arrays. O(n) this is our space complexity.
Sort both these arrays. == nlogn. This is our time complexity. If we get them already sorted then time complexity is O(n).
Start scanning the death array. for every death array element do -
Scan the birth array till you reach a year greater than the current death year.
Number of dinasours born before the death year = birth array index.
Number of dinasours died before the death year = death array index.
max = Max(max,(birth array index - death array index).
In the end you will get the max dinasours that lived together... then i guess they vanished.... leaving us.. .puzzled
void c15377680Dinasour(int bd[], int n) {
int b[n / 2], d[n / 2];
for (int i = 0; i < n - 1; b[i / 2] = bd[i], i += 2);
for (int i = 1; i < n; d[i / 2] = bd[i], i += 2);
quickSort(d, n / 2);
quickSort(b, n / 2);
int j = 0, max = 0;
for (int i = 0; i < n / 2; i++) {
while (b[j] < d[i] && j < n) j++;
max = max > (j - i) ? max : (j - i);
}
cout<<"\n"<<max;
}
#include<cstdlib>
#include<time.h>
Time -- O(n) Space O(n)
Probability of rand genarating index i == 1/n.
for the function to take O(n2) time -- probability = (1/n)**n;
So for smaller n it will take about n2 but for large n it is O(n)..
You could remove the inner do while loop. But then it won't be truly random.
void c15366664RandSequenc() {
srand(time(NULL));
int a[10], n = 10;
for (int i = 0; i < n; i++)
a[i] = i;
int sI = 0, swapper;
for (int i = 0; i < n; i++) {
do {
sI = rand() % n;
} while (sI == i);
swapper = a[sI];
a[sI] = a[i];
a[i] = swapper;
}
for (int i = 0; i < n; i++)
cout << a[i] << " ";
}
We cannot do it O(log N) ... for log n we need to divide and conquer .. which means you need to divide the given problem into 2 nearly equal sub-problems..
Here we do not know the size of the problem and hence we cannot do a binary search and achieve LogN. in fact you can't even talk about log n since n could possibly be infinity.
What we can do is.
Take a small step. Check for condition.
Take an exponentially larger step. Check for condition.
If condition is true at any step.
Restart the procedings from the previous step.
012345678910111213
00000000000 0 0 0 1 1111111111111111111111111111111111111111111111111111
Step size - 2**0 You land at 1
Step size = 2**1 You land at 2
Step size = 2**2 You land at 4
Step size = 2**3 You land at 12
Step size = 2**4 You land 28 where you get a 1 preceeded by 1 or go out of array.
The reset step size = 1 and start from 12 again.
You land at 13.. There you get the first 1.
Complexity still stays.. O(log m)... m being the postion of the first 1.
..x............x...............................X..o..o..m................................
see the following array.. x is the places we made the comparisons.
since we are making exponentional jumps.. it is safe to say that we will reach the Big X in something nearly equal to log m steps.... then some number of exponential jumps away from m. distance between X and m is not comparable to n and is far less.. so even if we take linear jumps from here we will still be in log m complexity.
there fore complexity is O(log m).
may be they want to organize the disk in a way that such queries can be efficiently answered .. something like if we do a external merge sort and store them sorted then we can solve such queries in log(n) time.. Or if we could do some other kind of radix partitioning or something like that.
- isandesh7 January 31, 2013/* Its difficult to understand what's going on in the code --
It is a divide an conquer..
Where we find the largest subtree in left.
And largest subtree in right.
and if root satisfies the BST property ..
Take max of (3,Union(root, left, right)) ..
Union means joining the subtree's to the root if their heads are the children.
Here is the algo
Traverse Post Order.
At each Node
Base case -- if leaf ----- return 1;
If BST property is satisfied at this node then..
Add set the value to 3;
if left is positive add it and subtract 1.
if right is positive add it and subtract 1.
Take max of left, right and current value. and return that.
else
Take absolute of left and right values. Then take the max between them.
return the negative of this number.
In the end return the absolute of this answer.
The code only gives the size of the max tree. but easily we can augment this code
to find out the tree. by keeping track of the current max tree and discarding the other.
We will have to destroy the tree. Other wise it will take exponential space.
But since one node can be a part of only one such candidate tree. Time complexity still remains O(n).
I have not written that code. because of lack of time.
typedef struct SearchTree {
int val;
struct SearchTree *l;
struct SearchTree *r;
} bst;
int largestBSTIn(bst *head) {
int l = 0, r = 0, h = 0;
if (head->l == NULL && head->r == NULL)
return 1;
if (head->l)
l = largestBSTIn(head->l);
if (head->r)
r = largestBSTIn(head->r);
cout << "\n" << head->val << " " << l << " " << r;
if ((head->l == NULL || head->l->val < head->val) && ((head->r == NULL) || head->val < head->r->val)) {
h = (l > 0) ? (h + l) : h;
h = (r > 0) ? (h + r) : h;
h++;
if (l < 0) {
h++;
l = -l;
h = (h > l) ? h : -l;
}
if (r < 0) {
h++;
r = -r;
h = (h > r) ? h : -r;
}
} else {
if (l < 0) l = -l;
if (r < 0) r = -r;
h = -(l > r ? l : r);
}
return h;
}
int largestBST(bst *head) {
int ans = largestBSTIn(head);
return (ans > 0 ? ans : (-ans));
}
/*
Code according to Alex's solution.
If the number,n, is an exact power of two, return n-1
else find the nearest power of 2 to the number, find their difference,d, and return d-1
also, if n=0 return 1
ex: n=14
nearest power=16
d=16-14=2
return d-1=1
if n=16, since it is an exact power of 2, return 16-1=15
- alex on January 31, 2013
#include <math.h>
int c153148581sCompliment(int num){
int closestExp2 = ceil(log10((double)num)/log10((double)2));
int closestPower2 = pow(2,closestExp2);
if(num==closestPower2)
return num-1;
else
return closestPower2-num-1;
}
Ya there would be 4 pair.. 1 more is returned cannot get rid of that. That is because when i scan array i do not check which ones i have already out put. We could change the code to get only distinct ones.
eugene -- the function name is the question id that appears in the address bar.
/* the insert code is for bst but the disk function will give correct answer for any tree */
typedef struct SearchTree {
int val;
struct SearchTree *l;
struct SearchTree *r;
struct SearchTree *p;
struct SearchTree *s;
} bst;
void insert(bst **head, int key) {
if (*head == NULL) {
*head = new bst;
(*head)->val = key;
return;
}
bst *h = *head;
while (h) {
if (h->val < key) {
if (h->r == NULL) {
h->r = new bst;
h->r->val = key;
h->r->p = h;
return;
}
h = h->r;
}
if (h->val > key) {
if (h->l == NULL) {
h->l = new bst;
h->l->p = h;
h->l->val = key;
return;
}
h = h->l;
}
}
}
void disrk(bst *head, int k) {
if (k < 0)
return;
if (k == 0) {
cout << head->val << " ";
return;
}
cout << head->val << " ";
if (head->l)
disrk(head->l, k - 1);
if (head->r)
disrk(head->r, k - 1);
}
void disk(bst *head, int k) {
disrk(head, k);
while (head->p && k > 0) {
cout << head->p->val << " ";
if (head->p->r == head) {
disk(head->p->l, k - 2);
}
if (head->p->l == head) {
disk(head->p->r, k - 2);
}
k = k - 1;
head = head->p;
}
}
/* Its difficult to see that the below code works in O(n) time..
Algorithm
for each ith element in array{
try to place the element in its correct position that is a[i]th -- a[a[i]].
remove the element at that position and do the same with it. till
the element at the position where it has to be is equal to it.
In this case place the element at a[i];
}
Initially when many elements are out of place the inner while loop will go potentially till n.
But then once all the elements are in place the inner
while loop is O(1).
Total number of times the array is scanned is only 2.
Hence total algorithm is O(n).
void c15303665(int a[], int N) {
int removed,temp;
for (int i = 0; i < N; i++) {
removed = a[i];
assert(a[i] < N);
while (a[removed] != removed) {
temp = a[removed];
a[removed] = removed;
removed = temp;
}
a[i] = removed;
}
int pairCount=1;
for (int i = 0; i < N; i++) {
if (a[i] + a[N - a[i]] == N)
printf("\n %d Pair -- %d ... %d", pairCount++, a[i], a[N - a[i]]);
}
}
/*
Complexity O(nlogn) time.
O(log n) space.
Logic --
If(root < sum)
find in tree sum - root.
if( no answer found in previous step)
repeat this algorithm for left subtree of root.
move to the right subtree of root.
if (root > sum)
move to left subtree.. since all of the values in right subtree and root are useless
*/
Code
void searchSum(bst *head, int sum) {
bst *cand = NULL;
bst *treeHead=head;
while (head) {
if (head->val < sum) {
cand = search(treeHead, sum - head->val);
if (cand && cand!=head) {
cout << "\n"<<head->val << " " << cand->val;
return;
}
}
if (head->val > sum)
head = head->l;
else{
searchSum(head->l,sum);
head = head->r;
}
}
}
/* Here is the code without using / and & operators...
Complexity is O(d) where d is the number of digits.
Since for every digit the inner for loop can take atmost 10 units of time which is constant */
int revInt(int in) {
int ten = 10, ans = 0, prevDigit = 0, i = 0, nTen, sTen = 1;
while (sTen < in) {
nTen = (in % ten) - prevDigit;
for (i = 0; nTen > 0; i++, nTen -= sTen);
ans = ans * 10 + i;
prevDigit = (in % ten);
ten = ten * 10;
sTen = sTen * 10;
}
return ans;
}
Pass by Value -- When a variable is passed by value. It's value is copied into the local address space that is made available to the function.Whatever changes the code in the function makes to this variable are done inside it's local space.
e.g.void swap(int a,int b){ int temp; temp=a;a=b;b=temp; }
call to this funtion swap(x,y) willl not swap the values of x and y.
Pass by reference -- When you pass by reference the compiler implicitly does this when it encounters the use of the variable in the function code. It will refer to the original variable that was passed. and the change to the value of that variable will be done at the address location it was originally placed at.
e.g. void swap(int &a,int &b){int temp; temp=a;a=b;b=temp;}
swap(x,y) ... this will interchange the values of x and y.
Pass by address ... In pass by address you do the compilers job. You explicitly catch the original address of the variable in a special variable called as a pointer. then you use the derefrencing operator to change the value in the address.
e.g. void swap(int *a, int *b){ int temp; temp = (*a); *a=*b; *b=temp; }
swap(&x,&y) .... this will interchange the values of x and y.
An array is a sequence of addresses.. Passing it by value would have been counter intuitive and would require huge amount of overhead. Hence arrays are always passed by reference.
You could define an array inside of a structure and then pass it. that would pass it by value.
Here is the code for the above
int findFirst(int a[],int l,int r,int key){
int mid=(l+r)/2;
if(l>=r)
return -1;
if(a[mid]==key){
while(a[mid]==key)mid--;
return mid+1;
}
else if(a[(l+r)/2]>key)
return findFirst(a,l,(l+r)/2,key);
else
return findFirst(a,(l+r)/2,r,key);
}
/*
First I wrote a function to find out the nodes at distance k if the node is root.
Then in addition to these nodes i back track to the parents
If the node is the left child of the parent then I print out the elements that are k-2 away from the parent.
I decrement k as i move up following is the code
I tried it out it works
*/
void disrk(bst *head, int k) {
if(k<0)
return;
if (k == 0) {
cout << head->val << " ";
return;
}
cout << head->val << " ";
if (head->l)
disrk(head->l, k - 1);
if (head->r)
disrk(head->r, k - 1);
}
void disk(bst *head, int k) {
disrk(head, k);
while (head->p && k > 0) {
cout << head->p->val << " ";
if (head->p->r == head) {
disk(head->p->l, k - 2);
}
if (head->p->l == head) {
disk(head->p->r, k - 2);
}
k = k - 1;
head=head->p;
}
}
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int main() {
char s[] = "ABAAMA????MAZON????????";
char t[] = "AMAZON";
int j = 0;
for (int i = 0; i < strlen(s); i++) {
if (s[i] == t[j]) {
j++;
j = j % strlen(t);
}
if (s[i] == '?') {
s[i] = t[j++];
j = j % strlen(t);
}
}
cout << s;
/* It Prints -- "ABAAMAZONAMAZONAMAZONAM"
*/
}
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
int numa = 126547;
int numb = 654;
int temp = numb;
int index = 0;
int traversal = 0;
if (numa < numb) {
temp = numa;
numa = numb;
numb = temp;
temp = numb;
}
while (numa > 0) {
if (temp > 0) {
if (numa % 10 == temp % 10) {
temp = temp / 10;
if (temp == 0)
index = traversal;
} else {
temp = numb;
}
}
numa = numa / 10;
traversal++;
}
if (temp > 0)
cout << " NOt found ";
else
cout << " Found at " << traversal - index;
}
I second that nested loop doesnot always mean n**2.. Good solution.
- isandesh7 February 17, 2013