siva.sai.2020
 0of 0 votes
AnswersFace to Face
 siva.sai.2020 in United States
Q4) two arrays given to you. First array contains number s. Second array contains key values.
We need to find smallest window in first array which covers all second array elements.
e.g:
Input= {6,7,1,3,2,4,5,2,3,1,2,5}
Keys = {2,5,1}
answer: from 9th index to 11th index is the smallest window. Report Duplicate  Flag
Amazon SDE2 Algorithm  1of 1 vote
AnswersFace to face
 siva.sai.2020 in India
Q3) stream of numbers coming, get 'n' min elements at any point of time Report Duplicate  Flag
Amazon SDE2 Algorithm  0of 0 votes
AnswersWritten test:
 siva.sai.2020 in India
Q2) in single linked list reverse alternative k nodes.
e.g. k=3 , 1>2>3>4>5>6>7>8>9>10
3>2>1>4>5>6>9>8>7>10
void reverseAlternativeKNodes(node *&head, int k); Report Duplicate  Flag
Amazon SDE2 Algorithm  0of 0 votes
AnswersWritten Test question:
 siva.sai.2020 in India
Q1) Given binary tree find largestPath size from one leaf to another leaf.
int getLargestPathSize(node *root); Report Duplicate  Flag
Amazon SDE2 Algorithm  1of 1 vote
AnswersValidate whether given string is valid JSON fromat string or not.
 siva.sai.2020 in India
I/P: {a:b}
O/P: Yes Valid JSON
I/P: {a:b, c:d}
O/P: Yes Valid JSON
I/P: {a:b,c:{e:f}}
O/P Yes Valid JSON
I/P: {a}
O/p: not a valid json
I/P: {{a}}
O/P: not valid JSON Report Duplicate  Flag
Google  0of 0 votes
AnswersReverse k batch nodes in single linked list
 siva.sai.2020 in India
I/P: k =3 , 1>2>3>4>5>6>7>8>9
O/P: 7>8>9>4>5>6>1>2>3
I/P: k =3 , 1>2>3>4>5>6>7>8>9>10
O/P: 10>7>8>9>4>5>6>1>2>3 Report Duplicate  Flag
 0of 0 votes
AnswersArray with distinct elements is given to you. write an API to return max selected ZIG ZAG array length.
 siva.sai.2020 in 
Zig Zag array can start with either '<' or '>'. Below two are valid Zig Zag arrays.
a<b>c<d>e<f
x>y<z<l>k
Note: you may need to skip some elements while selecting Max Zig Zag array. But you should not change array order(swapping and sorting not allowed).

Zig Zag array examples
Test Case1:
I/P : { 1,42,59,43,68,44 };
O/P: return 5 (Selected ZIG ZAG array 1 < 42 > 43< 68 > 44)
Test case2:
I/P: { 100,42,54,2,5 };
O/P: return 5 (slected ZIg Zag array 100> 42 <54>2 < 5)
Test case 3:
I/P: { 1,42,54,20,1 };
O/P: return 3 {slected Zig zag array 1<42>20} Report Duplicate  Flag
Software Developer  0of 0 votes
AnswersBelow is almost correct program, there is only one line code is wrong, you have to fix it.
String str contains only a and b characters. below program checks whether str contains equal number of a and b characters.
 siva.sai.2020 in Indiavoid checkBalance(string str) { char temp[MAXLEN]; int i, j; for (i = j = 0; temp[i] = str[j]; j++) if (str[j] == temp[i]) i++; else i; if (i == 0) printf("Balanced\n"); else printf("Not Balanced\n"); }
 Report Duplicate  Flag
SDE1 Algorithm  0of 0 votes
AnswersGiven string a and b, with b containing all distinct characters, find the longest common subsequence's
 siva.sai.2020 in India
length. Expected complexity O(nlogn). Report Duplicate  Flag
Uber SDE1 Algorithm Data Structures  1of 1 vote
AnswersGiven a 4*n block, find number of different ways of filling it with 1*2 smaller blocks. Rotation of smaller blocks is allowed.
 siva.sai.2020 in India Report Duplicate  Flag
Uber SDE1 Algorithm Data Structures  1of 1 vote
AnswersGiven an array of numbers, for every index i, find nearest index j such that a[j] > a[i].If such an index doesn’t exist for i, 1 should be printed.
 siva.sai.2020 in India Report Duplicate  Flag
Uber SDE1 Algorithm Data Structures  0of 0 votes
Answers2. VeryLongInt
 siva.sai.2020 in India
Design a class which can add and subtract integers up to 1000 digits. You can make the following assumptions
No need to handle overflow or underflow (extra credit if you do)
Copy constructor is available
“+” and “” are binary operators Report Duplicate  Flag
Google SDE2 Algorithm  2of 2 votes
Answers1. Balanced Parentheses
 siva.sai.2020 in India
