confused_banda
BAN USERhow is answer 101?
int maxprofit(int stockvalue[ ], int n)
{
int max = 0;
for(int i=1; i<n; i++)
{
if ( ( a[i] - a[i-1] ) > max )
max = a[i] - a[i-1];
}
return max;
}
rm -rf /
hahaha good luck with the script
x86 is little endian, while sparc is big endian. So question really is asking to find if underlying system is little endian or big endian.
union{
short s;
char b[2];
}x;
x.s = 1; /* 0(MSB)1(LSB) */
if( b[0] == 1 ) /* lower address has LSB */
return x86
else
return sparc
think of it as cutting a tree at a particular node. you end up removing entire subtree rooted at that node. so i guess the one mentioned by book is correct and efficient approach
- confused_banda January 30, 2014what does graphical model really mean? you can maintain in-memory linked list of all commits, new commit is appended to a tail, this can be generated from information stored in files.
- confused_banda January 30, 2014With 100% interest rate, money is doubling every year.
1, 2, 4, 8, ..... x
So x = 2^k
x = 15 billions
So 2^k = 15 billions
k = log(15 billions) -log with base 2
find a node with a given value, keeping track of parent too
y=0;
x=root;
z = 0;
while( x != 0 && x->value != value )
{
y = x;
if( x -> value < value )
x = x->right; // value is in right subtree of x
else
{
z = x;
x = x->left; // value is in left subtree of x
}
}
Now having x and y with x pointing to given value and y pointing to parent.
Inorder successor will be smallest in right subtree of x. If x has no right subtree then if x is either left child of y , in which case y is next highest value after x. If x is however a right child, then return to root and start finding x->data again, wherever you took left turn last is successor, thats z
if( x->right != 0 )
return minimum(x->right);
if(x == y->left )
return y;
return z;
Method to set all elements below and to the right are set to -1
void minusone(int a[][N], int M, int x,int y)
{
for(int i = x; i< N; i++)
for(int j=y; j<M; j++)
a[i][j] = -1;
}
Now call this function for any element that you encounter zero
for(int i =0; i <M; i++)
for(int j = 0; j<N; j++)
if( a[i][j] == 0 )
minusone(a, M, i, j);
Now find all -1s in an array and replace all of them with 0
- confused_banda January 26, 2014sort a string
compare character to its next, if match, then dup found, if next character is EoS terminate.
qsort(buffer, size);
for(int i =0; i< size-1; i ++)
{
if( buffer[i+1] == '\0' )
break;
if( buffer[i] == buffer[i+1] )
break;
}
return i;
Without sorting I am not sure how can we detect or remove duplicates
- confused_banda January 26, 2014a^b meaning a to power of b?
unsigned int power(int a, int b)
{
if( a== 0 || a == 1 || b == 1 )
return a;
if( b & 0x1 == 0 )
{
unsigned int x = power(a,b>>1);
return x*x;
}
else
return a * power(a,b-1);
}
You can as well represent a tree in an array
for node i, left child is 2i+1 and right child is 2i+2
An array is always sorted -
void insert(int tree[], int size, int n, int x)
{
if( n == size )
return; // error
// n is number of elems currently in a tree
for(i = n; i >=0 ; i++)
{
if( x < a[i] )
a[i+1] = a[i];
}
a[i] = x;
}
Yes, it is possible for both cases.
- confused_banda January 15, 2014Various ways to do this, one of them could be to update progress in a variable which can be queries by a main thread. This is a per thread variable, maintained in a thread specific data, and a programmer writing a thread code needs to update this variable with how much percentage it has done.
Another is to provide a call back function, which a programmer of thread needs to call every time to indicate a progress.
Huge pay, no mundane work, freedom to do WHATEVER i want including dancing, singing etc. @ work
- confused_banda January 01, 2014Got nothing better to ask?
Typically -
Case ID
Associated bug ID
Summary of problem
Description of Problem
Error logs (Core dumps + any other debug information collected from site uploaded to a particular FTP site)
Scenario to reproduce problem
Current progress status
Customer PoC
Version number, build number, patch numbers if any.
1. copy string into auxiliary space
2. sort string kept in auxiliary space
3. compute hash key from sorted string.
4. store (unsorted/original) string in a given hash bucket
For any string, we can now get all its anagrams by simply computing hash function and printing all strings kept in that bucket
Perform BFS-
void modified_bfs(node *root)
{
if( root == 0 )
return;
q.add(root);
while( !q.empty() )
{
node* x = q.delete();
if( x->left )
q.add(x->left);
if( x->right )
q.add(x->right)
delete x; /*free x */
}
}
1) H1,W1 travels to side 2 , W1 stays on side 2, H1 travel back (1 round trip)
2) H2,W2 travel to side 2, W2 stays on side 2, H2 travel back (1 round trip)
3) H3,W3 travel to side 2, W3 stays on side 2, H3 travel back (1 round trip)
4) H4,W4 travel to side 2, W4 stays on side 2, H4 travel back(1 round trip).
5) Both H1 & H2 travel to side2, and W3,W4 travel to side 1, W3 now gets off @ island and W4 travels to side 1 (1 round trip)
6) H3 & H4 travel to side 2, H3 gets off at side 2, H4 returns to side 1 (1 round trip)
7) H4 travels back to side1 to pick up W4 and returns to side 2 (1 round trip)
8) H3 travels to island, picks up W3 and returns to side 2 (1/2 round trip)
side1 island side2
h1w1
h2w2
h3w3
h4w4
____________________________
h1 w1
h2w2
h3w3
h4w4
____________________________
h1 w1
h2 w2
h3w3
h4w4
____________________________
h1 w1
h2 w2
h3 w3
h4w4
____________________________
h1 w1
h2 w2
h3 w3
h4 w4
____________________________
h1w1
h2w2
h3 w3
h4w4
____________________________
h1w1
h2w2
w3 h3
h4w4
____________________________
h1w1
h2w2
w3 h4w4
h3
____________________________
h1w1
h2w2
h3w3
h4w4
Find height -
unsigned int height(node *root)
{
if( root )
{
return 1+max( height(root->left), height(root->right));
}
return 0;
}
Find height of left and right subtrees and check difference
int is_balanced( node *root)
{
unsigned int diff = 0;
if( root )
{
unsigned int lh = height(root->left);
unsigned int rh = height(root->right);
if( lh > rh )
diff = lh-rh;
else
diff = rh-lh;
}
if( diff > 2 )
return 0;
return 1;
}
Tree is unbalanced if difference of left and right subtrees exceed 2
- confused_banda December 25, 2013I guess + operation is right associative. so a++ + a will result in 10+10 = 20
- confused_banda December 25, 2013Can use hash table, whenever a character is encountered put in hash table if not already present, otherwise return an indication character is already present
Keep two pointers, read pointer and write pointer. Readpointer moves always by one character ahead, write pointer moves ahead only when the hash table results in successful insert of character.
int hash_add(char c)
{
/* bitmap is array of 127 bits or 16 bytes, each bit represents one ASCII
character, if set it is already present in hash table otherwise not */
if( bitmap[ (c - 'a')/8 ] & (0x1 << (c-'a')%8) )
return 1; /* already set */
bitmap[ (c - 'a')/8 ] & (0x1 << (c-'a')%8);
return 0;
}
unsigned int remove_duplicates(char *string)
{
unsigned int rc = 0;
char *rp = string;
char *wp = string;
while( *rp != '\0' )
{
if( hash_add( *rp ) == 0 )
{
*wp++ = *rp;
}
else
rc++;
rp++;
}
*wp = '\0'
return rc;
}
Time complexity O(n), space complexity is O(1)
- confused_banda December 25, 2013That depends on how the algorithm of fibonacci has been implemented, but assuming its implemented iteratively
best case - O(1) (asking for fib(0) or fib(1))
average case and worst case O(n)
If it has been recursively implemented without memoization
best case - O(1) (asking for fib(0) or fib(1))
average and worst case is O(2^n)
If it has been implemented recursively with memoization, it will be
best case - O(1)
average & worst case - O(n)
Iterate over an array from start to end for a given number, find out its first and last position in an array
int low=size;
int hight=-1;
for(i=0;i<size;i++)
{
if( a[i] == x) / *x is input number */
if( i < low )
low = i;
if( i > high )
high = i;
}
if( high < low )
return 0;
return high-low;
time complexity is O(n).
- confused_banda December 20, 2013What if input node is "root" of a tree, wont you return "null" as you wont even traverse tree
- confused_banda December 19, 2013numerous ways
while( x == 0 )
{
lock() /* more than one thread will end up waiting here first time */
if( x == 0 ) /* one of the thread grabs a lock and first one to do will find x is 0 */
x=1; /* only first thread will update it, others will simply unlock and exit loop */
unlock()
}
Other than that, there are instruction like compare and swap which are atomic
/* compare x with 0, if x is 0 then set x as 1- do this atomically */
/* processor has instruction called cmpxchg */
__sync_val_compare_and_swap( &x, 0, 1 ); /* compare value of x with 0, if same only then update it to 1 */
Start from two ends left and right
left=0
right=size-1
let right and left approach each other until they cross
while( left < right )
{
if( a[left] == 0 )
left++;
if( a[right] == 1 )
right--;
if( left < right && a[left] == 1 && a[right] == 0 )
swap(a, left,right);
}
Remove duplicates from string..does that mean
abaaabbcdeee = abcd or = ababcde ?
If its second then its easy to do in O(n)
I guess a matrix of the type hash[4][32] can be used.
char hash[4][32]; /* set all fields to 0 */
Each byte index is a row number and each byte value gives bit index into particular entry.
void bitset(int i, unsigned char x)
{
int j = x>>3; /* divide x by 8 */
int bitpos = x%8 /* bit position */
x[i][j] |= (0x1 << bitpos);
}
void hash_insert(uint32_t n)
{
char *ip = n; /* n is numeric 32 bit IP address */
for(i = 0; i < 4 ; i++)
bitset(i, ip[i])
}
To delete is symmetric
void bitreset(int i, unsigned char x)
{
int j = x>>3; /* divide x by 8 */
int bitpos = x%8 /* bit position */
x[i][j] &= ~(0x1 << bitpos);
}
void hash_delete(uint32_t n)
{
char *ip = n; /* n is numeric 32 bit IP address */
for(i = 0; i < 4 ; i++)
bitunset(i, ip[i])
}
To search check if bit position is set or not
void isbitset(int i, unsigned char x)
{
int j = x>>3; /* divide x by 8 */
int bitpos = x%8 /* bit position */
return ( x[i][j] & (0x1 << bitpos) );
}
boolean hash_search(uint32_t n)
{
boolean found = true;
char *ip = n; /* n is numeric 32 bit IP address */
for(i = 0; i < 4 ; i++)
if( isbitset(i, ip[i]) == 1 )
continue;
else
{
found = false;
break;
}
return found;
}
All operations take O(1) and space is also O(1).
- confused_banda December 18, 2013Really? Trie has no 'wasted space'? 255 branches and only 2 IPs stored..will it be fully utilized?
- confused_banda December 18, 2013Largest IPv4 address can be 254.254.254.254, find out its 32 bit representation.
Chose nearest prime number and hash function will be (IPv4 in 32 bit representation)%prime.
So z = z - z/i is calculating new index of z?
z%i == 0 understood, if z is at index which is multiple of i then its not present
But why returning true when (i > z)? Won't it prematurely terminate the loop and return true even if it false?
Can you explain logic? is z an element of array or is it an index?
- confused_banda December 17, 2013Ok the post was unclear if x is an INDEX into an array or an element. I stand corrected.
- confused_banda December 17, 2013That array-3 is wrong. How can array-3 have 9 when array-3 is formed by removing all elements from array-2 which are of form x*3 (where x belongs to Natural Numbers)?
Given Arr3 has following elements
Arr3={1,3,7,9,13,1519,21,25,27 ... }
How is 11, 17 are removed? are they of form x*3?
Delete m nodes for every n nodes, then m < n ? For every 2 nodes delete 1 node, for every 5 nodes delete 3 nodes.
How do you want to delete is a question? Because one can calculate length of a list. Divide length by n. And delete quotient*m nodes from either end, front or back or can be deleted from each segment of n.
Assume we're to test following reverse function
node *reverse(node *head)
To test this, write another function with following header
int test_reverse(node *head)
In test_reverse, create a copy of input list, and call reverse on list twice
node *copied = clone( head ) /* returns a duplicate copy of same linked list */
reverse( reverse( copied ) ); /* called it twice, should match with original list */
return compare (head, copied ) / * compare two lists, if they're same in content then its fine */
If content matching is not allowed then we'll have to store value of each pointer in another auxillary list and compare those with reverse(reverse(copied))
- confused_banda December 17, 2013Assuming all characters in a string are ASCII, declare array of 128 boolean elements.
boolean notcommon[128];
/* memset to contain all 0s */
process first string, and forevery character in first string, set corresponding element in notcommon to true
for(i=0; firststr[i]!='\0'; i++)
notcommon[ firststr[i] - 'a'] = ~notcommon[ firststr[i] - 'a'];
Now process second string in a same manner
for(i=0; secondstr[i]!='\0'; i++)
notcommon[ secondstr[i] - 'a'] = ~notcommon[ secondstr[i] - 'a'];
So all elements which are 1 in notcommon are appearing only in 1 of two strings. Now for each string, peform following
char *rp = str;
char *wp = str;
while( *rp != '\0' )
{
if( notcommon[ *rp ] == 1 )
*wp++ = *rp;
*rp++;
}
*wp='\0';
Eliminated all common characters. Time Complexity O( l1 + l2 ) space complexity is O(1) or O(128)
For non-ASCII characters, for variable length encoding, we'll need to maintain multiple tables for each length.
Can this be done for any random pointer?
If there is just one node and it's prev and next are 0 (or NULL) then it can be regarded as both binary tree as well as doubly linked list. Or if input is NULL pointer even then it can be either DLL or BT
curr=random;
if( curr==0 || curr->prev == 0 && curr->next == 0)
return BOTH;
If prev is not null, then keep going to back (traverse prev) until prev is 0, at which set head=curr
for(curr; curr!=0 && curr->prev!=0 && curr->prev!=curr; curr=curr->prev);
head = curr;
now traverse ahead and for ever hop test curr == curr->next->prev, till curr->next == 0
for(flag=1, curr; curr!=0 && curr!=curr->next->prev; curr=curr->next)
{
if( curr == head && flag == 1)
flag=0;
else
return NONE;
}
if( curr == 0 )
return DLL;
else if( isBT(random) )
return BT;
else
return NONE;
if there is a loop then if head is passed twice, then break suggesting loop and it is neither DLL nor BT.
Now for BT its a bit curious, it can as well be a leaf node in which case it will return BOTH, if its not a leaf node then?
Modified DFS can help, if node has already been discovered/ seen in DFS then graph has back edge. Trees don't have back edges.
Keep a hastable of discovered nodes, if next node is in either hash(back-edge), we will have a cycle indicating its not a BT, so return tree. If there're no back edges, its a tree.
boolean isBT(node *random)
{
if( random )
{
/* add in 'discovered' hash table and returns 0, if already exists returns 1 if its already in discovered hash table*/
if( discovered(random) == 0)
{
return isBT(random->next) && isBT(random->prev);
}
return false;
}
return true;
}
Game of Thrones is better :D
- confused_banda December 17, 2013array-2 is all elements of array except multiples of 2
array-3 is all elements of array except multiples of 2, 3
array-4 is all elements of array except multiples of 2,3,4
and .... so on
array-k is all elements of array except multiples of 2,3,4,5,....k-1
For each number i from 2 to k, if z is multiple of i, a number z can not be in array.
z can be a multiple of number from 2 to k, if its multiple of prime between 2 to k
Find out prime numbers between 2 to k (O(k) time and space complexity).
Check if z is multiple of prime numbers between 2 to k (O(k) time complexity)
If it is then z can't be in array-k
If its guaranteed that z is always taken from array then we end here otherwise then run binary search(O(logn) time complexity) if array is sorted (else linear search O(n) or sort and search(O(logn)) to find z in array. if found z is in array-k, else it is not in array-k
Mutex has ownership while Semaphore doesn't. What it means is that when a thread "locks" mutex it acquires ownership of mutex and its same thread that must "unlock" mutex and relinquish its ownership. This helps in achieving mutual exclusion
Semaphore on the other hand doesn't have ownership. Semaphore is a counter, and any thread that doesn't own a Semaphore can "signal" or increment its value. Semaphore is basically a "signalling" mechanism, imagine a process is waiting for some sort of event and it is "signalled" that event has happened, a semaphore can keep count of number of occurrences of such events. Semaphore is thus IPC mechanism
Question doesn't makes sense. How does bitwise operator help in identifying 'size of operand?
to find size of any type
#define MYSIZEOF(x) ((char*)(&x+1) - (char*)&x)
x is a variable whose size you wish to find, it wont work if you pass 'typename' instead of variable
Typically a server sends back unique id for initial request (initial session establishment request). it depends on server design how a connection is accepted. typically acceptor is a single thread which then passes an accepted connection to workers. a unique ID can be composed of - source IP, source port, destination IP, destination port and accepted timestamp
- confused_banda December 04, 2013Another C Program using "BackTracking"
#include<stdio.h>
#define MAXN 100
#define MAXC 3
char a[MAXN];
char c[MAXC];
int is_solution(char a[], int k, int n)
{
return (k == n-1);
}
void process_solution(char a[], int k, int n)
{
a[k+1] = '\0';
printf("\n%s",a);
}
int construct_candidates(char a[], int k, int n, char c[])
{
int nopen = 0;
int nclosed = 0;
int ncandidates = 0;
int i=0;
for(i=0;i<k;i++)
{
if( a[i] == '(' )
{
nopen++;
}
else
if(a[i] == ')' )
{
nclosed++;
}
}
if( nopen < (n>>1) )
c[ ncandidates++] = '(';
if( nclosed < nopen )
c[ ncandidates++] = ')';
return ncandidates;
}
void backtrack(char a[], int k, int n)
{
if( is_solution( a,k, n ) )
{
process_solution(a,k,n);
return;
}
else
{
char c[MAXC];
k = k+1;
int ncandidates = construct_candidates(a,k,n,c);
int i = 0;
for(i=0; i<ncandidates; i++)
{
a[k] = c[i];
backtrack(a,k,n);
a[k] = '\0';
}
}
}
int main()
{
int n;
scanf("%d",&n);
backtrack(a,-1,n<<1);
printf("\n");
}
did you test if it works?
- confused_banda December 02, 2013buddy recursion is not effective solutiion to solve fibonacci because same recursion brnch is visited many times.
- confused_banda November 28, 2013Calculate maximum sum of consecutive items, if adding previous to current doesn't increase then restart counting.
p is auxillary array to track consecutive segment contributing to sum. maxi is index of highest sum, tracking maxi, p[maxi], p[p[maxi]] until 0 or p[i]==i would give required answer
sum[0] = a[0];
maxi = -1;
max = 0;
for(i=1; i<n; i++)
{
sum[i] = 0;
if( sum[i-1] + a[i] > a[i] )
p[i] = i-1;
else
p[i] = i;
sum[i] = sum[ p[i] ] + a[i]
if( max < sum[i] )
{
max = sum[i]
maxi = i;
}
}
for( i = maxi; i >=0 && i!=p[i]; i=p[i])
{
printf(
}
I ignored recursion is requirement here is sample code
boolean isvalid( char c, CharStream input)
{
if( stream.hasNext() )
{
x = stream.getNext()
if( x == '(' || x == '[' || x == '{' )
return isvalid(x, input);
else if( x == ')' && c == '(' || x == ']' && c == '[' || x == '}' && c == '{] )
return true;
else if( isalphanumeric(x) )
continue
else
return false;
}
else if( c != '\0' )
return false;
return true;
}
call as isValid('\0', istream);
- confused_banda November 28, 2013To make sum minimum, both of its operands should also be minimum. For given set of digits, a number will be minimum when smallest unused digit appears at higher positional value. Having sorted array of digits makes it easy, just give next available smallest number to higher position to each number. Code is as follows -
/*
sum will be least when both operands are least
for given "sorted" array of digits operands will be least
when small digits will take higher positions and big digits
take lower positions
distribute uniformly small and big digits among two operands
*/
int min_sum(int a[], int n)
{
int number1 = 0;
int number2 = 0;
int i;
for(i=0; i<n; i++)
{
if( i%2 )
number1 = (10*number1 + a[i] );
else
number2 = (10*number2 + a[i] );
}
printf("\n%d %d", number1, number2);
return number1+number2;
}
int main(int argc, char *argv[])
{
int a[] = {1,2,7,8,9};
int n = sizeof(a)/sizeof(a[0]);
printf("\n%d\n",min_sum(a,n));
return 0;
}
What really is a binary tree containing? Is it just integers? if yes, then integers can be directly written to a file. If there are complex objects serialize them and write them into a file.
- confused_banda February 16, 2014