gdg
BAN USER 1of 3 votes
AnswersWhats the time complexity of this code?
When I told him its O(N^3), he told me to look carefully, its O(N^2),
I dont know why? Any idea?for (int i = 0; i < n2; ++i) { //some code for (int j = i+1; j < n1; ++j) { //some code for (int k = j+1; k < n; ++k) { //some code } }
}
 gdg in United States Report Duplicate  Flag  PURGE
Microsoft  4of 8 votes
AnswersGiven an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and viceversa maintaining the order of appearance.
Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.*
Example:Input: arr[] = {1, 2, 3, 4, 1, 4} Output: arr[] = {4, 1, 1, 2, 3, 4} Input: arr[] = {5, 2, 5, 2, 4, 7, 1, 8, 0, 8} output: arr[] = {5, 5, 2, 2, 8, 4, 7, 1, 8, 0}
Limitations:
 gdg in United States
a) Use O(1) extra space
b) Time Complexity should be O(N)
c) Maintain the order of appearance of elements as in original array. Report Duplicate  Flag  PURGE
Google  0of 0 votes
Answerswhile(scanf("%d,",&a)) { //store a as you wish to }
Input given is : 1,2,3,4,5,6,7,8,9
while(scanf("(%d,%d),",&a,&b)) { //store a and b as you wish to
}
 gdg in United States
Input given is : (1,5),(8,11),(3,6),(10,20)
EXPLAIN INTERNAL WHOLE MECHANISM IN BOTH CASES Report Duplicate  Flag  PURGE
Yahoo  1of 1 vote
AnswersGiven a binary tree, change the value in each node to sum of all the values in the nodes on the left side of the node.
 gdg in United States
Eg 1
/ \
2 3
3
/ \
2 6
solved this question using int* he asked me to do it without integer pointer. Report Duplicate  Flag  PURGE
Yahoo  0of 0 votes
AnswerYou are given a mxn grid arr[][] and you stand at cell arr[p][q]. In 1 'move' you can either go up, down , left or right. Tell the probability that after taking 'k' moves, you are still inside the grid.
CODE:
(Can you point out any mistake)
 gdg in United States#include <stdio.h> #include <stdlib.h> void traverse(int m, int n,int cur_x,int cur_y,int moves,int * in,int * tot) { if(moves==0) *tot = *tot+1; if(moves==0 && !(cur_x>=mcur_y>=ncur_x<0cur_y<0)) *in = *in +1; traverse(m,n,cur_x,cur_y+1,moves1,in,tot); traverse(m,n,cur_x+1,cur_y,moves1,in,tot); traverse(m,n,cur_x,cur_y1,moves1,in,tot); traverse(m,n,cur_x1,cur_y,moves1,in,tot); } int main() { int m = 5, n = 5; int in=0,tot=0; int k,p,q; scanf("%d%d%d",&k,&p,&q); traverse(m,n,p,q,k,&in,&tot); printf("%d/%d ",in,tot); return 0; }
 Report Duplicate  Flag  PURGE
Yahoo  1of 1 vote
AnswersGiven 2 set of arrays of size N(sorted +ve integers ) find the median of the resultant array of size 2N.
 gdg in United States
(dont even think of sorting the two arrays in a third array , though u can sort them. Try something better than order NLogN Report Duplicate  Flag  PURGE
Google  1of 1 vote
AnswerWhy is returning pointer to a node in linked list from a pointer is unsafe and sometimes gives wrong answers.
 gdg in United States Report Duplicate  Flag  PURGE
Accenture  0of 0 votes
AnswersMost efficient way to check whether a number is Prime or not.
 gdg in United States Report Duplicate  Flag  PURGE
Akamai  0of 0 votes
Answersstruct node { int data; struct node* left; struct node* right; }; void Postorder(struct node* root,struct node** leaf) { if (root == NULL) return; if(root>data%2==0) *leaf>left=root; //WHY I'M GETTING PROBLEM IN THIS LINE //[Error] request for member 'left' in '* leaf', which is of nonclass type 'node*' Postorder(root>left,leaf); Postorder(root>right,leaf); } int main() { struct node *root = newNode(1); root>left = newNode(2); root>right = newNode(3); struct node* leaf=root; Postorder(root,&leaf); getchar(); return 0;
}
 gdg in United States Report Duplicate  Flag  PURGE
Akamai  1of 1 vote
Answersprint all the binary values of number from 1 to n , each number’s binary should be printed in 0(1).
 gdg in India
for eg: n = 6
then print 1 10 11 100 101 110. printing 1, 10 ,11 ,100,101,110 should be in o(1) each Report Duplicate  Flag  PURGE
Morgan Stanley Sales Development Representative  1of 1 vote
Answers. If a/b is recurring like 10/3, print 10/3 as 3.(3), 16/6 as 2.(6), 3227/555 as 5.8(144)
 gdg in United States Report Duplicate  Flag  PURGE
 0of 0 votes
AnswersSherlock rolls a N faced die M times. He adds all the numbers he gets on all throws. What is the probability that he has a sum of K.
 gdg in United States
A N faced die has all numbers from 1 to N written on it and each has equal probability of arriving when dice is thrown.
2
1 5 2
2 3 2
For first testcase, sum=1,2,3,4,5 are all equally probable. Hence probability is 0.2.
For second testcase:
(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) are all possible ways.
Out of these 1 has sum 2. So 1/9 is the answer. Report Duplicate  Flag  PURGE
 2of 2 votes
AnswersI was asked to design an application that sends a message to two friends if they come within two miles of each other.
 gdg in India
I gave him a solution indicating the data structures used to maintain the friend list and model of the solution .
He pointed out the cons of the solution and I modified the data structure Report Duplicate  Flag  PURGE
Microsoft  0of 0 votes
AnswersI was asked to design an application that sends a message to two friends if they come within two miles of each other.
 gdg in India
I gave him a solution indicating the data structures used to maintain the friend list and model of the solution . Report Duplicate  Flag  PURGE
Microsoft  2of 2 votes
AnswersA quadra tree is a tree where each node has atmost 4 child nodes(similar to a binary tree which has atmost 2 child nodes).
 gdg in India
A monitor screen (black and white) is represented by a qudra tree in the following way:
case 1: If the entire screen is white then the value in the root node is white.
similarly if the entire screen is black then the root stores black.
case 2: If the screen is neither completely black nor white then the screen is divided into 4 quadrants and the node has 4 child nodes each representing one of the quadrants.( the screen is recursively divided into subscreens).
Now given two screens represented by two quadra trees, return a quadra tree which represents the overlapping of the two screens.( assume when white and white overlaps results in white,black and white overlap results in black , black and black overlap results in black).
algo and code both have to be given. Report Duplicate  Flag  PURGE
Microsoft  2of 2 votes
Answers(Bar Raiser Round)
 gdg in United States
Divide the array(+ve and ve numbers) into two parts such that the average of both the parts is equal.
Input:
[1 7 15 29 11 9]
Output:
[15 9 1 7 11 29]
Explanation:
The average of first two elements is (15+9)/2 = 12, average of remaining elements is (1+7 +11 +29)/4 = 12 Report Duplicate  Flag  PURGE
Amazon Arrays  1of 1 vote
AnswersGiven a singly linked list, modify the value of first half nodes such that 1st node’s new value is equal to the last node’s value minus first node’s current value, 2nd node’s new value is equal to the second last node’s value minus 2nd node’s current value, likewise for first half nodes.
 gdg in United States
(No extra memory to be used) Report Duplicate  Flag  PURGE
Amazon  1of 1 vote
AnswersTwo robots land with their parachutes on an infinite onedimensional number line. They both release their parachutes as soon as they land and start moving. They are allowed only to make use of the following functions.
 gdg in India
I. moveLeft() // robot moves to left by 1 unit in 1 unit time
II. moveRight() // robot moves to right by 1 unit in 1 unit time
III. noOperation() // robot does not move and takes 1 unit time
IV. onTopOfParachute() // returns true if the robot is standing on top of either of the parachute, else false
V. didWeMeet() // returns true if the robot meets to the other robot, else false
Write a function in order to make the robots meet each other. Robots will be executing the same copy of this function. Report Duplicate  Flag  PURGE
 1of 1 vote
AnswersYou have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
 gdg in United States
another array ar_low[] such that ar_low = number of elements lower
than or equal to ar in ar[i+1:n1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed. Report Duplicate  Flag  PURGE
Amazon  4of 6 votes
AnswersYou have an array of integers(size N), such that each integer is present an odd number of time, except 3 of them(which are present even number of times). Find the three numbers.
 gdg in United States for Bing
Only XOR based solution was permitted.
Time Complexity: O(N)
Space Complexity: O(1)
Sample Input:
{1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9}
Sample Output:
1 6 8 Report Duplicate  Flag  PURGE
Google Developer Program Engineer Arrays  1of 1 vote
AnswersWhat would be the O/P and why?
#include<stdio.h> #include<conio.h> int main() { int k = 7; printf("%d", 0 < !k); return 0;
}
 gdg in United States Report Duplicate  Flag  PURGE
Accenture  1of 1 vote
AnswersExplain the output of the following code:
 gdg in United Statesint main( ) { int x = 10, y = 20;/. x =!x; y =!x&&!y; printf(“x =%d y =%d”, x, y); return 0; }
 Report Duplicate  Flag  PURGE
Amazon C  3of 3 votes
Answerswhy will the code show error when tried to compiled
below given is a C program snippet to get height of a binary tree.int height (struct node * root) { if(root=NULL) return 0; else { return max(height(root>left), height(root>right))+1; } } int max(int a,int b) { return ((a>b)?a:b);
}
 gdg in United States Report Duplicate  Flag  PURGE
Adobe Algorithm
 2 Answers If we have to allocate memory ...
If we have to allocate memory to a string of size n and read the string at run time character by character?
And we write the following code then why doesn't it works properly#include <stdio.h> #include <conio.h> #include <malloc.h> #include <stdlib.h> #include <string.h> int main() { int n,i; printf("Enter size n: "); scanf("%d",&n); char* str=(char*)calloc(n+1,sizeof(char)); for(i=0;i<n;i++) scanf("%c",&str[i]); str[n]='\0'; printf("%s",str); getch(); return 0; }
i wrote this but why doesnt it works properly??
 gdg March 17, 2014 Flag  PURGE  2 Answers If we have to allocate memory ...
If we have to allocate memory to a string of size n and read the string at run time character by character?
And we write the following code then why doesn't it works properly#include <stdio.h> #include <conio.h> #include <malloc.h> #include <stdlib.h> #include <string.h> int main() { int n,i; printf("Enter size n: "); scanf("%d",&n); char* str=(char*)calloc(n+1,sizeof(char)); for(i=0;i<n;i++) scanf("%c",&str[i]); str[n]='\0'; printf("%s",str); getch(); return 0;
}
 gdg March 17, 2014
i wrote this Flag  PURGE
#include <stdio.h>
#include <stdlib.h>
void print(int *arr, int m, int n)
{
int i, j;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
printf("%d ", *((arr+i*n) + j));
}
void traverse(int * arr,int m, int n,int cur_x,int cur_y,int dest_x,int dest_y,int moves)
{
if(cur_x>=mcur_y>=ncur_x<0cur_y<0)
return;
*((arr+cur_x*n) + cur_y)= moves;
if(moves==(m*n)&&cur_x==dest_x&&cur_y==dest_y)
{
print((int *)arr,m, n);
return;
}
traverse(arr,m,n,cur_x,cur_y+1,dest_x,dest_y,moves+1);
traverse(arr,m,n,cur_x+1,cur_y,dest_x,dest_y,moves+1);
traverse(arr,m,n,cur_x,cur_y1,dest_x,dest_y,moves+1);
traverse(arr,m,n,cur_x1,cur_y,dest_x,dest_y,moves+1);
}
int main()
{
int arr[3][3] = {{0,0,0}, {0,0,0}, {0,0,0}};
int m=3,n=3;
traverse((int *)arr,m,n,0,0,2,2,1);
return 0;

gdg
August 01, 2014 Algorithm:
Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.
1) Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node>next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
(a) Find out the last node using a loop.
while(current>next != *head_ref)
current = current>next;
(b) Change the next of last node.
current>next = new_node;
(c) Change next of new node to point to head.
new_node>next = *head_ref;
(d) change the head pointer to point to new node.
*head_ref = new_node;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current>next!= *head_ref &&
current>next>data < new_node>data)
{ current = current>next; }
(b) Make next of new_node as next of the located pointer
new_node>next = current>next;
(c) Change the next of the located pointer
current>next = new_node;
#include<stdio.h>
#include<stdlib.h>
/* structure for a node */
struct node
{
int data;
struct node *next;
};
/* function to insert a new_node in a list in sorted way.
Note that this function expects a pointer to head node
as this can modify the head of the input linked list */
void sortedInsert(struct node** head_ref, struct node* new_node)
{
struct node* current = *head_ref;
// Case 1 of the above algo
if (current == NULL)
{
new_node>next = new_node;
*head_ref = new_node;
}
// Case 2 of the above algo
else if (current>data >= new_node>data)
{
/* If value is smaller than head's value then
we need to change next of last node */
while(current>next != *head_ref)
current = current>next;
current>next = new_node;
new_node>next = *head_ref;
*head_ref = new_node;
}
// Case 3 of the above algo
else
{
/* Locate the node before the point of insertion */
while (current>next!= *head_ref && current>next>data < new_node>data)
current = current>next;
new_node>next = current>next;
current>next = new_node;
}
}
/* Function to print nodes in a given linked list */
void printList(struct node *start)
{
struct node *temp;
if(start != NULL)
{
temp = start;
printf("\n");
do {
printf("%d ", temp>data);
temp = temp>next;
} while(temp != start);
}
}
/* Driver program to test above functions */
int main()
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;
/* start with empty linked list */
struct node *start = NULL;
struct node *temp;
/* Create linked list from the array arr[].
Created linked list will be 1>2>11>56>12 */
for(i = 0; i< 6; i++)
{
temp = (struct node *)malloc(sizeof(struct node));
temp>data = arr[i];
sortedInsert(&start, temp);
}
printList(start);
getchar();
return 0;
}
Output:
1 2 11 12 56 90
Time Complexity: O(n) where n is the number of nodes in the given linked list.
Case 2 of the above algorithm/code can be optimized.
// Case 2 of the above algo
else if (current>data >= new_node>data)
{
// swap the data part of head node and new node
swap(&(current>data), &(new_node>data)); // assuming that we have a function swap(int *, int *)
new_node>next = (*head_ref)>next;
(*head_ref)>next = new_node;
}

gdg
March 11, 2014 here's the code for you man,
cheers!!!
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<math.h>
int main()
{
long int num,c,x,i;
printf("enter the fuckin number, PUNK!!!");
scanf("%d",&num);
long int b=num%1000;
int a=num/1000;
int n1=a;
c=0;
while(n1!=0)
{
c++;
n1=n1/10;
}
if(c%2==1)x=c1;
else x=c;
for(i=x;i>=0;i=i2)
{
if(((a/(int)pow(10,i))%100)!=0)
printf("%d,",((a/(int)pow(10,i))%100));
}
printf("%d",b);
getch();
}

gdg
January 14, 2014 Why not just use a hash table? Always insert each number into the table, no matter what. If it's already in there, it doesn't matter, since you are replacing a number with itself. Then return the 100 highest entries in the table as your new hash table, so you don't run out of memory.
We don't need to sort it, since the hash does that. We don't care if we have a duplicate, since each bucket only holds one item. Finally, we don't care where it falls in relation to anything else, since we always return the top 100 entries.
how to make it behave in a normal manner so that when the input is given in the form of a string:
i can use the above method to store the numbers in an array
 gdg August 14, 2014int ar[10];
ar[0]=1
ar[1]=2
ar[2]=3
:
:
: so on.......