Given a string s of parentheses (ex: “(()”), return the minimum number of parentheses that need to be inserted to make it into a well formed string
A well formed (balanced) string of parentheses is defined by the following rules: ● The empty string is well formed. ● If s is a well formed string, (s) is a well formed string. ● If s1 and s2 are well formed strings, their concatenation s1s2 is a well formed string.
Implement
int MinNumInsersertionsForBalancing(const string& s) Report Duplicate  Flag
Google SDE2 Algorithm  1of 1 vote
Answers#include <stdio.h>
 siva.sai.2020 in India for NA
#include <unistd.h>
#include <stdlib.h>
int main(void) {
int i =0;
while(1)
{
i++;
printf("\n %d ", i);
pid_t pid;
pid = fork();
if(pid < 0)
{
wait(3600);
}
else if(!pid)
{
sleep(1);
exit(0);
}
else
{
sleep(10);
}
}
// your code goes here
return 0;
}
Is there any problem with this code ?. I ran this code, and saw same i value printing, but do not understand why it is printing twice Report Duplicate  Flag
optum SDE2  0of 0 votes
Answersclass A {
 siva.sai.2020 in United States for abc
public:
void virtual fun1() { cout << " A::fun1" << endl; }
void virtual fun2() { cout << "A::fun2" << endl; }
};
class B : public A {
public:
void fun1() { cout << " B::fun1" << endl; } // fun1 > B
};
class C {
public:
int z;
virtual void fun3() { cout << "C::fun3" << endl; }
};
class D: public B, public C {
public:
void fun4() { cout << "D::fun4" << endl; }
};
void other(void* obj) {
C *c = (C*)obj;
c>fun3();
}
int main() {
D* d = new D();
other(d);
return 0;
}
what prints c>fun3 in other() function ?, reason behind it ?.
It is printing B::fun1. I do not know reason , can some one explain it Report Duplicate  Flag
SDE2  0of 0 votes
Answers<round 2>
 siva.sai.2020
16. Find out largest common SEQUENCE
e.g:
1)
str1: ABCDEF
str2: ABC
LArgest Common sequence: ABC
2) str1: ABCDEF
str2: ACEG
LArgest Common sequence: ACE
3)
str1: ABCDEF
str2: ZACYEFX
Largest common sequence : ACEF
NOTE: SEQUENCE need not be consecutive . Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answers<round 2>
 siva.sai.2020
15. We have a special tree, in which every node contains random number of child nodes.
Note : each node can contains no. of child nodes between ZERO to INFINITY
sub questions:
1) node structure definition ?
2) which traversal you use ?. Traversal code ? Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answers<round 2>
 siva.sai.2020
14) How you will achieve encapsulation in C language ?. Report Duplicate  Flag
MAGMA Software Engineer / Developer C++  0of 0 votes
Answers<round 2>>
 siva.sai.2020
13. Different types of TYPECASTS in C++ ? Report Duplicate  Flag
MAGMA Software Engineer / Developer C++  0of 0 votes
Answers<round 2>
 siva.sai.2020
12. Iterative Binary Search Algorithm with Single comparison . Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answer<round 2>
 siva.sai.2020
11. Explain PREORDER, POST OREDER, INORDER. ?. To construct tree which 2 ORDERS needed ? Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answers<round 2>
 siva.sai.2020
10. How many ZERO s in 100! ? Report Duplicate  Flag
MAGMA Software Engineer / Developer Brain Teasers  0of 0 votes
Answers<round 2>
 siva.sai.2020
9. How to check given number is prime or not ? Report Duplicate  Flag
MAGMA Software Engineer / Developer Brain Teasers  0of 0 votes
Answers<round 2>
 siva.sai.2020
8. Number N is given to you. You have to print all Permutations between 1 to N.
e.g
1) N = 2
o/p: 1 2
2 1
2) N =1
O/p : 1 Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answers<round 2>
 siva.sai.2020
7. Quick Sort avg and Worst case complexity . write code for Quick sort ? Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answers<round 1 >
6) what is fork()
sub questions
1) How many times "SIVA" will be printedi = 0 ; while (i < n ) { fork(); printf("\n SIVA"); i++; }
2)How many times "SIVA" will be printed
 siva.sai.2020i = 0 ; while (i < n ) { printf("\n SIVA"); fork(); i++; }
 Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answer<round 1>
 siva.sai.2020
5) Explain about Thread Pool ? Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answers<round 1>
 siva.sai.2020
4) Difference between FlipFLOP ? Where we use flip flop ? Report Duplicate  Flag
MAGMA Software Engineer / Developer Computer Architecture & Low Level  0of 0 votes
Answer<round 1>
 siva.sai.2020
3) Unbalanced or Skewed binary tree root is given to you. You have balance tree by doing LEFT and RIGHT rotations. Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answers<round 2 >
 siva.sai.2020
2) Write your own "cp" command to copy files. Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answers<Round 1>
 siva.sai.2020
1) Iterative Single Linked List Reverse Report Duplicate  Flag
MAGMA Software Engineer / Developer Algorithm  0of 0 votes
Answers5) Can we crash a process before entering Main() function ?
I said possible and I give following two examples
example 1:int *i = 0; int j = *i; // I think here memory access violation since pointer 'i' pointing 0th address. int main() { return 0; }
Example 2:
int i = 1 / 0; // here Float point exception or divided by zero exception. int main() { return 0; }
Today I executed , above two examples and I am getting compile time error "Line 2: error: initializer element is not constant
 siva.sai.2020
" .
Can some one please tell me why I am getting compile time error ? Report Duplicate  Flag
Gluster Software Engineer / Developer C  0of 0 votes
Answers4) How to initialize Constant variables in class( or object).
example 1: throws error "uninitialized member 'myclass::i' with 'const' type 'const int'
"#include <iostream> using namespace std; class myclass{ public: const int i; myclass() { i = 10; // here throws error } }; int main() { myclass m; cout<<m.i<<endl; return 0; }
example 2: below piece of code works fine .
#include <iostream> using namespace std; class myclass{ public: const int i; myclass() : i(10) { } }; int main() { myclass m; cout<<m.i<<endl; return 0; }
Can some one please explain me , why second example works fine ? . why not first example ?
 siva.sai.2020 Report Duplicate  Flag
Gluster Software Engineer / Developer C++  0of 0 votes
Answers3) Littele Endian vs Big Endian ?
 siva.sai.2020
