fabregas
BAN USERA more logical solution. Assuming available instructions :
MOVE F ( move forward)
MOVE B ( move backward)
IF(P) (condition satisfied if any of the two starting points reached there is no THEN to this)
code:
A:MOVE F
IF(P)
GOTO B
GOTO A
.
.
.
B: MOVE F
GOTO B
both robots run the same code concurrently. First MOVE F moves both the robots in forward direction(same) i.e. get them off their starting points. Thus both of these robots are stuck in the A loop until one of the robot reaches the starting point of the robot moving in front of it. Only this robots' IF(P) condition gets satisfied and it moves into the B loop which is again making it move forward.
Now both the robots are moving in forward direction but one is in loop A and one is in loop B and we see that it takes a lil more time to execute loop A iteration coz of executing the extra condition in A than it is the case in B. Thus they will meet eventually due to some time difference in executing each of the two loops' iterations.
A variation of this problem is given in How to Ace the Brainteaser Interview Question book.
a O(n^2) solution
int palindrome(int a[], int n)
{
int LongestSoFar = 0, start, end, count=0,lstart,lend;
for(int i=0;i<n;i++)
{
if(count>LongestSoFar)
{
LongestSoFar = count;
lstart = start;
lend = end;
}
count = 0;
for(int p = i,q=i;p>=0&&q<n;p--,q++)
{
if(a[p]!=a[q])
break;
else
{
count++;
start = p;
end = q;
}
}
}
for(i=lstart;l<=end;l++)
count<<a[i];
retun count;
}
similar to longest increasing subsequence problem but here ordered not by the order of elements in sequence but ordered by the volume instead.
1. sort all boxes in decreasing order in volume.
v1 > v2 > v3 > .......... vn
2. now create subproblem h[j] = max no of boxes that i can fit into one another s.t. jth box goes the most inside. thus,
h(j) = max(h(i)) where i<j and width(i) > width(j);depth(i)>depth(j);height(i)>height(j) (strictly)
3. find max(h(j)) for j in [1...n]
pseudocode:
box[1...n]: array containing boxes
h[1...n] : array to store subprob solns
h[1] = 1;
qsort(box,1,n)
for(j=2;j<=n;j++)
{
h[j]=0;
for(i=j-1;i>=1;i--)
{
max = 0;
if(box[i].w > box[j].w && .... && ... && h(i) > max)
max = h(i);
}
}
for all j in 1 to n find max(h(j)) which is the soln
#include <iostream>
#include <sstream>
#include <stack>
using namespace std;
int DEBUG = 1;
//
// Note that if s->size() becomes 0, then left = start.
// This is useful when entry in hist[] can be zero.
// If all entries in hist[] are positive, then no need to use start,
// In that case, use -1 in place of start in this function.
//
void getMax(int hist[], stack<int> * s,
int newHeight, int right, int & max, int & start)
{
int height, left = 0, area;
while (s->size() > 0 && hist[s->top()] > newHeight)
{
height = hist[s->top()];
s->pop();
left = (s->size() > 0) ? s->top() : start;
while (s->size() > 0 && hist[s->top()] == height)
{
s->pop();
left = (s->size() > 0) ? s->top() : start;
}
area = height * (right - left);
if (DEBUG) cout<<"\narea: "<<height<<"*("<<right<<"-"<<left<<") = " <<area;
if (area > max) max = area;
}
}
//
// Note that when hist[i] == top_v, we push i.
// In the acm judge site, it says skip i if equal.
// But I feel somehow it can't keep track of the left value
// when multiple columns have the same height.
//
int doHist(int hist[], int len)
{
stack<int> * s = new stack<int>;
int i, max, top_v;
int start = -1; // the position before the last 0, used by left.
max = 0;
for (i = 0; i < len; i ++)
{
if (s->size() == 0)
{
s->push(i);
continue;
}
top_v = hist[s->top()];
if (hist[i] >= top_v)
{
s->push(i);
}
else if (hist[i] < top_v)
{
getMax(hist, s, hist[i], i - 1, max, start);
s->push(i);
if (hist[i] == 0) start = i - 1;
}
}
getMax(hist, s, 0, i - 1 , max, start);
cout << "\nmax = " << max << endl;
return max;
}
int main()
{
//int hist[] = {3, 5, 4, 7, 6, 5, 2}; // answer: 20
int hist[] = {1,2,1};
doHist(hist, sizeof(hist) / sizeof(int));
return 0;
}
for every i do
1. if stack empty then push i i.e. create subpoblem
2. if hist[i] >= top element in stack, push(i) i.e. create subproblem
3. if hist[t] < top element in stack,
a. solve all subproblems existing in stack and popping them off until the top most element in stack is less than the current hist[i]
b. push i, i.e. create subproblem
now solve the remaining subproblems in stack by sending an element of height 0 and width i-1
yes..this looks better
we can maintain a singly linked list with head and tail pointers containing coordinates in the nodes with new coordinates added at the head and deleted at the node. but first we need to create a 2d array of the map specifying special values indicators of food,wall,free,collision condition
1. food - add a new node at the head with food coordinates (length of the snake increases)
2. wall - hit wall, break out
3. free - add node at the head with free coordinates and hence updating the free coordinate status to collision and also delete the node at tail and hence updating the tail coordinate status to free ( length of the snake remains same)
4. collision - signifying that the current coordinate is in the cirrent list and hence collision of snake to itself. break out
so we start creating a list by adding a free coordinate at start into the linked list and wait for user next direction. we check the next coordinate from the map status and hence updata the list or map accordingly.
1. Use an array representation of 1..100
2. each a[i] contains value (i+1) if no snake or ladder is there
a[i] contains the value > i and the value pointed by the ladder; if a[i] has a ladder starting
a[i] contains value < i; if a[i] is a snake mouth
3. Create the above array depending on the board structure.
4. Generate two random numbers MOD 100 and use them to take a chance
rootToLeaf(nodeptr root)
{
int path[1000];
rootToLeafPath(root,path,0);
}
rootToLeafPath(nodept root,int path[],int pathlen)
{
if(!root) return;
path[pathlen++]=root->data;
if(!root->left && !root->right) //leaf
{
printarray(path,pathlen);
return;
}
else
{
rootToLeafPath(root->left,path,pathlen);
rootToLeafPath(root->right,path,pathlen);
}
}
printarray(int path[],int pathlen)
{
for(int i=0;i<=pathlen;i++)
cout<<root->data;
}
similar to box stacking dynamic programming problem:
1. sort the boxes in decreasing order of their volumes. this defines the order of the sequence that the subsequence shall abide to while finding out the largest subsequence
2. instead of the constraint that the subsequence should be strictly increasing as in the case of longest increas(ing subsequence problem we have here constaint that the current box to be stacked inside the previous subsequence shall be stricly less in each of the three dimensions.
3. if i define,
H(j): the max no of boxes i can put inside each other s.t. jth box is the one that is the most inside(that is the last element of the subsequence as in the LCS problem)
H(j) = max(H(i) for all i<j s.t. h(i)>h(j);w(i)>w(j);d(i)>d(j)) + 1 ( for the jth box)
thus after builing the H[] we find max(H(j) for all j) which is the answer.
order (O(n^2))
1. count the no. of nodes in the btree (len)
int ht(nodeptr p)
{
if(!p) return 0;
else return( ht(p->left)+ht(p->right)+1);
}
2. prob is to find len/2th node if (len=even) or len/2th and len/2 + 1 th node and hence to find their avg. which is the median
3. Finfing k-th smallest node in a binary search tree
1.maintain no of left sub tree elements in each node.
2.if k=n+1 , then root is the kth node
3.if k<n, search for kth node in root->left
4.if k>n+1, search for k-n-1 th node in root->right
2d array:
1. using 2 malloc
int **p = (int**)malloc(sizeof(int*) * ROWS);
for(int i = 0;i<ROWS; i++)
p[i] = (int*)malloc(sizeof(int) * COLS);
p[i][j] = p[i][j]
2. using 1 malloc
int *p = (int*)malloc(sizeof(int) * ROWS * COLS);
p[i][j] = *(p+i*COL+j);
for 3d array:
int ***p = (int***)malloc(sizeof(int**) * SET);
for(int i=0;i<SET;i++)
{
p[i] = (int**)malloc(sizeof(int*) * ROWS);
for(int j=0;j<ROWS;j++)
p[i][j] = (int*)malloc(sizeof(int) * COL);
}
we have to basically minimize the no. of throws so that we are able to cover the entire building that is 100 floors...
1.I throw from floor x, and it breaks hence I need to check all the x-1 floors (linearly) for the second egg to break .. i.e. if I start at x then I need x throws at least ( and we are minimizing x)
2. now observe that if I throw at x I cover x floors at first then x-1 floors then x-2 and so on... we have to minimize x such that the some of each spans reaches 100
e.g.
for x = 16
drop at 16, now have 15 drops for 1-15 (now drops left =15 (16-1))
drop at 31, now have 14 drops for 32-44 (now drops left =14(16-2))
.
.
.
.
i.e. at each step I span x + x-1 + x-2 + ...... until the sum reaches 100
in the optimal soln I should have just one drop left in the end and also just one floor to check ...
i.e. x + x-1 + x-2 + .... + 1 >=100
solving for x(min) gives 14 (ans)
i.e.
thow at 14, 28, . ... , 99, 100
a better solution:
bool isthisBST(nodeptr root)
{
return isthisBSTUtil(root,INT_MIN, INT_MAX);
}
int isthisBSTUtil(nodeptr root, int min, int max)
{
if(root == NULL) return true; //empty tree is a bst
if(root-data < min || root->data >max) return false;
return (isthisBSTUtil(root->left, min, root->data) || isthis BSTUtil(root->right,root->data, max);
}
NOte: we call isthisBST(root,INT_MIN,INT_MAX);
- fabregas March 04, 2011suppose its a 900 mb file and our ram is 100 mb... i.e. 9 blocks
1. bring each block in ram and sort (O(nlogn)) and then put back
2. now we have 9 consecutively sorted blocks.
3. maintain an input buffer of 90 mb and output of 10mb
4. get 10 mb each from start of each block i.e. toal 90mb in input buffer.
5. perform 9-way merge into 10mb output buffer.
6. whenever o/p buffer is filled, write it to disk and erase from ram
7. whenver either of 9 chunks are all read, copy futer 10 mb from the corresponding 100mb block until it exhausts the 100mb
8. do this until all chunks are processed.
source:wiki
#include<stdlib.h>
#include<stdio.h>
#define SIZE 16
int main()
{
int arr[SIZE]={1,0,0,2,0,3,0,0,4,5,6,7,0,0,8};
int i=0,j=0;
printf("\nInitial Array: ");
for(i=0;i<(SIZE-1);i++)printf(" %d",arr[i]);
for (i=1;i<(SIZE-1);i++)
if(arr[i]!=0)
{
arr[++j]=arr[i];
arr[i]=0;
}
printf("\nFinal Array: ");
for(i=0;i<(SIZE-1);i++)printf(" %d",arr[i]);
system("pause");
}
you dont need to waste o(n) space. square the array itself in time o(n) and then the problem reduces to finding pairs summing to a value in the same array.
1. sort the new array o(nlogn)
for all i in n
j from 1 to i and k from i-1 to 0 at the same time
if a[k]+a[j]=a[i] bingo shift both indexes
inc j if a[j]+a[k]<a[i] else
dec k if a[j]+a[k]>a[i]
inner loop - o(i) and i from 0-n
again this is o(n^2)
its more like maintaining a weight balanced tree but not rebalancing it as it is required to do so in weight balanced tree.
pseudo code would be:
typedef struct node
{
char* str;
int freq;
struct node *left,*right;
}mynode;
typedef mynode* nodeptr;
insert(char*str,nodeptr *tree)
{
nodeptr p=*tree;
nodeptr backp = Null;
int i;
//1.search if already in tree
while(p!=Null)
{
if((i=strcmp(str,p))==0)//found
{
p->freq+=1;
return p;
}
else //not this node
{
if(i<0)
{
backp = p;
p=p->left;
}
else
{
backp = p;
p=p->right;
}
}
}
//if not found add a new node
nodeptr q = newnode(str);
q->left=q->right=null;
q->freq=0;
if(strcmp(backp->str,str)>0)
backp->left = q;
else
backp->right = q;
}
//the string needs to be tokenized first
int main()
{
char *lstr = "This is a long string";
char *p;
p=strtok(lstr," ");
if(p!=null)
{
do
{
p=strtok(null," ");
if(p==null)
break;
else
insert(p);
}while(1);
}
}
using 1 malloc
- fabregas March 12, 20111. int (*arr)[COL] = malloc(ROWS * sizeof(*arr));
2. int (*arr)[ROWS][COL]=malloc(sizeof(*arr));