siva.sai.2020
BAN USER- 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 | PURGE
Amazon SDE-2 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 | PURGE
Google - 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 | PURGE
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 | PURGE
SDE1 Algorithm - 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 | PURGE
Google SDE-2 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 | PURGE
Google SDE-2 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 | PURGE
optum SDE-2 - 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 | PURGE
SDE-2 - 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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
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 | PURGE
Amazon Software Engineer / Developer Data Structures - 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 | PURGE
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 | PURGE
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 | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersI appeared for the Amazon( Bangalore) Interview on 05-Feb-2011. I cleared written test. After that I gave 3 rounds of interview.
- siva.sai.2020
Note: They are going conduct interviews on 13-Feb-2011 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 | PURGE
Amazon Software Engineer / Developer Algorithm - 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 | PURGE
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 | PURGE
Amazon Software Engineer / Developer - 2of 2 votes
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) A-successor = 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 | PURGE
Amazon Software Engineer / Developer
good Solution.
- siva.sai.2020 March 04, 2011@Tulley, truly great solution.
- siva.sai.2020 March 04, 20111. please find my code below. it is compiled and executable code.
2. API: int IsGreater(int a, int b) takes two integers.
return 1 if a > b ( i.e a's value is lexicographically greater than b's value )
return 0 if a > b ( i.e a's value is lexicographically less than b's value )
Example 1: a = 8, b=89 then a < b
Exmaple 2: a = 7, b = 76 then a > b
Example 3: a=7 b=778 then a<b
3. I used selection sort to sort the array lexicographically.
4. I am achiebing lexicographical order by using IsGreater() API.
5. Time complexity O(n^2);
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void reverse(char *str,int len) {
int i=0;
char ch;
for(i=0;i<=(len-1)/2;i++) {
ch=str[i];
str[i]=str[len-1-i];
str[len-1-i]=ch;
}
}
char* itoa(int number) {
char *str= (char * ) malloc(sizeof(char)*20);
int negFlag=0,pos=0;
if(number<0) {
negFlag=1;
number=-number;
}
while(number>0) {
str[pos++]='0'+number%10;
number=number/10;
}
if(negFlag) {
str[pos++]='-';
}
str[pos]='\0';
reverse(str,pos);
return str;
}
int IsGreater(int a, int b)
{
char *str1 = itoa( a ) ;
char *str2 = itoa( b ) ;
int len1 = strlen(str1);
int len2 = strlen(str2);
// printf("\n str1 = %s str2 = %s \n", str1, str2 );
int i =0;
int j =0;
while( i< len1 && i < len2 )
{
if( str1[i] > str2[i] )
{
return 1;
}
else if( str1[i] < str2[i] )
{
return 0;
}
else
{
i++;
}
}
j = i;
i--;
while( j< len1 || j < len2 )
{
if( len1 < len2 )
{
if( str1[i] > str2[j] )
{
return 1;
}
else if( str1[i] < str2[j] )
{
return 0;
}
else
{
j++;
}
}
else
{
if( str1[j] > str2[i] )
{
return 1;
}
else if( str1[j] < str2[i] )
{
return 0;
}
else
{
j++;
}
}
} // end of while
}
void Swap( int data[], int i, int j )
{
if( i != j)
{
data[i] = data[i] ^ data[j] ;
data[j] = data[i] ^ data[j] ;
data[i] = data[i] ^ data[j] ;
}
}
int main()
{
int data[] = {4,94, 9,14,1,8,89,7,76,778} ;
int data_size = sizeof(data) / sizeof(int) ;
int i = 0;
int j;
int max_index;
while( i < data_size )
printf("\t %d , ", data[i++] );
printf("\n \n ");
/* Selection Descending order sort */
for( i = 0 ; i < data_size ; i++ )
{
max_index = i;
for( j= data_size ; j > i ; j-- )
{
if( IsGreater( data[j], data[max_index] ))
{
// printf("\n j = %d max_index = %d \n", j, max_index );
max_index = j;
}
}
Swap( data, max_index, i );
}
i = 0;
while( i < data_size )
printf("\t %d , ", data[i++] );
return 0;
}
I think, killing system process is good answer
- siva.sai.2020 March 02, 20111) By using recursion we can solve this p0roblem
2) create 3 circular linked lists . one is for left sub tree , second one is for right sub tree, and 3rd one for root node it self.
3)Now just merge above 3 circular lists.
Code for this problem
typedef struct node
{
int data;
struct node *left;
struct node *right;
}tnode;
tNode * AppendLists ( tNode *h1, tNode *h2 )
{
if( h1 == NULL )
{
return h2;
}
else if( h2 == NULL )
{
return h1;
}
else
{
tNode *temp;
temp = h1->left;
h1->left = h2->left;
temp->right = h2;
h2->left->right = h1;
h2->left = temp;
return h1;
}
} // Endo of APPendLists
tNode * TreeToList( tNode *root)
{
if( root == NULL )
{
return NULL;
}
else
{
tNode *l1, *l2 ;
l1 = root->left;
l2 = root->right;
root->left = root->right = root ;
l1 = TreeToList( l1 );
l1 = AppendLists( l1, root );
l2 = TreeToList( l2 );
l1 = AppendLists(l1, l2 );
return l1;
}
}
S1, S2 , S3 ... are students
case 1) if n == 1, then number of possibilities
1
case 2) if n==2 ( two students S1 and S2 ), then number of possibilities
3
---------
S1 S2
1 1
1 2
2 1
---------
case 3) Three students S1, S2, S3
number of possibilities 13.
S1 S2 S3
1 1 1
1 1 2
1 2 1
2 1 1
1 2 2
2 1 2
2 2 1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
-----------
Code for this problem
// 'n' is number of students.
long int NumWays(int n)
{
if( n < 0 )
{
return -1; //error
}
else if( n <= 1)
{
return 1;
}
else
{
int i =1;
long sum = 0;
while ( i <= n )
{
sum + = Combinations( n, i ) * NumWays( n - i );
i++ ;
}
return sum;
}
}
// combinations function
long int Combinations( int n, int k )
{
// here this API returns nCk i.e ( n! /((n-k)! * k! );
return nCk;
}
Interviewer told me, we can solve this problem in two ways 1. Brute force 2. Dynamic programming . After that he explained Brute Force method .
- siva.sai.2020 February 18, 2011He told me, we can solve this problem in two ways 1. Brute force 2. Dynamic programming . After that he explained Brute Force method .
- siva.sai.2020 February 18, 2011I corrected the code . Now it is proper
- siva.sai.2020 February 17, 20111. I could not answer this question. Interviewer explained me the possible answer.
2. str1[] length is n
str2[] length is m
3. find all combinations of str1 i.e 2^n .
e.g 1) n = 2 , str1 = "AB"
possible combinations { "","A", "B","AB" }
total 4 combinationsi.e 2^2
e.g 2) n=3, str1 ="ABC"
Possible combinations {"","A","B","C","AB","AC","BC","ABC" } .
total 8 combinationsi.e 2^3
4. find all combinations of str2 i.e 2^m .
5. now have to match each str1 combination with str2 combination .
If it matches and greater than Previous matched string length, then store it as a best match. Otherwise goto next match.
6. Time complecxity O(2^n * 2^m) = O(2^(m+n) )
1. For binary tree, node structure will be
struct node
{
int data;
struct node *left;
struct node *right;
}
2. But our special tree is not Binary Tree .
3. A is a tree root node and it can have ZERO to INFINITY childrens.
Let us assume B, C, D, E,F,G are childrens of A.
4. Now B can have any number childrens . similarly Other children nodes also.
5. diagram representation of tree
A
/ / / | \ \ \
B C D E F G H
//|
X Y Z ...
4. My answer
struct node
{
int data;
struct node *child;
struct node *sibling;
};
6. Traversal code
void PreOrderTraversal( struct node * root )
{
if( root == NULL )
{
return NULL;
}
else
{
printf(" %d \t", root->data );
PreOrderTraversal(root->child);
PreOrderTraversal(root->sibling);
}
}
1. Generally in BinarySearch algorithm we do 2 comparisions
while(stat < end )
{
if( A[mid == KeyElem )
{
-----
}
else if( A[mid] < KeyElem )
{
------
}
else
{
----
}
------
}// end of While
2. He asked me to use single comparision in While loop .
3. code for this .
int BinSearch(int A[], int n , int key )
{
if( n <= 0 )
{
return -1; // key not found
}
else
{
int start = 0 ;
int end = n - 1;
int mid;
while(start < end)
{
mid = (start + end) / 2 ;
if( A[mid] > key )
{
start = mid + 1;
}
else
{
end = mid ;
}
}
if( ( start == end ) && ( A[start] == key ))
{
return start;
}
else
{
return -1; // key not found
}
}
}
My answer :
1. { inorder, postorder} or {inorder, preorder }
2. I think {inorder, level order } is also a answer
1. By using recursion , we can solve this problem.
2. You need two Arrays one is Permuted array P[] which stores permutation numbers.
second Array is Presence Arraya Presence[] which tells whether a particular number is already included in P[] or not .
3. Compiled and tested Code for this.
#include<stdio.h>
#define TRUE 1
#define FALSE 0
void PrintArray(int *P, int n)
{
int i=0;
while(i<n)
{
printf(" %d , ", P[i] );
i++;
}
printf("\n");
}
/*
int P[]: Permutation Array which stores numbers permutation
int Presence[]: it store either 0 or 1 for all numbers 1 - n .
if Presence[i] == 1, i'th number already there in P[] array.
So we will not include that number again.
int Count: tells so far how many numbers included in Permuted Array.
*/
void Permutations(int *P, int *Presence, int n, int count )
{
if( count >= n || n <= 0)
{
return;
}
else
{
int i = 1;
while(i <= n)
{
if( Presence[i] != TRUE )
{
Presence[i] = TRUE;
P[count] = i;
if( count + 1 == n )
{
PrintArray(P,n); // Print all elements in P[]
}
else
{
Permutations(P, Presence, n, count + 1 );
}
Presence[i] = FALSE;
}
i++;
}
}
}
int main()
{
int n = 5; // 1 to 10 numbers ermutations
int P[n] ; // Permutation Array, which store numbers permutation
int Presence[n]; // it store either 0 or 1 for all numbers 1 - n
int i =0;
/* Intializing arrays */
while( i < n )
{
P[i] = Presence[i] = 0;
i++;
}
Permutations(P, Presence, n, 0 );
return 0;
}
Is there any other better way ?
- siva.sai.2020 February 17, 20111. Quick sort Avg O(nlogn), best O(n^2)
void swap(int a, int b )
{
if( a != b )
{
a = a ^ b ;
b = a ^ b ;
a = a ^ b ;
}
}
int Partition(int A[], int start, int end)
{
int pivot ; // pivot element
int le; // Left end index
int re; // right end index
pivot = A[start];
le = start + 1;
re = end;
while( le < re )
{
while( A[le] < pivot )
le++;
while( A[re] < pivot )
re--;
if( le < re)
swap( A[le], A[re] );
}
swap(A[le], pivot );
return le;
}
void QuickSort(int A[], int start, int end )
{
if( start >= end )
{
return;
}
int pivotIndex = Partition( A , start, end );
QuickSort( A, start, pivotIndex-1 );
QuickSort( A, pivotIndex+1, end );
}
In case if find any bug in my code please let me know ?
- siva.sai.2020 February 17, 2011My answer:
First sub question answer :
i = 0 ;
while (i < n )
{
fork();
printf("\n SIVA");
i++;
}
1) if n > 0, 2^n + 2^n-1 + .... 2^1
Second sub question answer :
i = 0 ;
while (i < n )
{
printf("\n SIVA");
fork();
i++;
}
2) if n > 0, 2^n-1 + 2^n-2 + ... + 2^0
1. Multi Thread management is easier than Multi Process management. So prefer multi threading in our applications.
2. Creating thread and Destroying thread are costly( CPU spends more time ) operations . So we maintain pool of threads.
3. I think almost all Server side products use Thread Poool or Connection Pool.
4. When ever server receives new request from a client , it assign that request to one of the thread in thread pool. this particular thread is responsible for that connection. Once that thread done with client operation, it back to ThreadPool.
5. If someone is interested, I wrote Threadpool example code but it is 400 Lines of code . So I am not pasting entire code in this comment. Click below links if you interested about Thread code.
6. Server side example
codepad.org/9pkMIpjR
7. Client side example
codepad.org/VQ8GKBS8
8. I have tested both server side and client programs
My answer :
#include<stdio.h>
#include<stdlib.h>
#include<fcntl.h>
#define BUF_SIZE 100
void mycp(const char *SourceFile, const char *DestFile )
{
int SFD; // source file Descriptor
int DFD; // Destination File Descriptor
int rb ; // read bytes
int wb ; // write bytes
char buf[BUF_SIZE];// Buffer to read and write
if( (SFD = open(SourceFile, O_RDONLY )) == -1 )
{
perror("open() : ");
exit(0);
}
if( (DFD = open(DestFile, O_WRONLY | O_CREAT )) == -1 )
{
perror("open() : ");
exit(0);
}
while( ( rb = read( SFD, buf, BUF_SIZE )) > 0 )
{
wb = write(DFD, buf, rb );
if( rb != wb )
{
perror(" write ");
exit(0);
}
}
Close(SFD);
Close(DFD);
}
int main(int argc, char **argv)
{
if( argc < 3)
{
printf("\n Usage: $mycp Sourcefile Destfile ");
exit(0);
}
mycp( argv[1], argv[2] );
return 0;
}
$ Mycp SourceFile DestFile
Is there any other better way ?
/* Iterative Single linked list reverse */
typedef struct node{
int data;
struct node *next;
}mynode;
/*
Input: Header node of the Single linked list
OutPut: Header node of the Reversed Linked list
*/
mynode * Reverse( mynode * head )
{
if( head == NULL || head->next == NULL )
{
return head;
}
else
{
mynode *P, *Q, *R;
P = head;
Q = head->next;
/* Head become tail node in Reverse list */
P->next = NULL;
while( Q != NULL )
{
R = Q->next;
Q->next = P;
P = Q;
Q = R;
}
return P;
}
}
I used 3 temporary variables P,Q and R, can we reduce temporary variables ?
- siva.sai.2020 February 17, 2011magma-da.com
- siva.sai.2020 February 17, 2011you selected for Amazon Bangalore ?
- siva.sai.2020 February 09, 2011>>
1) where string literal i.e "SIVA" will be stored ( heap , stack, data or code segments) in above both cases.
str - code segment
str1 - stack
>>
str points to Read only data sigment
>>
1. code segment (read only)
>>
wrong.
Read only data segment is correct answer .
>>
strings - convert to int assuming base 26
objects - convert to int base 128 and then mod(you can also consider only allowed objects)
>>
I don't understand , why you are using "base 26" and "base 128" ?
I spent 30 min to understand k-d tree but I couldn't.
- siva.sai.2020 February 09, 2011without using extra space, we have to find missing number.
- siva.sai.2020 February 09, 2011@Code saviour, great answer
- siva.sai.2020 February 09, 2011Great answer
- siva.sai.2020 February 09, 2011yes
- siva.sai.2020 February 09, 2011Great answer.
- siva.sai.2020 February 08, 2011@ gekko gordan, Yes correct, We can do it with one hash table . Thansk for correction .
- siva.sai.2020 January 20, 20111. 3 digits sum minimum, MIN_SUM = 0
2. 3 digits dum Maximum , MAX_SUM = 27
3. let us take an Array A[10] = {0,1,2,3,4,5,6,7,8,9}
4. for Each sum From MIN_SUM to MAX_SUM
find all 3 -digit combinations which gives above sum .
/* program to find no of lottery tickets */
void Sum( int *A, int i, int digit, int *count, int Psum, int sum )
{
if( digit <= 0 || psum > sum || i >= 10 )
{
return;
}
else if (psum == sum )
{
*count += 1;
return;
}
else
{
sum( A, i, digit-1, count, sum, psum + A[i] ) ;
sum( A, i+1, digit-1, count, sum, psum + A[i] ) ;
sum( A, i, digit, count, sum, psum ) ;
}
}
int main()
{
long int count=0;
long int CumulativeSum = 0;
int i = 0;
for( i = 0; i<= 27 ; i++ )
{
count = 0;
sum(A, 0, 3, &count, i, 0 );
CumulativeSum += *count ;
}
printf(" Totla number of combinations = %l \n", CumulativeSum );
return;
}
Incase , if you find any bug, please let me know.
- siva.sai.2020 January 19, 20111. We have to use TWO hash tables and ONE Double linked list .
2. Time complexity O(1) to add a number and delete a number.
Approach:
1. Store numbers in double linked list. Highest frequency number first node and least frequency number last node .
number frequency
5 2
4 3
3 1
2 10
2) linked list looks :
I don't know how to represent double linked list diagrammatically, so in below example i am using single linked list .
2->4->5->3
3) now THREE times you added 3 , then linked list becomes
2->3->4->5
4) to make above node swapping in O(1) time complexity you can use hashing technique.
Hash table1:
number | Frequency
-------------------
|
|
Hash table 2:
Frequency | First node | Last node
-------------------------------------
| |
| |
5) From First hash table you can get number frequemncy and by using frequency on second Hash table you can get Linked list location where you to insert node.
6) I know above explanation bit confusing. I could not showed my solution properly in diagrammetic way .
7) My solution works O(1) time complexity.
8) Space complexity: O(n) + Hash tables space O(1)
yes, you are correct. Thanks for correction
- siva.sai.2020 December 17, 2010L1: 1->2->3->4->5
L2: 6->7->8->9->10
P is pointer on L1 and q is a pointer on L2. r is temp pointer .
Resultant list L: 1->6->2->7->3->8->4->9->5->10
=====================================
Hello Sir, can you merge two lists without using third pointer ?
If you use HASH, you need to take care about collisions. In the question, they mentioned very large file, so you will get too many hash collisions even if you use good hash function.
We better to use HASHing when your data size low to medium. If data is large, better to use TRIE.
good solution
- siva.sai.2020 December 15, 2010TRIE is suitable for both a) and c)
a) search in dictiorry
c) typing prefix of a valid string suggests valid words
---------
Hash table is suitable for
b) given a string find all valid anagrams in a dictionary
---------
so we need TRIE + HASH data stractures to satisfy all operations
/* 52-bit mask i.e 2-bit for each character from 'a' to 'z' */
/* 0,1st bits for 'a'. 2,3rd bits for 'b' ... */
/* if two bits are 1 for a character , then character is repeated */
void FindRepeartedCharacters(char *S)
{
if( S == NULL )
return ;
else
{
int len = strlen(S);
int i=0;
int MASK:52 = 0; // bit-filed
while(i < len -1 )
{
if ( alpha(S[i] )
{
if( S[i] >= 'A' && S[i]<='Z')
{
S[i] = lower(S[i]);
}
if( MASK & (1<< (S[i] - 'a')*2) )
{
MASK | = 1<< ((S[i] - 'a')*2 + 1 ) ;
}
else
{
MASK | = 1<< (S[i] - 'a')*2 ;
}
}
else
{
printf("\n wrong input ");
exit(0);
}
i++;
}// end of while
i=0;
while(i<26)
{
if( (MASK & 1<<2*i) && (MASK & 1<<(2*i + 1) ) )
{
printf("\n %c is repeated \n", i + 'a' );
}
}
}
}
If you find any bug in my code , please let me know
- siva.sai.2020 December 15, 2010/* 26-bit mask i.e 1-bit for each character from 'a' to 'z' */
void FindRepeartedCharacters(char *S)
{
if( S == NULL )
return ;
else
{
int len = strlen(S);
int i=0;
int MASK:26 = 0; // bit-filed
while(i < len -1 )
{
if ( alpha(S[i] )
{
if( S[i] >= 'A' && S[i]<='Z')
{
S[i] = lower(S[i]);
}
if( MASK & (1<< (S[i] - 'a')) )
{
printf("\n %c is repeated", S[i]);
}
else
{
MASK | = 1<< (S[i] - 'a') ;
}
}
else
{
printf("\n wrong input ");
exit(0);
}
i++;
}
}
}
/* Reverse of every K nodes in Single Linked list */
void reverse(node * head, node ** end1, node **end2, int n, int K)
{
if( head == NUL)
{
return NULL;
}
else if( head->next == NULL)
{
*end1 = NULL;
}
else
{
reverse(head, end1, end2, n+1, K);
if( n%K == 0)
{
head->next->next = head;
head->next = end2;
end2 = end1;
}
else if( n% K == K-1)
{
end1 = head;
}
else
{
head->next->next = head;
}
}
}
node * Reverse_K_nodes(node *head, int K)
{
node *end1=NULL,*end2=NULL;
reverse(head, &end1, &end2, 0, K)
return end2;
}
int main()
{
head = Reverse_K_nodes(head, K );
}
Time Complexity O(n) & Space complexity O(1).
If you find any bug please let me know.
/* intersection of linked lists */
node * Intersection( node * L1, node * L2 )
{
if( L1 == NULL )
return L2;
else if( L2 == NULL )
return L1
else
{
node *p=L1, *q=L2;
int m=0, n=0;
/* calculate L1 list size */
while ( p != NULL )
{
p = p->next;
m++;
}
/* calculate L2 list size */
while ( q != NULL )
{
q = q->next;
n++;
}
p = L1;
q= L2;
/* if L1 list bigger in size, forward p pointer, else forward L2 list pointer q till both L1 & L2 no. of untraversed nodes same*/
while (m != n )
{
if( m > n)
{
p = p->next;
m--;
}
else
{
q=q->next;
n--;
}
}
/* this while loop exits when it finds common node in two lists L1 & L2, or lists end */
while( p!=q )
{
p=p->next;
q=q->next;
}
return p;
}
}
/* merging two linked lists */
node * Merge( node * L1, node * L2 )
{
if( L1 == NULL )
return L2;
else if( L2 == NULL )
return L1
else
{
node *p=L1, *q=L2, *r;
while( p->next!= NULL && q!=NULL)
{
r = p->next;
p->next = q;
p = q;
q = r;
}
if( p->next == NULL )
{
p->next = q;
}
return L1;
}
}
good answer
- siva.sai.2020 December 15, 2010very good answer
- siva.sai.2020 December 15, 2010@Ram, good job
- siva.sai.2020 December 15, 2010Your code takes O(n2) which is not acceptable at all . I think Interviewer looking for O(n) solution.
- siva.sai.2020 December 14, 2010int main()
{
char str[] = {'a','b','d','c','d','f','s','\0'}, *sortOrder = "dacg", ch;
int i=0, j=0, k=0, count[256];
printf("\n %s", str);
for(; i<256;i++)
{
count[i] = 0;
}
for(i=0; (ch = str[i])!= '\0'; i++)
count[ch] +=1;
for( i=0; (ch= sortOrder[i])!= '\0'; i++)
{
for(j=0; j < count[ch]; j++)
str[k++] = ch;
count[ch] = 0;
}
for(i=0; i<256; i++)
{
if( count[i] != 0 )
{
for(j=0; j < count[i]; j++)
str[k++] = i;
count[i] = 0;
}
}
str[k] = '\0';
printf("\n %s", str);
return 0;
}
TRIE should help us to solve problem in O(n).
- siva.sai.2020 December 14, 2010
RepJennyReimer, Dev Lead at Adobe
Badminton lover, coffee addict, guitarist, International Swiss style practitioner and TDC honorary member. Acting at the nexus of simplicity and ...
Repallisonepollard, Applications Developer at Accenture
I am Allison from Germantown. I work as a Staff manager at The LawnGuru company. But my interest in blogging ...
Reparlinenwalters, Software Analyst at ASAPInfosystemsPvtLtd
I Performed extensive web research to collect pertinent data and gather images related to the assigned articleIts act of writing ...
Repjunehudson, Associate at Advisory Board Company
I am passionate about fashion and love to explore black magic to take revenge.Being a fashion designer involves more ...
RepSoccer lover, coffee addict, guitarist, International Swiss style practitioner and TDC honorary member. Acting at the nexus of simplicity and ...
RepHi, I am Anne from Portsmouth, USA. I have been working as a freelance digital illustrator specialized in 3D character ...
If array contains duplicate elements then we need to take extra care.
- siva.sai.2020 March 04, 2011Example:
A[] = {1,1,1,1,1,1,1}
B[] = {1,2,3}
here big array is A[] with respect number elements.
But if consider distinct elements, then B[] is big array