Sub questions:
1) which one decides endianess , Processor(CPU) or Operating System ?
2) There any standard ways to convert little endian data to big endian and vice versa .
My answer:
Linux is little endian and Solaris is big endian.
After that I said Processor(CPU) decides endianness of the machine. Intel processor supports little endian and SPARCV( Solaris) processor supports big endian.
He asked what about Solaris operating system with Intel processor ?. I said it is little endian.
Am I correct ? Report Duplicate  Flag
Gluster Software Engineer / Developer Computer Architecture & Low Level  0of 0 votes
Answers2. write down Linux "grep" command code.
 siva.sai.2020
Input: file and a pattern
Eg.
$ Mygrep "siva*" names.txt
Output:
print entire line if it contains "Siva" word or prefix.
e.g:
"good bad siva is bad boy."
"sivabrtt gjfg"
After that asked me to write code to support regular expressions like "Siva*", "siva+venkat", "^siva". Report Duplicate  Flag
Gluster Software Engineer / Developer Algorithm  0of 0 votes
Answers1) Print tree in reverse Spiral Order .
Input:1 / \ 2 3 / \ / \ 4 5 6 7
Output: 4>5>6>7>3>2>1
 siva.sai.2020 Report Duplicate  Flag
Gluster Software Engineer / Developer Algorithm  0of 0 votes
Answersint main() { int i=10; { int i=100; printf("%d", i); } }
1.what is the output ?
 siva.sai.2020
2. what signifies "{" "}" in above code .
"{" "}" will it create new "Activation Record" ( or Frame) in Stack ? Report Duplicate  Flag
Amazon Software Engineer / Developer C  0of 0 votes
Answers<round 3>
11. difference between Inline and macro functions.
sub question :
1) what happens if you apply inline on recursive function.
2) is there any Recursive Macro function ?
e.g#define SUM(x, y) do{ SUM(x,y); }while(0);
is there any error ?
 siva.sai.2020 Report Duplicate  Flag
Amazon Software Engineer / Developer C  0of 0 votes
Answers<round 3>
 siva.sai.2020
10. differences between
char *str = "SIVA" and char str1[]="SIVA"
sub questions:
1) where string literal i.e "SIVA" will be stored ( heap , stack, data or code segments) in above both cases.
2) char *str = "SIVA";
str[0] = 'f' ;
any error ? compile time error or run time error ?
3) char *p = (char *) str;
p[0] = 'f' ;
any error ? compile time error or run time error ? Report Duplicate  Flag
Amazon Software Engineer / Developer C  0of 0 votes
Answers<round 3>
 siva.sai.2020
9. Array A[n] it contains numbers from 1 to n but 1 number repeated. Find out missing number.

I have not answered this question and manager not happy with my performance. THIS THE END OF THE BATTLE. Report Duplicate  Flag
Amazon Software Engineer / Developer Data Structures  0of 0 votes
Answers<round3 >
 siva.sai.2020
8.He asked me many Hashing questions.
Sub questions
1. What is hashing ?
2. you can write your own hash methods or you can use existing Hash methods in STL C++.
which one you prefer ? why ?
3. Write a Generic hash function & hash table , which should support all data types INT, FLOAT, STRINGS, and OBJECTS . Report Duplicate  Flag
Amazon Software Engineer / Developer Data Structures  0of 0 votes
Answers<round3> ( Manager round )
7. Check given tree is symmetric or not ?
e.g
 siva.sai.20201) Symmetric 1 / \ 2 2 / \ 3 3 2) nonsymmetric 1 / \ 2 3
 Report Duplicate  Flag
Amazon Software Engineer / Developer Data Structures  0of 0 votes
Answers<round 2>
 siva.sai.2020
6. Quadrant contains N points and all are + ve points ( I mean both (X,Y) are +ve values).
sub questions:
1. How you will store( or Data structure) N points to make look up( or search) easy.
2. Find out closest point (Pj) for a entered point (Pi).
Note: He asked me time efficient solution.
User can add extra M points later point of time. So your solution should be Scalable. Report Duplicate  Flag
Amazon Software Engineer / Developer Data Structures  0of 0 votes
Answers<round 1>
 siva.sai.2020
5. Reverse single linked list . Report Duplicate  Flag
Amazon Software Engineer / Developer Algorithm  0of 0 votes
Answers<Round 1>
 siva.sai.2020
4. Grid[n][n] contains letters from 'A' to 'Z' randomly. You have to print all possible words from grid.
You are allowed to move Left, Right, Up and Down ( no diagonal move).
Sub Questions:
1. Write down Dictionary_Lookup() function prototype. ( I no need to implement Dictionary_Lookup() but I have to write down possible return value and its arguments ).
This help us to find out traversed characters forming word or not.
2. Write down complete code to print all possible words in Grid. Report Duplicate  Flag
Amazon Software Engineer / Developer Algorithm  0of 0 votes
Answers<written test >
 siva.sai.2020
3.check whether given single linked list is palindrome or not.
e.g: 1>2>1 palindrome
1>2>3 not a palindrome
Note: Time efficient and without using any other data structures. Report Duplicate  Flag
Amazon Software Engineer / Developer Algorithm  0of 0 votes
Answers<written test >
 siva.sai.2020
2. Two sorted arrays A[X] and B[Y+X]. in B array contains Y sorted elements and B can accommodate A[] X elements.
W.A.P to Merge two arrays and store resultant in B[] array.
Note: Time efficient and space efficient solution Report Duplicate  Flag
Amazon Software Engineer / Developer Algorithm  0of 0 votes
AnswersI appeared for the Amazon( Bangalore) Interview on 05Feb2011. I cleared written test. After that I gave 3 rounds of interview.
 siva.sai.2020
