CareerCup

Sorry, it was right shift, I have changed this. Shalini can you please elaborate through code. Thanks!

Yes, we will have to free it manually when we are done with it.

Its simple.. free (p) will do the job

Use Radix sort.

No.

@devesh
Do you always follow syntax? There is a thing called logic. Btw you can modify the function internally.

Could you please explain about this, probably logic ?

Push elements in stack in inorder.
Then pop each element and assign its successor. Complexity O(n);

Stack stack

Inorder (node *root)
{
if (root == NULL)
return;

Inorder (root->left);

stack.push (root);

Inorder (root->right);
}

node *p1=NULL, *p2=NULL;

while (!stack.empty) {
p2 = stack.pop;
p2->next = p1;
p1 = p2;
}

The subarray should be "15 1 11 -15 18" not "15 1 11".

Pseudo code

sum = 0, max = 0, start, end
a = 1,

for i = 1 to N
{
sum = sum + arr[i];

if (sum > max) {
max = sum;
end = i;
start = a;
}
if (sum < 0) {
a = i+1;
sum = 0;
}
}

The maximum sum subarray would be from arr[start] to arr[end]

Do BFS from start node and find the nodes which has distance K, print them.

The other solution:

Distance (Node *node, dist, k, Node *parent, Node *child) {

if (node == NULL)
return;

if (dist == k) {
print (node->data);
return;
}
// Passing parent and child to avoid the same node to be visited again.
if (node->left != child)
Distance (node->left, dist+1, k, node, NULL);

if (node->parent != parent)
Distance (node->parent, dist+1, k, NULL, node);

if (node->right != child)
Distance (node->right, dist+1, k, node, NULL);
}

main () {
Distance (Node *node, 0,k, NULL, NULL);
}

I was asked the same question. Write a recursive program to compute the number of paths from top left to bottom right.

I couldn't write that time but later I tried at home and did it.

Here is the pseudo code:

int Number_of_Paths (node *head)
{
if (!head)
return 0;

if (head->right && head->down)
return ( Number_of_Paths(head->right) + Number_of_Paths(head->down));
else if (head->right)
return Number_of_Paths (head->right);
else if (head->down)
return Number_of_Paths (head->down);
else
return 1;
}

This looks like a good solution. nCr could be written as nCn-r.
So (m+n-2)C (n-1) could also be written as (m+n-2)C(m-1).
So it could be vice versa

Approach would be right if string length is even. It wouldn't work for string which is of odd length.

what about 3x3 grid ? Answer should be 12 according to you but its 6.

elegant solution

Do ps -AL | grep pid
1st column is parent id and the second column is thread (LWP) id. if both are same then its a process id otherwise thread.

when dynamic allocated memory is not freed after its use. This result in the memory leak.

To implement integer array of size array_size
int *p = (int *) malloc (sizeof(int) * array_size);

now you can assign values using p[i] = something // i =0 to array_size-1
and and access them using same;

yeah.. looks like a good solution.

How ?

reverse the whole string
then reverse by words.

reverse (str);

while (*str != '\0') {
start = str;

while (*str != ' ' && *str != '\0')
{
str++;
}
end = str-1;

while (start < end)
{
char c; // to swap characters
c = *start;
*start = *end;
*end = c;
start++;
end--;
}
if (*str != '\0')
str++;
}

This one is classy problem :
classic-puzzles.blogspot.in/2006/12/google-interview-puzzle-2-egg-problem.html

pick any 6 balls divide them into 3 each.
if they are same check the rest two and you will find the heavier.
if they are not same then choose 3 from heavier bowl and pick any two and weigh them, if they are same third one is heavier otherwise its clear.

so you have to weigh only two times.

const char *p, char * const p
first is constant character pointer, the value pointed by p is constant.
second one is a constant pointer to character, where the value of p (address) is constant.

Yes if it is not a waited graph. It can be done by slightly modifying BFS algorithm.

for u , v E all edges connected to u. // just a reference from bfs algo
if v is already marked gray and check if d (v) == d(u) + 1, increment number of shortest paths to v by 1
otherwise if v is white set number of shortest path to 1, d(v) = d(u) +1.

You can also modify dijkstra's Algorithm but complexity would increase (in case of weighted graph).

Use BFS to find strongly connected components in undirected graph return the largest one.
O(|V| + |E|)

Using expected value of first 100 outcomes. black 90 white 10.
remains 810 black and 90 white. so probability would still be 9/10

there are two cases in which india win:
1) Akbar tells the truth and Amar tells the truth : 3/4*3/4 = 9/16
2) Akbar tells a lie that India loose and Amar tells lie to anthony that "Akbar told me india win" : 1/4*1/4 = 1/16

So total probability of winning India would be 9/16 + 1/16 = 10/16

Correct me if I am wrong.

The code is correct and produces right output.
What is the problem in using global variable ? or you are unfamiliar with them ?

This means that each node will contain its data + sum of all node's data in right subtree.
node->data = node->data + (sum of all nodes in right subtree).
Reverse Inorder would do the work for us.

Code:
int sum = 0; //global variable
sum_max (node *root)
{
if (root == NULL)
return;

sum_max (root->right);
sum = sum + root->data;
root->data = sum;
sum_max (root->left);
}

Algo:
for each character in string
if its a left part i.e. (,{,[ Push in stack
else if its a right part pop from stack and match whether is appropriate left part of parenthesis.
any case doesn't match return FALSE.

return TRUE.

Answer is C. (if its a 16 bit integer)

Negative numbers are stored as 2's compliment . Assuming 32 bit integer answer would be
fffffff0.

1. get to middle element of string.
2. take two pointers p1 and p2 point to middle element(if string is of odd length, or two different middle elements incase of even length).
3. while (p1 >= start, p2 <= end)
{
if (*p1 !=*p2)
return FALSE;
p1--;
p2++;
}
return true;

nice

warning : overflow. random output

Algo.
1. find the longest palindrome in string.
2. repeat the procedure for remaining two strings (left and right side of palindrome).

Assume it has all distinct characters.
total number of permutations : n!
Algo:
start from first character and traverse till end. find how many characters are ranked before this, suppose this is x, now we know there are x * (n-1)! permutations are ranked above this.
Repeat the procedure for every character in string.

int n = strlen(str);
int rank = 0;
for (i = 0; i < n-1; i++) {
int x=0;
for (j = i+1; j<n ; j++) {
if (str[i] > str[j])
x++;
}
rank = rank+ x*((n-i-1)!)
}

return rank;

Use randomize selection to find the 2nd largest element i.e. element at N-1 th position.

solution 2.
int max1, max2 = 0;
for i = 1 to N
if (A[i] > max2)
max2 = A[i]
if (max2 > max1)
swap (max1, max2)

return max2

Hashing would be best approach for O(n).
n = length of array.
Before inserting each element to hash table look for if found n-- otherwise insert to table.
return n

What about hashing ?
Before insertion check whether it is present before Inserting if no insert it with value 1 and if yes then increment the value with 1.

Is it to find the zeros in binary format?
If yes then:

count = 0
while (n>0) {
count = count + !(n&1)
n=n>>1 //Right shift by 1
}
return count

To find in decimal format the

count = 0
while (n>0) {
count = count + (n%10>0 ? 0 : 1)
n = n/10;
}
return count

Algorithm for problem
j=1
for i = 1 to N
if (A[i] > 0)
A[j] = A[i]
j++

for i = j to N
a[i] = 0

This takes O(n) without using any buffer