- There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). Full points are given for the solution bearing efficiency O(log n). Partial points for the efficiency O(n).
- Given a string *Str of ASCII characters, write the pseudo code to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed) . Extend your algorithm to remove duplicates in the string which consisted of UNICODE characters.
- Given that, there are 2 linked lists L1 and L2. The algorithm finds the intersection of the two linked lists. i.e' "L1 intersection L2 " ( similar to intersection of 2 sets ). Write all the possible test cases involved in the above given problem.
Microsoft Written Test Questions
Microsoft visited our campus for recruitment. Here are the 3 questions asked for us in written round. Unfortunately, i couldn't clear the written round. Anyone, please post the answers if you know them.
Subscribe to:
Post Comments (Atom)
The median can be obtained recursively as follows. Pick the median
ReplyDeleteof the sorted array A. This is just O(1) time as median is the n/2th
element in the sorted array. Now compare the median of A, call is
a with median of B, b. We have two cases.
• a < b : In this case, the elements in B[n
2 · · · n] are also
greater than a. So the median cannot lie in either A[1 · · · n
2 ]
or B[n
2 · · · n]. So we can just throw these away and recursively
solve a subproblem with A[n
2 · · · n] and B[1 · · · n
2 ].
• a > b : In this case, we can still throw away B[1 · · · n
2 ] and
also A[n
2 · · · n] and solve a smaller subproblem recursively.
In either case, our subproblem size reduces by a factor of half and
we spend only constant time to compare the medians of A and B.
So the recurrence relation would be T(n) = T(n/2) + O(1) which
has a solution T(n) = O(log n).
Anantharam: "Now compare the median of A, call is
Deletea with median of B, b . We have two cases."
There are 3 cases, not 2 -
1. a < b
2. a > b
3. a = b
case a = b:
Deletea is the median of the 2 lists.
Great Article Artificial Intelligence Projects
DeleteProject Center in Chennai
JavaScript Training in Chennai
JavaScript Training in Chennai
2.
ReplyDeletemain()
{
char *str = "Potato";
char *temp,*cur,*loop;
temp = str;
cur = temp;
int flag;
while (*cur !='\0')
{
loop = str;
flag =0;
while(loop<=temp)
{
if(*loop == *cur)
{
flag = 1;
break;
}
loop++;
}
if (flag ==0)
{
temp++;
str[temp-str]=*cur;
}
cur++;
}
temp++;
str[temp-str]='\0';
printf("\n\n %s",str);
}
This comment has been removed by the author.
ReplyDeleteint mergeStep(int * & a, int * aEnd, int * & b, int * bEnd) {
ReplyDeleteif (a == aEnd) {
return *b++;
}
if (b == bEnd) {
return *a++;
}
if (a < aEnd && b < bEnd) {
return (*a < *b) ? *(a++) : *(b++);
}
throw runtime_error("can't progress merge");
}
/*
* O(size) solution.
*/
double findMedianLinear(int * a, int * b, int size) {
int * aEnd = a + size, * bEnd = b + size;
for (int i = 0; i < size - 1; i++ ) {
mergeStep(a, aEnd, b, bEnd);
}
return (mergeStep(a, aEnd, b, bEnd) + mergeStep(a, aEnd, b, bEnd)) / 2.0;
}
anantharam,
ReplyDeletecould you explain how your algorithm of finding. will work on the following input:
a = {1, 3};
b = {2, 2);
I forgot the case a (median of list 1) = b (median of list 2), in that case median is-> (max(a[n/2],b[n/2]) + min(a[n/2+1],b[n/2+1])/2
DeleteHence in this problem-> median of list a = 2 = median of list b = 2.
(max(1,2) + min(3,2))/2 = (2+2)/2 = 2
double findMedianLog(int * a, int * b, int size) {
ReplyDeleteint m1 = a[size / 2];
int m2 = b[size / 2];
if (size == 2) {
return (max(a[0], b[0]) + min(a[1], b[1])) / 2;
}
if (m1 < m2) {
return findMedianLog(a + size / 2, b, size - size / 2);
}
return findMedianLog(b + size / 2, a, size - size / 2);
}
For 1st qns think on these lines for a logn algorithm:
ReplyDeletecompare the medians of both arrays (in O(1) since it is sorted). The problem size will be reduced to n elements by this single comparison. Then continue
main()
ReplyDelete{
char *str = "abababababcdefefefefefegyuiopl";
char *p = str;
char *q = p + 1;
char *check = str;
while (*p != '\0')
{
if (*q == '\0')
{
p++;
q = p + 1;
}
while (( *q != *p ) && (*q != '\0'))
q++;
if (*p == *q)
{
check = q + 1;
if (*check == '\0')
*q ='\0';
strcpy(q,check);
q = p + 1;
}
}
printf ("\n%s",str);
}
For Question 2:
ReplyDelete* Arrays
* Articles
* Bit Magic
* C/C++ Puzzles
* GFacts
* Linked Lists
* MCQ
* Misc
* Output
* Strings
* Trees
Print all the duplicates in the input string.
March 22, 2009
Write an efficient C program to print all the duplicates and their counts in the input string
Algorithm: Let input string be “geeksforgeeks”
1: Construct character count array from the input string.
count['e'] = 4
count['g'] = 2
count['k'] = 2
……
2: Print all the indexes from the constructed array which have value greater than 0.
Solution
view source
print?
# include
# include
# define NO_OF_CHARS 256
/* Returns an array of size 256 containg count
of characters in the passed char array */
int *getCharCountArray(char *str)
{
int *count = (int *)calloc(sizeof(int), NO_OF_CHARS);
int i;
for (i = 0; *(str+i); i++)
count[*(str+i)]++;
return count;
}
/* Print duplicates present in the passed string */
void printDups(char *str)
{
int *count = getCharCountArray(str);
int i;
char temp;
for (i = 0; i < NO_OF_CHARS; i++)
if(count[i] > 1)
printf("%c, count = %d \n", i, count[i]);
}
/* Driver program to test to pront printDups*/
int main()
{
char str[] = "test string";
printDups(str);
getchar();
return 0;
}
NOTE: Copied from geeksforgeeks.org site....
char *remove_duplicates(char *str)
ReplyDelete{
char *str1, *str2;
if(!str)
return str;
str1 = str2 = str;
while(*str2)
{
if(strchr(str, *str2)<str2)
{
str2++;
continue;
}
*str1++ = *str2++;
}
*str1 = '\0';
return str;
}
Can anyone please give the solution for the last problem.
ReplyDeletechar * remove_dup_chars(char *str)
ReplyDelete{
int len=strlen(str);
char *tmp=str,*tmp2=str;
int hole=0;
while(tmp && *tmp!='\0') {
hole=0;
tmp2=(tmp+1);
while(tmp2 && *tmp2!='\0') {
if(!hole && *tmp2==*tmp) {
hole=1;
}
if(hole) {
while(*(tmp2+hole) == *tmp) {
hole++;
}
*tmp2=*(tmp2+hole);
}
tmp2++;
}
tmp++;
}
return str;
}
int main()
{
char a[]="abcdabedaaabcf";
printf("orig:%s\n",a);
printf("after rem dup:%s\n",remove_dup_chars(a));
memcpy(a,"Potato",strlen("Potato")+1);
printf("orig:%s\n",a);
printf("after rem dup:%s\n",remove_dup_chars(a));
return 0;
}
int main()
ReplyDelete{
char str[]="ababdfdfhjiab";
char *ptr;
int i;
printf("\n %s ",str);
for(i=0;i<strlen(str)-1;i++)
{
for(ptr=&str[i+1];*ptr!='\0';ptr++)
{
if(*ptr==str[i])
strcpy(ptr,ptr+1);
}
}
printf("\n %s ",str);
}
for the first question the method is very easy actually:
ReplyDeletewe can do it using a recursive function:
find the median of both the arrays:
suppose m1 is the median of the first array
m2 is the median of the second array
then if m1 > m2 then again call that recursive function in the right part of the second array and in the left part of the first array.
continue this step until the number of elements in the array is not two
when the number of elements in both the arrays are two then do the following:
suppose in the first array the elements are :
f1 f2
and in the second the elements are
s1 s2
then if
f1 < s2
return (f2+s1)/2
else
return (f1+s2)/2
#include
ReplyDelete#include
#include
main(){
char s[100] = "aabcdeefgghijjkllllmnooo";
int l = strlen(s);
int i;
int count[226] = {0};
for(i=0;i1){
count[s[i]] = -1;
i++;
}
else if(count[s[i]]==-1){
int j;
for(j=i+1;j<l;j++){
s[j-1] = s[j];
}
l--;
}
else
i++;
}
s[l] = '\0';
printf("%s\n",s);
system("pause");
}
visit geeks for geeks.org
ReplyDeleteabe yaad kaise nahi rehta be gadhe aadhe question post kerta hai........... bhak
ReplyDeletesorry be faaltu me maarli....galat samjha tha tujhe tu bahut achha insaan haibe....
ReplyDeleteIN 2nd question it is given no extra data structure should be used (IN place).so can we use extra 256 size array as hash table
ReplyDeleteThis section covers HR Interview Questions & Answers for fresher’s and experienced. It helps job seekers who are about to attend HR interview round. Please go through each question to find out a number of sample answers.
ReplyDeleteClick On any question to find out a variety of sample answers:
Tips On Personality Development.
1) Sample Answers - Tell Me Something About Yourself.
2) Sample Answers - What Are Your Strengths?
3) Sample Answers - What Are Your Weaknesses?
4) Sample Answers - Can You Work Well Under Pressure Or deadlines?
5) Sample Answers - What Are Your Short Term Goals?
6) Sample Answers - What Are Your Long Term Goals?
7) Sample Answers - Where Do You See yourself After Five Years?
8) Sample Answers - Why Should We Hire You?
9) Sample Answers - What Kind Of Salary Are You Looking For?
10) Sample Answers - Why Do You Want To Leave Your Current Job/Organization/Company?
Hi
ReplyDeleteI read this post two times.
I like it so much, please try to keep posting.
Let me introduce other material that may be good for our community.
Source: Computer programmer interview questions
Best regards
Henry
// code for question 1 : median.c
ReplyDelete// Prem Raj... IITJ
#include
#include
void median(int* p1,int* p2,int* p3,int* p4);
int a[5] = {1,2,3,5,6};
int b[5] = {6,7,8,9,10};
int main()
{
int i=0,j=4,k=0,l=4;
median(&i,&j,&k,&l);
printf("Median is %d and %d\n",a[i],b[k]);
return 0;
}
void median(int* i,int* j,int* k,int* l){
int n1,n2,x;
if(*i > *j || *k > *l)
{
printf("Invalid array\n");
exit(0);
}
if(*i == *j)
{
return;
}
if(*i == *j-1)
{
if(a[*i]>b[*k])
{
if(a[*j]b[*l])
a[*j] = b[*l];
*i = *j;
*l = *k;
}
}
n1 = (*i+*j)/2;
n2 = (*k+*l)/2;
x = (*j-*i+1)%2;
if(a[n1] > b[n2])
{
if(x==0)
{*j = n1+1;
*k = n2;}
else
{*j = n1;
*k=n2;}
}
else
{
if(x==0)
{*l=n2+1;
*i=n1;}
else
{*l=n2;
*i=n1;}
}
median(i,j,k,l);
}
Thank you for such a wonderful Information !!
ReplyDeleteHere is a list of Top LINUX INTERVIEW QUESTIONS
Veritas Cluster Interview Questions
SAMBA Server Interview Questions
Linux FTP vsftpd Interview Questions
SSH Interview Questions
Apache Interview Questions
Nagios Interview questions
IPTABLES Interview Questions
Ldap Server Interview Questions
LVM Interview questions
Sendmail Server Interview Questions
YUM Interview Questions
NFS Interview Questions
Read More at :- Linux Troubleshooting
Great and Useful Article.
ReplyDeleteJava Online Training
Online Java Course
Java Course Online
J2EE training
online J2EE training
Best Recommended books for Spring framework
Java Interview Questions
Java Training Institutes in Chennai
Java Training in Chennai
J2EE Training in Chennai
java j2ee training institutes in chennai
Java Course in Chennai
Check this one...Java Interview Questions
ReplyDeleteLing
Nice posting..
ReplyDeleteVmware Training in Chennai
CCNA Training in Chennai
Angularjs Training in Chennai
Google CLoud Training in Chennai
Red Hat Training in Chennai
Linux Training in Chennai
Rhce Training in Chennai
Nice Information,
ReplyDeleteThanks For Sharing..
create your professional video resume online
digital jobseeker services