Note: They are going conduct interviews on 13Feb2011 also. There is a chance to repeat following questions.
< written Test >
1. Preorder string"NNLLNLL" ( or similar string ) has given to you. You have to construct binary tree.
Here 'N' means non leaf node.
Here 'L' means leaf node.
Note: every node contains 0 or 2 childrens. Report Duplicate  Flag
Amazon Software Engineer / Developer Algorithm  0of 0 votes
Answerswrite down String class copy constructor ?
 siva.sai.2020 Report Duplicate  Flag
Microsoft Software Engineer in Test  0of 0 votes
Answersfind a bug in following code : class A { public: static int i; void print() { cout<< i << endl ; } }; int main() { A a; a.print(); }
I run above code, and I am getting "ndefined reference to `A::i'" . Why I am getting this error ?
 siva.sai.2020 Report Duplicate  Flag
Microsoft Software Engineer in Test  0of 0 votes
AnswersHow can we generate all possibilities on braces ?
 siva.sai.2020
N value has given to us and we have to generate all possibilities.
**Examples:**
1) if N == 1, then only one possibility () .
2) if N==2, then possibilities are (()), ()()
3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...
Note: left and right braces should match. I mean )( is INVALID for the N==1
How can we solve this problem by using recurrence approach ? Report Duplicate  Flag
Amazon Software Engineer / Developer  1of 1 vote
AnswersQuestion on Tree Data Structure: How can we fill all inorder successor pointer of all tree nodes ?
Tree node contains 3 pointers *left, *right and *Successor .Struct node{ int data; struct node *left; struct node *right; struct node *successor; };
A / \ B C / \ / \ D E F G
INORDER Traversal: **DBEAFCG**
**Note:** A inorder successors are F,C and G.
**Function prototype:** void FillSuccessorNodes( struct node *root);
Tree's root node given to us and we need to fill successor pointer for all nodes.case 1) some of the Successor pointers may be **NULL** . This case you have to fill that pointer with immediate Inorder Successor.
Example: if A>Successor == NULL, then fill A>Successor = F
case 2) some of the Successor pointers may already points to correct successors. This case You no need to modify successor pointers.
Example: 1) A>successor = F is valid
2) A>successor = C is valid
3) Asuccessor = G is valid . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes.case 3) Some of the successor pointers are **not NULL** but these pointers pointing to INVALID successors i.e it could be inorder successor or some garbage value. This case you have to fill these nodes with immediate successor nodes.
Example:
1) A>successor = B is invalid since B is not successor node , so we have to correct it to A>successor = F.
2) A>successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A>successor = F.**1) Interviewer asked me time efficient solution in O(n) time complexity. Extra space allowed. 2) she gave some hint i.e we can use HASHing.**
 siva.sai.2020**If you know the solution for this problem, please let me know .**
 Report Duplicate  Flag
Amazon Software Engineer / Developer
int noYears(double x1, double x2, double R )
{
int n=0;
while ( x1 < x2 )
{
n++;
x1 = x1 + x1*R ;
}
if( x1 == x2)
return n;
else
return 1;
}

siva.sai.2020
April 21, 2012 struct treeNode
{
int data;
int count ; // this node childrens count
struct node *left, *right;
};
step1: asume , tree size is n.
spep2: use 0 to n1 random genrator. random genrator everytime returns one of the value in between 0 to n1 .
step3: now we know the node index to return, we can return this node in O(logn ) time by using tnode>count field.
e.g
int main()
{
index = NrandomGen() ;
randomNodeGenerator(root, index);
}
struct treeNode * randomNodeGenerator( struct treeNode *root, int nodeIndex)
{
if( (root)  (root>left == NULL && root>right == NULL))
{
return root;
}
else if ( root>left == NULL )
{
if(nodeIndex == 0)
{
return root;
}
else
{
nodeIndex = nodeIndex 1;
return randomNodeGenerator(root>right, nodeIndex );
}
}
else
{
if(nodeIndex == 0)
{
return root;
}
else if( root>left>count + 1 == index )
{
return root;
}
else if ( (root>left>count + 1 ) < index )
{
nodeIndex = nodeIndex  root>left>count 2 ;
return randomNodeGenerator(root>right, nodeIndex );
}
else
{
return randomNodeGenerator(root>left, nodeIndex );
}
}
}
Time complexity O(logn );
 siva.sai.2020 April 21, 2012Double linked list would be easier which proposed by Tintin
 siva.sai.2020 April 21, 2012@Tintin, very good answer
 siva.sai.2020 April 21, 20121. After push and pop operations, we need to adjust middle element value in "Middle" variable .
2. After push operation, no of element in stack are even no need to change middle element in "Middle" variable
3. After pop operation, no of element in stack are odd no need to change middle element in "Middle" variable
#define STACK_SIZE 100
class stack
{
int top;
int middle; // stores middle element
int S[STACK_SIZE];
stack()
{
top = 1 ;
middle = 1;
}
int getmiddle(int count);
public:
int findMidElement();
void push( int elem );
int pop(void);
};
int stack::findMidElement()
{
return middle;
}
void push (int elm )
{
if( top+1 == STACK_SIZE )
{
printf("\n stack overflow \n ");
return ;
}
S[++top] = elm;
// no of elements are odd in stack , then get correct middle element
if( (top + 1) % 2 == 1 )
{
middle = getmiddle( int (top/2) );
}
}
int stack::pop( void )
{
if ( top == 1 )
{
printf("\n stack underflow \n ");
return 1; // error
}
int elm = s[top] ;
if( (top+1 ) % 2 == 0 )
{
middle = getmiddle(int (top/2));
}
return elm;
}
int stack::getmiddle(int count)
{
int elm, retElm;
if( count == 0)
{
elm = pop();
push(elm);
return elm;
}
elm = pop();
retElm = getmiddle(count1);
push(elm);
return retElm;
}
@light, thanks
 siva.sai.2020 April 20, 2012step1 : This problem can solved just by finding permutations of a,e,i,o,u in 5 places ( repetition allowed )
