vgeek
BAN USER- 0of 0 votes
AnswersYou are required to parse the xml file:
- vgeek in United States
<ledger>
<person>
<name>Jai</name><location>Bangalore</location>
</person>
<entries>
<entry><day>1</day><credit>50</credit><debit>40</debit></entry>
….
…
multiple entries were there, and multiple people were there.
We were required to validate the XML file.Open and Close tags matching.
We were required to parse, maintain the max balance for each person, the longest span of days each person had the max balance, and report queries such as who had the overall max balance , his span and location. Span must contain the day numbers, not length.| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer - 0of 2 votes
AnswersConvert a base 2 number to a base 4 number
- vgeek in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - -1of 1 vote
AnswersI have heard this question many times in microsoft interviews. Given two arrays find the intersection of those two arrays. Besides using hash table can we attain the same time complexity that is O(m+n) by using some other approach.
- vgeek in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersGiven a dl representing the spiral level order traversal of a binary tree,convert it to a binary tree using one stack. In Last level, nodes will be either to the right or left only. complete code in C. It is usually done using two stacks. Can it be done using one stack?
- vgeek in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersConsider the problem of sorting in ascending order of an array of numbers where each number is in the range 50000 to 50000000. What sorting algorithm is the best choice for the above problem. What is the best case time complexity of sorting available to this problem.
- vgeek in United States
Options are:
a. Merge Sort
b. Insertion Sort.
c. Quick Sort.
d. Counting Sort.
e. Bubble Sort| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer - 1of 1 vote
AnswersTwo 32-bit integers n and m are given and positions i,j,k,l are given.Write a method to copy the contents of m from position k to l into n from position i to j.
- vgeek in United States
(example n=1010000000,m=10101010,i=3,j=5,k=5,l=7..output=10'101'00000)| Report Duplicate | Flag | PURGE
Microsoft
Just sort the array and then start traversing the array and keep the traversed element in another array..if during traversing you get a condition where arr[i]==arr[i+1] then ignore this value otherwise keep copying the elements.It will time for sorting the array and then traversing which will take O(nlogn).
- vgeek June 19, 2013I think without using any other data structure this could be the solution:
a.Let n and m be the size of the arrays: If m=n then traverse one of the arrays.If at any point
&arr[i]=&arr[j] then that will be the intersection point.
b.If m>n then calculate the difference as m-n. Then with the array of size m traverse the first d elements and then start a parallel traversal of both the arrays until we get the intersection point.
With data structure you can store the addresses of both the arrays in a hashmap and then during array traversal of the array with larger size if you find at any time that the address of a particular element is same then that is the intersection point..
This can be done by considering the following scenario:
a.First sort the whole array and start from the last element as in order to get the minimum number of coins you have to try starting from the largest denomination. Divide it by the sum required and the quotient will tell us the number of coins of this denomination required.If quotient is not zero then take the remainder as that amount of money is left and divide it by the next number from the last.If quotient is zero it means this coin's denomination cannot be taken into account and thus divide it by the next smaller number.And in the count of no of coins add the quotient value for every denomination
b.In this way increment the count value and in the end you will get the count of the minimum number of coins.
Please test the below code as it works for all scenarios:
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b)
{
return (*(int *)a-*(int *)b);
}
int noofCoins(int arr[],int n,int S)
{
int div,noc=0,temp=S,i;
for(i=n-1;i>=0;i--)
{
div=temp/arr[i];
if(div!=0)
{
noc=noc+div;
temp=temp%arr[i];
}
}
return noc;
}
int main()
{
int arr[]={5,3,1};
int S=1;
int n=sizeof(arr)/sizeof(arr[0]);
qsort(arr,n,sizeof(int),compare);
printf("The minimum number of coins required are %d ",noofCoins(arr,n,S));
}
The time complexity is not O(n). Suppose the input array is 4,3,2,6,5. Then according to program mid=0+(4-0)/2, then mid is 2 and arr[mid]=2 then here we can get our condition true and thus return the mid so how is it traversing the whole array..?? Remember this is binary search whenever it finds the mid with the given condition it returns. Also you should first check for binary search in wiki and there you should check under the tag recursion
- vgeek June 18, 2013First sort the array and then check if the adjacent elements are same.If yes then increment the count everytime and whenever a the count is greater than n/2 then print the element.Here us the code.
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b)
{
return (*(int *)a-*(int *)b);
}
int checkForNumber(int arr[],int n)
{
int i,count=1;
for(i=0;i<n-1;i++)
{
if(arr[i]==arr[i+1])
count++;
else if(arr[i]!=arr[i+1])
count=1;
if(count>n/2)
{
return arr[i];
}
}
return 0;
}
int main()
{
int arr[]={1,1,1,1,2,2,2,2,2};
int n=sizeof(arr)/sizeof(arr[0]);
qsort(arr,n,sizeof(int),compare);
int i=checkForNumber(arr,n);
if(i==0)
printf("No such number");
else
printf("Number that occurs more than n/2 is %d ",i);
}
The triplet can be found out by using binary search in the following way. You can test the below code:
#include <stdio.h>
#include <stdlib.h>
int findTriplet(int arr[],int low,int high)
{
if(low==high)
return 0;
else if(low==high+1)
return 0;
else
{
int mid=low+(high-low)/2;
if(arr[mid-1]>=arr[mid]&&arr[mid]<=arr[mid+1])
return mid;
findTriplet(arr,low,mid-1);
findTriplet(arr,mid+1,high);
}
}
int main()
{
int arr[]={4,3,4};
int n=sizeof(arr)/sizeof(arr[0]);
int i=findTriplet(arr,0,n-1);
if(i==0)
printf("No triplet exists");
else
{
printf("Triplet exists and it is \n");
printf("%d %d %d",arr[i-1],arr[i],arr[i+1]);
}
}
Use inorder traversal. Keep a static pointer that is previous that points to the previous node.Note inorder traversal will lead to you a sorted set of values.If at any time current value is less than the previous value then it is not a bst otherwise it is:
#include <stdio.h>
#include <stdlib.h>
typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *nn=(node_t *)malloc(sizeof(node_t));
nn->data=data;
nn->left=NULL;
nn->right=NULL;
}
int isBst(node_t *root)
{
static node_t *prev=NULL;
if(root)
{
if(!isBst(root->left))
return 0;
if(prev!=NULL&&root->data<=prev->data)
return 0;
prev=root;
return isBst(root->right);
}
return 1;
}
int main()
{
node_t *root = newNode(4);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(3);
if(isBst(root))
printf("Is BST");
else
printf("Not a BST");
return 0;
}
You can solve it like:
a.First sort the array in non-decreasing order.Take two pointers left and right.Left point to the start and the right pointer points to the end of the array.
b.while(left<right)
b.check whether a[left]+a[right]<k.If yes then increment the left pointer by one.
c.check whether a[left]+a[right]>k.If yes decrement the right pointer by one.
d.If a[left]+a[right]==k.Return true
You can solve it like:
a.First sort the array in non-decreasing order.Take two pointers left and right.Left point to the start and the right pointer points to the end of the array.
b.while(left<right)
b.check whether a[left]+a[right]<k.If yes then increment the left pointer by one.
c.check whether a[left]+a[right]>k.If yes decrement the right pointer by one.
d.If a[left]+a[right]==k.Return true.
please do act logically. You might be saying from the first part that b matches bb as it shows aaab b outputs 1. But please, that determines the different states of a finite automata and also a space between aaab and b .It means that a* which is null.If there is no comma in between then you consider that it should accept bb. But it should not..You can ask anybody in the context of this question that only when given b and bb whether they should match or not.The answer would be no.Please do refer somebody on this question and then provide some further comments...
- vgeek June 13, 2013@Anonymous: I respect your comments but please correct your basics. For bb it should give no as in the input string you are giving a single b and not a b*. Also further for the second case in the input string it is b* and you are bcc. Remember my friend it is b 'c' 'c' not multiple instances of b because b* MEANS multiple instances of only b not anything else....All right...????
- vgeek June 12, 2013The example 2 output is 0 because in string there is a pattern ab which does not matches with a+aabc as a+ means one or more instance of a followed by two necessary instances of a.Note those a are alone they are not followed by any notation .So in ab one a is there for a+ but it should have been followed by 2 a's but it is not..So the output comes out to be 0..
I hope it is clear..
The code for this problem is given below.You can consider the following approach:
a.Find maximum continuous sub-array sum using kadane's algorithm.
b.Similarly find minimum continuous sub-array sum using the same approach.
c.Find the difference between the maximum and minimum element.
#include <stdio.h>
#include <stdlib.h>
int maxSumArrayNegative(int arr[],int size)
{
int max_so_far=arr[0],i;
int max_ending_here=arr[0];
for(i=1;i<size;i++)
{
max_ending_here=max_ending_here+arr[i];
if(max_so_far<max_ending_here)
{
max_so_far=max_ending_here;
}
}
return max_so_far;
}
int maxSumArrayPositive(int arr[],int size)
{
int max_far=0,i;
int max_ending=0;
for(i=1;i<size;i++)
{
max_ending=max_ending+arr[i];
if(max_ending<0)
{
max_ending=0;
}
if(max_far<max_ending)
{
max_far=max_ending;
}
}
return max_far;
}
int minSumArray(int arr[],int size)
{
int min_so_far=arr[0];
int min_ending_here=arr[0],i;
for(i=1;i<size;i++)
{
min_ending_here=min_ending_here+arr[i];
if(min_so_far>min_ending_here)
{
min_so_far=min_ending_here;
}
}
return min_so_far;
}
int main()
{
int arr[3]={-1,-2,-5};
int n=sizeof(arr)/sizeof(arr[0]);
int i,size=0,diff;
for(i=0;i<n;i++)
{
if(arr[i]<0)
size++;
}
if(size==n)
{
int max=maxSumArrayNegative(arr,n);
int min=minSumArray(arr,n);
diff=max-min;
}
else
{
int max=maxSumArrayPositive(arr,n);
int min=minSumArray(arr,n);
diff=max-min;
}
printf("The diff is %d ",diff);
}
Below is the code you can check it it takes the following approach:
a.If currently both the characters match increment both the pointers that is first and second.
b.If currently a * is there then you have to consider either the current character of second string or ignore it.
c.If there is a + then consider the fact such as the previous character of first string is equal to the previous character of second string (if there is only one instance) and then consider both either consider the current character or ignore it.
#include <stdio.h>
#include <stdlib.h>
int stringWildCard(char *first,char *second)
{
if(*first=='\0'&&*second=='\0')
return 1;
else if(*first=='*'&&*(first+1)!='\0'&&*second=='\0')//in case of 'a*' and '' it should return true as a* means 0 or more occurences
return 1;
else if(*first=='*'&&*(first+1)!=*second&&*(first-1)!=*second)
return 0;
else if(*first=='*')
return stringWildCard(first+1,second)||stringWildCard(first,second+1);
else if(*first==*second)
return stringWildCard(first+1,second+1);
else if(*first!=*second&&*(first+1)=='*')
return stringWildCard(first+2,second);
else if(*first=='+'&&*(first-1)==*(second-1))
return stringWildCard(first,second+1)||stringWildCard(first+1,second);
return 0;
}
void test(char *first,char *second)
{
stringWildCard(first,second)?puts("Yes"):puts("No");
}
int main()
{
test("a*b", "aaaab");//yes
test("a+bc*", "bccc");//no
test("ab+cd*", "abbcdd");//yes
}
In the d option that you are saying there will be no zero instance of a or b as when
{0,a,aa,aaaa..aaaaa} is bitwise ORed with b then the result will be
{b,a,aab,aaabbb...} .Note there will be no zero instance of b and in order to get it you also have to cover it under the star notation.I hope you now understand
For moving the elements that is the even to the left and odd to the right we could take the following approach:
a.Consider two references such that one reference points to the start of the array and another points to the last of the array. Increment the first reference and decrement the second reference until first is equal to second.
b.Now if the both references point to even element then increment the first reference as the second reference now points to the even element and whenever we find that the first points to the odd then we swap both the elements.
c.If last points to even and first points to odd then first swap and then decrement the second and increment the first pointer
d.If first points to even and second points to odd then decrement the second reference as it is already that is the odd element is already in the right side of the array.
e.If both the elements are odd then also decrement the second reference as the odd element should be to the right and for the first one pointing to the odd whenever an even element is found that condition is handled in the c. condition. Below is the code:
void swap(int arr[],int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
void placeElements(int arr[],int n)
{
int i=0,j=n-1;
while(i<j)
{
if(arr[j]%2==0&&arr[i]%2==0)
{
i++;
}
else if(arr[j]%2==0&&arr[i]%2!=0)
{
swap(arr,i,j);
j--;
i++;
}
else if(arr[j]%2!=0&&arr[i]%2==0)
{
j--;
}
else
{
j--;
}
}
}
void printArray(int arr[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",arr[i]);
}
int main()
{
int arr[]={3,3,3,5};
int n=sizeof(arr)/sizeof(arr[0]);
placeElements(arr,n);
printArray(arr,n);
}
Its easy take two pointers increment one pointer by one and the other pointer by two and then
1.First find the meeting point of these two pointers.
2.After finding the meeting point take the first pointer to the start that is head and then increment n1 and n2 both by one until they point to the same value
Here is the code
LinkedListNode FindBeginning(LinkedListNode head) {
LinkedListNode n1 = head;
LinkedListNode n2 = head;
// Find meeting point
while (n2.next != null) {
n1 = n1.next;
n2 = n2.next.next;
if (n1 == n2) {
break;
}
}
// Error check - there is no meeting point, and therefore no loop
if (n2.next == null) {
return null;
}
/* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps
/* from the Loop Start. If they move at the same pace, they must
* meet at Loop Start. */
n1 = head;
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
// Now n2 points to the start of the loop.
return n2;
}
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, then that element is duplicate :
- vgeek June 19, 2013if(count[arr[i]]==1) then that element is duplicate...