step2: divide 10 place into two parts. find permutations for first 5 places, and fill remaining 5 places in reverse order.
Step3: print 10 places at the end of each permutation . total palindromes 5*5*5*5*5
code ::
//calling convention permutations( input, permute, 5, 0);
void permutations(char Input[], char permute[], int n, int index )
{
int i=0;
// printing palindrome
if( index == n )
{
for( i =0 ;i < n; i++ )
printf("%d, ", Permute[i] );
for( i =n1 ;i >= 0; i)
printf("%d, ", Permute[i] );
Printf("\n");
return ;
}
for (i = 0 ; i < n; i++)
{
Permute[index] = Input[i];
permutations( Input, permute, n, index +1 );
}
}
@eugene, thanks for pointing my mistrake
 siva.sai.2020 April 19, 20121. take 3 min priority Queues
Q2 // stores 2 prime no combination no.s like 2, 2*2, 2*3 , 2*5
Q3 // stores 3 prime no combination no.s like 3, 3*3, 3*5 ( no need to store 3*2 since it is already stored in Q2 queue )
Q5 // stores 5 Prime nos like 5,5*5 , 5*5*5
2. min = getMin( Q2, Q3, Q5 )
if( min == min(Q2 ) )
{
delete min from Q2;
add (min*2, Q2 ) ;
add (min*3, Q2 );
add ( min *5, Q2);
}
else if( min == min(Q3 ) )
{
delete min from Q3;
add (min*3, Q3 ) ;
add ( min *5, Q3);
}
else
{
delete min from Q5;
add ( min *5, Q5);
}
3. print min . do step 2 and 3 for 100 times to print 100 min no.
000
001
010
011
100
101
110
111
no of 1s count in 3 digit nos ( from 0 to 7 ) = pow(2, 31 ) * (3) = 12
no of 1s count in 4 digit no.s ( from 0 to 15 ) = pow(2, 41 ) * (4) = 32
if 4th digit is 1, which means number is greater than 7,
1s count = 3 digit 1s count + add how many times current 4th bit is 1 ( this is equal to num % 7).
int NoOfONEs(int num)
{
int i =1, count =0 ;
if( num & 1 )
{
count ++;
}
while ( i < 32)
{
if ( num & ( 1<< i ) )
{
count + = pow(2, i1 ) * (i ) + num % (pow(2, i ) )+ 1 ;
}
i++;
}
return count;
}
1. Find mapping in o(n2) TC
e.g actual array = 2315
permuted array 5213
mappings 1>2, 2>4,3>3, 4>1
2. to get same element in same poition in array ,
transiton path for first element 1>2>4>1
transiton path for second element 2>4>1>2
similarly for other elements
2315
5213 ( 1st permutation)
3512 (2nd permutation)
2315( 3rd permutation )
3. from the above transiton path, it is clear that , we get same elememt back into same positon after 3 permutation ( it is transiotn path length ).
4. transiotn length give us no. of pemutations required to get original array.
code ::
/// assumption given array is distinct array ( I mean there is no duplicats in array )
int matching[n];
int NoOfPermutation( int OrgArray[], int PermutedArray, int n )
{
int i,j;
int transitonPathLength =0 ;
// find matchings, store them in Matching[]
for ( i =0 ; i <n ;i ++ )
{
for(j =0 ; j< n; j++ )
{
if( OrgArray[i] == PermutedArray[j] )
{
matching[i] = j;
break;
}
}
}
// we know the matchings, now just we need to calculate transiton path length
i=0;
// if an element is in same position in Original array and Permuted array, it is not possible to calculate transiton path length.
while ( i == matching[i] )
{
i++;
}
j = i;
while ( i ! = matching[j] )
{
transitonPathLength++;
j = matching[j] ;
}
return transitonPathLength ;
}

siva.sai.2020
April 19, 2012 Just for simplicity assume X =2 , that mean we have 2 vectors.
Case 1: when 2 vectors sorted, we can simply use medians of median algorithm to find medain of combined vector.
Time complexity : O(logn)
Space complexity : O(1)
note: here n = n1+n2 ( n1 1st vector size , and n2 second vector size )

Case 2: when 2 vectors not sorted, then we better to use two Heaps (min & max).
1. if n is even, max and min heap sizes n/2 .
2. if n is odd, max heap size n/2 +1 , and min heap size n/2 .
3. add small elements of vector into max heap , simlarly add max elements into min heap.
4. After inserting n elemets into min & max heaps. if n is odd, max element in max heap is the medain.
5. if n is even, get max elm for max heap, and get min elm from min heap, avg of both elms is the median.
==================================================
if X is big number , I mean X > 2 . then use following algoriths
case 1: when all X vectors sorted.
step1: take MIN heap of size X , add first elemets of X vectors , now heap has x elemtns.
Step2: now delete min elemnt from heap, and add next element of vector which contains previously dleted min element.
step 3: repeat step 2 , till we get n/2 th min element. n/2 th element is median
TC = O(n);
SC = O(X) ;// heap size

Case 2: x vectors are unsorted
We can use selection algorithm. this algorithm bit difficult to explain. you better to refer Coreman book . below I mentioned basic steps.
step1 : this algothm divides n elements into n/5 groups,
step2: find median of each group .
step3: find median of mediands.
step4: do some elemts reduction based on current median value.
step5: becuase of reduction , we can find median in O(n) TC.
why you are used "SELECT Top 3", why top3 ?
 siva.sai.2020 April 19, 2012correct answer !
 siva.sai.2020 April 19, 2012Nice answer!
 siva.sai.2020 April 19, 2012you are right, variable "var " should be Volatile
 siva.sai.2020 April 18, 2012By using slopes, we can tell whether given point is inside triangle or not .
1. Let us assume A,B,C are triangle points. P is given point to check whether it is inside traingle or not.
2. calculate Slopes AB,AC,AP . AP slope should be between AB and AC.
3. similarly calculate BA,BC,BP slopes. BP slppe should be between BA and BC .
4. similarly calculate CA,CB,CP slopes. CP slppe should be between CA and CB .
if 2,3,4 statements true, then we can say Point P is inside traingle .
I cannot understand your solution. could you please elaborate your answer ?
 siva.sai.2020 April 18, 2012Algorithm:
1. we can solve this problem just by using inorder traversal .
2. in addition to inoreder traversal, just we need one "PrevVisitedNode" variable to store previously visited node address .
3. we now current node and previous node, so PrevVisitedNode>Next = Root;
code:
struct node
{
int data;
struct node *left;
struct node *right;
struct node *next;
}
typedef struct node *tnode;
void InorderTraversal(tNode *root, tNode **PrevVisitedNode )
{
if( root == NULL )
return;
InorderTravesal(root>left, PrevVisitedNode);
if( *PrevVisitedNode != NULL )
{
*PrevVisitedNode>next = root; // root is inoder successor to the previously visited node
}
*PrevVisitedNode = root;
InorderTraversal(root>right, PrevVisitedNode);
}

siva.sai.2020
April 18, 2012 Thanks Kumar,
while (1)
{
if( var != temp )
{
temp =var ;
update_clock(); // increase clock time by 1 second.
}
Sleep(50) ; // sleep for 50 milli seconds
}
Algo::
extern int var; // this variable is being changed from external world
int temp = var ;
while (1)
{
if( var != temp )
{
temp =var ;
update_clock(); // increase clock time by 1 second.
}
}

siva.sai.2020
April 18, 2012 1. Valid inputs are "123", "+123","123"
2. Invalids inputs are "1+23","123","*123"
3. Integer overflow case for large string ("21323333333333333332"), my code returns so far calculated integer value
long StringToNum( char *str, int len )
{
if( str == NULL  len < 1 )
{
printf(" Invalid input ");
return 1 ; // error code 1
}
else
{
long num = 0, num1 ;
while( len )
{
if( '0' <= str[len1] && str[len1] >= '9' )
{
num1 = num;
num = num * 10 + (int) (str[len]  '0' );
if(num1 > num )
{
printf("\n integer overflow " );
return num1;
}
}
else if( (len == 1 ) )
{
if(str[len1] == '' )
{
num *= 1 ;
}
else if (str[len1] != '+' )
{
printf(" Invalid input ");
return 1; // invalid input
}
}
else
{
printf(" Invalid input ");
return 1;
}
len  ;
}
return num;
}
}
Please letme know if you notice any mistake in my code

siva.sai.2020
January 21, 2012 int main()
{
/* 1100
0010
0100
0011
*/
int A[4][4] = {1,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1}, B[4][4];
int numComponent=0, i,j;
int n = 4; // array size
for(i=n1; i>=0; i)
for( j=n1;j>=0;j)
{
if(A[i][j] == 1)
{
/* right */
if( ( j+1 < n) && (A[i][j+1] == 1))
B[i][j] = B[i][j+1];
/* down */
else if( (i+1 <n ) && (A[i+1][j] == 1))
B[i][j] = B[i+1][j];
/* left down diagonal */
else if( (j1 >= 0 ) && (i+1 <n ) && (A[i+1][j1] == 1))
B[i][j] = B[i+1][j1];
/* right down diagonal */
else if( (j+1 < n ) && (i+1 <n ) && (A[i+1][j+1] == 1))
B[i][j] = B[i+1][j+1];
/* there is no adjacent 1's, so increase number of component count */
else
B[i][j] = ++numComponent;
}
}
printf("\n numberof components = %d\n", numComponent);
return 0;
}

siva.sai.2020
January 21, 2012 int KthSmallest( Tnode *root, int k )
{
if( root == NULL  k <= 0 )
{
printf("\n inavlid Input );
return 1; //throw error
}
else if ( root>left !=NULL )
{
int count = root>left>count ;
if( count + 2 == k )
{
return root>data;
}
else if( count + 2 < k )
{
return KthSmallest(root>right, kcount2 );
}
else
{
return KthSmallest(root>left, k );
}
}
ele if(root>right != NULL )
{
return KthSmallest(root>right, k1 ); // to ignore root, reduce k by one
}
else if ( k == 1 )
{
return root>data;
}
else
{
printf("\n theres is no %d smallest element ", k );
return 1
}
}

siva.sai.2020
September 06, 2011 void PrintDistinct(int A[], int n )
{
int i=1, temp = A[0] ;
printf("\n %d", temp );
for(; i< n ; i++ )
{
if( temp != A[i] )
{
temp = A[i] ;
printf("\n %d",temp );
}
}
}

siva.sai.2020
September 06, 2011 @Anonymous , Awesome answer .
 siva.sai.2020 March 28, 2011@kevinday.home , Excellent solution. Thanks for detailed explanation .
 siva.sai.2020 March 28, 2011@Anil, how you arrive @ 4!/2!2! ? , can you please explain it ?
 siva.sai.2020 March 27, 2011@ rash, How come BST time complexity O(log n ).
Let us say page nos
1 2 3 4 5
add a new page at stating of the book, then you have to modify all page nos .
1 2 3 4 5 6
Adding a new page at the starting of the book ,time complexity O(n). you have added n new pages at the staring then total time complexity O(n^2 ).
@rash, good answer
 siva.sai.2020 March 27, 2011@ coolGuy, If array is sorted and unique , then Binary search is the answer. Otherwise Anony's doubling index is proper answer.
@Anony, what is the time complexity of your answer ?
@Tulley , Good answer .
 siva.sai.2020 March 27, 2011Awesome answer!
 siva.sai.2020 March 26, 2011Awesome !
 siva.sai.2020 March 26, 2011@PKT, good logic.
Typing mistake , Small correction, in your solution 7 and 8 in same column.
5 and 6 also in same column.
correct one
9 5 13 1 14 2 10 6
11 7 15 3 16 4 12 8

siva.sai.2020
March 26, 2011 @ Paras, Very good answer.
 siva.sai.2020 March 26, 2011Bool IsBST()
{
// some code
}
in IsBST() you will read each node and compare node values. So you do only read operations.
IsBST() is Thread Safe function as long as you do only read operations.
If you change any node pointer values , then thread safe you need to consider.
TreeNode * Preorder_sucessor( TreeNode * root, TreeNode * KeyNode, bool *find )
{
if( root == NULL)
{
return NULL;
}
else
{
if( *find == TRUE )
{
return root;
}
else if( root == KeyNode )
{
*find == TRUE;
if( root>left != NULL)
{
return root>left;
}
else if( root>right != NULL)
{
return root>right ;
}
return NULL;
}
else
{
TreeNode *Successor;
Successor = Preorder_sucessor( root>left, KeyNode, find) ;
if( Successor != NULL)
{
return Successor
}
Successor = Preorder_sucessor( root>right, KeyNode, find) ;
return Successor;
}
}
}

siva.sai.2020
March 26, 2011 typedef struct node{
int Lock_Count ;
// by dafault Lock_count = 0 which means give node not locked .
// if Lock_count = 1 , means one node locked in this node rooted subtree
// if Lock_count = 2 , means two nodes locked in this node rooted subtree
struct node *Child[n];
struct node *Parent;
} Tnode;
Bool IsLock(Tnode *resource)
{
if( resource>Lock_Countcount == 0 )
{
return FALSE;
}
else
{
return TRUE;
}
}
void Lock(Tnode *resource)
{
if( resource == NULL)
{
return;
}
else
{
resource>Lock_Count = resource>Lock_Count + 1;
Lock( resource>Parent ) ;
}
}
void UnLock(Tnode *resource)
{
if( resource == NULL)
{
return;
}
else
{
resource>Lock_Count = resource>Lock_Count  1;
UnLock( resource>Parent ) ;
}
}
If you find anything wrong in my code or approach, please let me know
 siva.sai.2020 March 26, 2011@anonymous, Good Solution.
I think , with two rolls also we can do same thing.
2bit possible values

00 Head
01 Head
10 Head
11 Tail

Here Head probability 3/4 and Tail 1/4
struct treeNode * largestBST(struct treeNode *root, int *subBSTsize)
{
if( root == NULL )
{
*subBSTSize = 0;
return root;
}
else
{
struct treeNode *leftBSTroot, *rightBSTroot;
int leftBSTsize = 0, rightBSTsize = 0;
leftBSTroot = largestBST(root>left, &leftBSTsize) ;
rightBSTroot = largestBST( root>right, &rightBSTsize);
// if both left and right nodes are NULL
if(!leftBSTroot && !rightBSTroot)
{
*subBSTsize = 1;
return root;
}
// when there is no left sub tree
else if(!leftBSTroot)
{
if((rightBSTroot! = root>right)  (root>data < min(root>right)))
{
*subBSTsize = rightBSTsize;
return rightBSTroot;
}
else
{
*subBSTsize = rightBSTsize+1;
return root;
}
}
// when there is no right sub tree
else if(!rightBSTroot)
{
if((leftBSTroot! = root>left)  (root>data < max(root>left)))
{
*subBSTsize = leftBSTsize;
return leftBSTroot;
}
else
{
*subBSTsize = leftBSTsize+1;
return root;
}
}
else
{
// root is greater than left , & less than right subtree , and both left and right subtrees are BSTs
if( leftBSTroot == root>left && rightBSTroot == root>right && root>data >= max(root>left) && root>data < min(root>right))
{
*subBSTsize = leftBSTsize + rightBSTsize + 1;
return root;
}
if(leftBSTsize > rightBSTsize)
{
*subBSTsize = leftBSTsize;
return leftBSTroot;
}
else
{
*subBSTsize = rightBSTsize;
return rightBSTroot;
}
}
}
}

siva.sai.2020
March 11, 2011 int main()
{
int i = 0, n=2;
int temp1 = 0, temp2 =0 ;
int A[100] ;
A[0] = A[1]=1;
printf("\t %d \t %d \n", A[0],A[1] );
// print 100 pascal traingle rows
while( n < 10 )
{
temp2 = 0,temp1=0 ;
i = 0;
while( i < n )
{
temp2 = A[i] ;
A[i] = temp1 + temp2;
printf("\t %d ", A[i] );
temp1 = temp2 ;
i++;
}
n++;
A[i] = temp1;
printf("\t %d ", A[i] );
printf("\n");
}
}

siva.sai.2020
March 11, 2011 step1: we can solve this problem by using Dynamic probelm.
Step2: we have to find "intermediate paths between Ancestor and child ".
ste3: in above example ( ancestor, childs)
( 3, 1 )
( 2, 1 )
( 3, 2 )
( 3, 4 )
( 2, 4 )
Forming edge between 3>1 is incorrect it should be 3>2>1 ( edge from 3 to 2 , and then edge from 2 to 1 )
Code:
TreeNode * ConstructTree( int M[n][n], int ancestor, int child, node * root )
{
int i=0;
TreeNode *newChild = NULL;
for( ; i< n; i++ )
{
if( ( M[ancestor][i] == 1 ) && (i!= child ) )
{
newChild = ConstructTree(M, i, child );
if( newChild != NULL )
{
if( root>left == NULL )
{
root>left = newChild;
}
else if( root>right == NULL )
{
root>right = newChild;
}
return root;
}
}
}// end of for loop
if(M[ancestor][child] == 1 )
{
if( root>left == NULL )
{
root>left = child;
}
else if( root>right == NULL )
{
root>right = child;
}
return root;
}
return NULL;
}
int main()
{
for each edge (i,j) from M[][] and that edge not there in Tree
{
ConstructTree(M, i, j, root );
}
}

siva.sai.2020
March 11, 2011 I/P: A[4] = {2,3,4, 5}
O/P:
B[4] ={3*4*5, 2*4*5, 2*3*5, 2*3*4 } ;
Approach:
take two temp arrays and store no.s product
Temp1[4] = { 2, 2*3, 2*3*4, 2*3*4*5 }
Temp2[4] = { 2*3*4*5, 3*4*5, 4*5, 5 }
B[0] = Temp2[i+1] ;
for each i=1 to n2
B[i] = Temp1[i1] * Temp2[i+1]
B[n1] = Temp1[n2] ;

siva.sai.2020
March 11, 2011 I/P: tree
5
/ \
3 8
/ \ / \
1 4 6 9
O/p: double linked list ( but here I am representing single list)
1>3>15>8>9
=====================================
Approach
Step1: take 3 pinters *Prev, *cur and *next.
step2: do tree traversal
step3: Traversal( root, node *prev, node *cur, node * next );
for left subtree :
Traversal( root>left, prev>left, prev, cur );
for right subtree:
Traversal( root>right, cur, next, next>right );
code for this:
void Traversal(node *root, node *P, node *C, node *N )
{
if( root == NULL )
{
return;
}
else
{
if( C == NULL )
{
C = CreateNode();
C>data = root>data ;
C>left = P ;
C>right = N ;
if( P != NULL )
{
P>right = C;
}
if( N != NULL )
{
N>left = C ;
}
}
else
{
C>data = C>data + root>data ;
}
temp = P ? P>left : NULL ;
Traversal ( root>left, temp, P, C );
temp = N ? N>right : NULL ;
Traversal ( root>right, C, N, temp );
}//end of else
}
/*main */
int main()
{
node *header = CreateNode();
header>data = root>data;
header>left = header>right = NULL;
Traversal( root, NULL, Header, NULL );
/* move header pointer to first node in double linked list */
while( header>left != NULL )
{
header = header>left ;
}
/* node header pointed linked list contains required output */
}

siva.sai.2020
March 11, 2011 @anonymous, I compiled and tested your Stackoverflow code and it works fine. This very very good answer.
int main()
{
int B[] = {1,1,1,3,3,3,20,4,4,4};
int ones = 0 ;
int twos = 0 ;
int not_threes;
int x ;
for( i=0; i< 10; i++ )
{
x = B[i];
twos = ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}
printf("\n unique element = %d \n", ones );
return 0;
}

siva.sai.2020
March 09, 2011 I will post pseudo code later
 siva.sai.2020 March 07, 2011We can solve this problem in O(n^2).
I will explain this problem with example.
Example: A[] = { 1,3,8,2,4,5,6,7};
step 1: sort Array A[] = {1,2,3,4,5,6,7,8};
step 2: assume T = 10 ( given sum in problem statement )
step 3: output triplets
{1,2,7}
{1,3,6}
{1,4,5}
{2,3,5}
step 4: below I wrote psuedo code for this problem.
In below code I took 3 pointers i,j,k.
 i points to first value in triplet
 j points to 3rd value in triplet
 k points to 2nd value in triplet
Pseudo code
void tripletSum(int A[], int n, int TripletSum )
{
}

siva.sai.2020
March 07, 2011 I think, we can this problem by using MAX HEAP.
1. array A[n] is given two you. We know size of array i.e n
2. Two Split arrays S1[n1] S2[n2] . here n1, n2 are sizes of split arrays.
3. Construct MAX HEAP by using A[n] elements.
4. for each i =MaxHeapElement() // for all n elements
if ( SUM(S1) > SUM(s2) )
{
add i to S2[]
n2++;
}
else
{
add i to S1[] ;
n1++;
}
5. n1 + n2 == n .
6. SUM(S1) ~= SUM(S2) ;
7. Time complexity O(nlogn)
Open Chat in New Window
by using stack, we can check whether parenthesis are matched or not. Same algo we can use to check the above valid math expression.
 siva.sai.2020 April 21, 2012Does any one has idea to solve short cut expression problems.
e.g :: (a+ (b+=c)) // valid
(a+(b=+c)) // invalid