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
Store all the values from the tree in an array in an inorder traversal form. Of course it wont give us a sorted array as it is not a binary search tree but then in the array just apply the sum of subsets algorithm to generate all the possible paths in the array. Now two scenarios arise:
a. If in the path the root node of the tree is included then just subtract the root node from the sum and then check for the remaining sum subset in the array.
b. If in the path root node is not to be included then just apply the sos algorithm and you will get all the paths that lead us to a given sum
You can solve this problem in O(n) by onsidering the following approach:
a. Take an array that contains the negative elements.
b. Take an array that will hold the sum of the negative values that will be a positive element in the array that is a triplet which sums up to 0.
c. Whenever we have tracked two negative elements track the sum till now in prev_sum that will hold the positive value in the array
Here is the code:
#include <stdio.h>
#include <conio.h>
#include <limits.h>
void findTriplet(int arr[],int n)
{
int bin[1000]={0},trip[2],k=0,sum=0,i,j,count_trip=1;
for(i=0;i<n;i++)
{
if(arr[i]<0&&count_trip<3)
{
sum=sum+(-1*arr[i]);
bin[sum]=1;
count_trip++;
trip[k]=arr[i];
k=k+1;
}
if(count_trip==3&&bin[sum]==1)
{
printf(" Triplet exists ");
printf(" %d %d %d ",trip[0],trip[1],sum);
sum=0;
trip[0]=trip[1]=INT_MAX;
count_trip=1;
k=0;
}
if(arr[i]>0)
{
bin[arr[i]]=1;
if(count_trip==3&&bin[sum]==1)
{
printf(" Triplet exists ");
printf(" %d %d %d ",trip[0],trip[1],sum);
sum=0;
trip[0]=trip[1]=INT_MAX;
count_trip=1;
k=0;
}
}
}
}
int main()
{
int arr[]={-1,4,-3,-5,11,-6};
int n=sizeof(arr)/sizeof(arr[0]);
findTriplet(arr,n);
}
Here is the code in O(n) and O(1) space
#include <stdio.h>
#include <conio.h>
void findJumps(int arr[],int n)
{
int i,len=0,prev;
if(arr[0]>n)
{
printf(" No of jumps are 1 ");
}
else
{
for(i=0;i<n;)
{
if(i+arr[i]>=n-1)
{
len=len+1;
break;
}
i=arr[i+arr[i]];
if(i==0&&i<=n-1)
{
len=len+arr[i];
break;
}
len=len+1;
}
}
if(len==0)
{
printf(" No jumps are there ");
}
else
{
printf(" Number of jumps are %d ",len);
}
}
int main()
{
int arr[]={1,5,4,6,9,3,0,0,1,3};
int n=sizeof(arr)/sizeof(arr[0]);
findJumps(arr,n);
}
The recurrence relation of a binary tree is given by the expression:
T(n)=T(k)+T(n-k-1)+c.
Here k are the number of nodes of the left subtree and n-k-1 are the number of nodes of the right subtree. Also for a complete binary tree
T(n)=T(n-1)+T(n-1)+c. So it is T(n)=2T(n-1)+c. So as it can be seen that the recurrence relation is a function of linear n. So the time complexity of traversal of a tree is O(n). (That is a whole tree both left and right).
For that you can take a upper bound value that is find the min element in the array. If it is negative then subtract it with all the elements in the array and in the code you can edit the statement like this
temp=sum-arr[i]-min_element. And then you can effectively solve the problem
You can consider this approach in O(n):
a. Make an array say of 1000 integers and all intialized to 0.
b. Take a temp variable and calculate the difference of the sum and the array and set the occurence of that particular integer to 1 by indexing that integer in the array of 1000 integers.
c. If the temp>=0 and if the array is set for that number then print the pair.
d. It prints all the valid pairs.
#include <stdio.h>
#include <conio.h>
void findSumPair(int arr[],int n,int sum)
{
int bin[1000]={0},i,temp;
for(i=0;i<n;i++)
{
temp=sum-arr[i];
if(temp>=0&&bin[temp]==1)
{
printf(" %d %d ",temp,arr[i]);
}
bin[arr[i]]=1;
}
}
int main()
{
int arr[]={2,1,3,4,6,5,7,8,21,9};
int n=sizeof(arr)/sizeof(arr[0]);
findSumPair(arr,n,7);
}
Yes it can be done using dynamic programming. The problem here is not to check whether the word is in the dictionary or not. The problem is used to determine whether by taking out one alphabet at a time the remaining word is in the dictionary or not. Now this can be easily done by using dynamic programming or recursion. Here is the idea
#include <iostream>
#include <string>
using namespace std;
bool dictionaryContains(string str)
{
string dictionary[] = {"restated","restate","estate","state","stat","sat","at","a" };
int size=sizeof(dictionary)/sizeof(dictionary[0]);
for(int i=0;i<size;i++)
{
if(dictionary[i].compare(str)==0)
{
return true;
}
}
return false;
}
bool wordBreak(string str,int temp)
{
int size=str.size();
if(size==0)
return true;
for(int i=1;i<=size;i++)
{
if(dictionaryContains(str.substr(0,temp))&&wordBreak(str.substr(0,temp-1)))
return true;
}
return false;
}
int main()
{
string str="restated";
int n=str.size();
if(wordBreak(str,n-1))
cout<<"Can be broken";
else
cout<<"Cant be broken";
}
Using bit manipulation array. That is if we have 2000 elements then using the bit operation they can be stored in 625 memory locations. Now their index is specified by element/32 and their bit position is specified by element%32.
Suppose we have 2000 elements .I am just taking some elements as:
arr[2000]={33,32,65,35};
now result array=33/32=1 and bit is 33%32= so bit one is set that is result[1]=2
now for 12/32=0 and bit is 32%32=0 so in index 0 bit 0 is set that is result[0]=1
for 65/32 index is 2 and bit is 1 set so result[2]=2
35 index is again 1 so 35%32=3 so bit result[1]=2|8=10
in this way the result array holds the numbers. Now to sort them
restore the array in sorted order. This one is good algo and was given by algos when i asked him the same question.
int i,j,index=0;
for(i=0;i<=625;i++)
for(j=0;j<32;j++)
{
array[index++]=i*32+j;
}
you can consider this approach:
a. Now in your example there are 5 arrays and they are sorted.
b. Let us suppose the arrays are a,b,c,d,e. Then take three variables i,j,d such that i,j=0 and d=m that is the size of the array. Take a destination array of size 5m that is didx[5m]
c. Then do this.
1.while(i<m&&j<m)
if a[i]<didx[d] then didx[d]=a[i],i++,d++
else didx[d]=b[j]j++,d++
then take i=0,d=0,j=m
2.while(i<m&&j<3m) then
if(c[i]<didx[j] didx[d]=c[i],i++,d++
else didx[d]=didx[j],j++,d++
again take i=0,j=0,d=4m and then do the above step 1
then take i=0,d=0,j=5m and do step 2 at last didx holds the sorted elements with 15 swaps.
Yes for that you can just ignore the -1 step that is if you use a stack or if you are doing an array traversal so you can skip that step where in an array if we reach the last element then it ignore the -1 step and also in stack you can pop the elements if they are left while storing the numbers
- vgeek July 31, 2013Here is a O(n) solution:
a. Keep the first element in temp and its index stored in k.
b. For every element see the difference with the next element
c. When the difference is greater than 0 then update the k variable and also the j variable.
d. Note for finding the difference of the element there are two pointers in the array that is j and k k runs the loop and j finds the difference.
e. If the element does not have a large element then it is updated to -1.
#include <stdio.h>
#include <conio.h>
void findNextGreater(int arr[],int n)
{
int j,temp,k=0;
temp=arr[k];
j=1;
while(k!=n-1)
{
if(arr[j]-temp<0&&j==n-1)
{
arr[k]=-1;
k=k+1;
temp=arr[k];
j=k;
}
if(arr[j]-temp>0)
{
arr[k]=arr[j];
k=k+1;
j=k;
temp=arr[k];
}
else
{
j=j+1;
}
}
arr[n-1]=-1;
for(j=0;j<n;j++)
printf(" %d ",arr[j]);
}
int main()
{
int arr[]={11,13,21,32,10};
int n=sizeof(arr)/sizeof(arr[0]);
findNextGreater(arr,n);
}
Suppose the double linked list representation is 12345678. The binary tree should be
---------------1-----------------
--------3-----------2---------------
---4------5-----6-------7
-----------------------------8
And yes you can use one stack to solve the problem. Sorry i used the word in place . I have edited the question now.
Insert the sorted order of each word in the trie. Since all the anagrams will end at the same leaf node. We can start a linked list at the leaf nodes where each node represents the index of the original array of words. Finally, traverse the Trie. While traversing the Trie, traverse each linked list one line at a time.
- vgeek July 30, 2013The probability can be found out as:
Consider there are 1000 transistors. Out of those 6 are defective that is 994 are good transistors. Now as 2 transistors are mis-identified as defective in 100 transistors. So number of transistors misidentified in 994 good transistors are - (2*994)/100=19.88. So in total defective transistors 6+19.88=25.88. So probability it is actually defective is 6/25.88=0.232
Tries can be used to print all anagrams together.
a. Get all the anagrams related to a word under one leaf node.
b. Then again traverse the trie and print all anagrams together
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define bool int
#define NO_OF_CHARS 26
// Structure to represent list node for indexes of words in
// the given sequence. The list nodes are used to connect
// anagrams at leaf nodes of Trie
struct IndexNode
{
int index;
struct IndexNode* next;
};
// Structure to represent a Trie Node
struct TrieNode
{
bool isEnd; // indicates end of word
struct TrieNode* child[NO_OF_CHARS]; // 26 slots each for 'a' to 'z'
struct IndexNode* head; // head of the index list
};
// A utility function to create a new Trie node
struct TrieNode* newTrieNode()
{
struct TrieNode* temp = new TrieNode;
temp->isEnd = 0;
temp->head = NULL;
for (int i = 0; i < NO_OF_CHARS; ++i)
temp->child[i] = NULL;
return temp;
}
//For qsort
int compare(const void* a, const void* b)
{ return *(char*)a - *(char*)b; }
/* A utility function to create a new linked list node */
struct IndexNode* newIndexNode(int index)
{
struct IndexNode* temp = new IndexNode;
temp->index = index;
temp->next = NULL;
return temp;
}
// A utility function to insert a word to Trie
void insert(struct TrieNode** root, char* word, int index)
{
// Base case
if (*root == NULL)
*root = newTrieNode();
if (*word != '\0')
insert( &( (*root)->child[tolower(*word) - 'a'] ), word+1, index );
else // If end of the word reached
{
// Insert index of this word to end of index linked list
if ((*root)->isEnd)
{
IndexNode* pCrawl = (*root)->head;
while( pCrawl->next )
pCrawl = pCrawl->next;
pCrawl->next = newIndexNode(index);
}
else // If Index list is empty
{
(*root)->isEnd = 1;
(*root)->head = newIndexNode(index);
}
}
}
// This function traverses the built trie. When a leaf node is reached,
// all words connected at that leaf node are anagrams. So it traverses
// the list at leaf node and uses stored index to print original words
void printAnagramsUtil(struct TrieNode* root, char *wordArr[])
{
if (root == NULL)
return;
// If a lead node is reached, print all anagrams using the indexes
// stored in index linked list
if (root->isEnd)
{
// traverse the list
IndexNode* pCrawl = root->head;
while (pCrawl != NULL)
{
printf( "%s \n", wordArr[ pCrawl->index ] );
pCrawl = pCrawl->next;
}
}
for (int i = 0; i < NO_OF_CHARS; ++i)
printAnagramsUtil(root->child[i], wordArr);
}
// The main function that prints all anagrams together. wordArr[] is input
// sequence of words.
void printAnagramsTogether(char* wordArr[], int size)
{
// Create an empty Trie
struct TrieNode* root = NULL;
// Iterate through all input words
for (int i = 0; i < size; ++i)
{
// Create a buffer for this word and copy the word to buffer
int len = strlen(wordArr[i]);
char *buffer = new char[len+1];
strcpy(buffer, wordArr[i]);
// Sort the buffer
qsort( (void*)buffer, strlen(buffer), sizeof(char), compare );
// Insert the sorted buffer and its original index to Trie
insert(&root, buffer, i);
}
// Traverse the built Trie and print all anagrms together
printAnagramsUtil(root, wordArr);
}
// Driver program to test above functions
int main()
{
char* wordArr[] = {"tar","rat","banana","atr"};
int size = sizeof(wordArr) / sizeof(wordArr[0]);
printAnagramsTogether(wordArr, size);
return 0;
}
A network mask helps you to determine which portion determines the network id and which portion determines the node id.
class A-255.0.0.0 class B-255.255.0.0 class C-255.255.255.0
Subnetting allows you to have multiple networks from among the class of networks which are A,B,C instead of having only one network from among the classes A,B,C. Here for class C the subnet mask is 255.255.255.224 here as the first 3 bits are set you can have 8 subnets and 32 host addresses.
For class B you can have more subnets and more host addresses as 255.255.248.0 allows you to have 32 subnets and 2^11 host addresses. It is also denoted as /27 as 27 bits are set in the network.
These are basically referred to as ugly numbers . Here is the code for it:
a. Take variables for multiples of 2,3,5,7.
b. Everytime find a minimum of the multiple.
c. Store 1 in the first index as it is multiple of all.
d. Find the minimum of all the multiples of 2,3,5,7. Whenever that minimum is equal to any of the multiples. Store that multiple in the indexes assigned for 2,3,5,7 and also multiply that element with the number to get the next higher multiple in next iteration.
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
int min(int a,int b)
{
return (a<b?a:b);
}
int min(int a,int b,int c,int d)
{
return min(a,min(b,min(c,d)));
}
void printAllMultiples(int n)
{
unsigned *ugly=(unsigned *)malloc(sizeof(ugly));
unsigned next_multiple_2=2;
unsigned next_multiple_3=3;
unsigned next_multiple_5=5;
unsigned next_multiple_7=7;
unsigned i2=0,i3=0,i5=0,i7=0;
ugly[0]=1;
unsigned next_ugly_no;
int i;
printf(" %d ",ugly[0]);
for(i=1;i<n;i++)
{
next_ugly_no=min(next_multiple_2,next_multiple_3,next_multiple_5,
next_multiple_7);
*(ugly+i)=next_ugly_no;
printf(" %d ",next_ugly_no);
if(next_ugly_no==next_multiple_2)
{
i2=i2+1;
next_multiple_2=ugly[i2]*2;
}
if(next_ugly_no==next_multiple_3)
{
i3=i3+1;
next_multiple_3=ugly[i3]*3;
}
if(next_ugly_no==next_multiple_5)
{
i5=i5+1;
next_multiple_5=ugly[i5]*5;
}
if(next_ugly_no==next_multiple_7)
{
i7=i7+1;
next_multiple_7=ugly[i7]*7;
}
}
}
int main()
{
printAllMultiples(20);
}
@algos
can you explain for your example how the bit array is filled.
Like for 97/32=3 that is arr[3] and bit position 97%3 is 1 but for 64/32=0 that is arr[0] the bit position is also 0 but how 2 and 32 are coming. Can you please again explain how the values in the bit array are filled. It will be of great help.
it is basically a problem of finding the subset sum with sum r/2 where r is the sum of the array. This code prints all the necessary subsets possible for summing upto r/2
#include <stdio.h>
#include <stdlib.h>
int arr1[]={6,5,4,3,2,1};
int sumOfSubset(int s,int k,int w[],int r,int n,int m,int x[])
{
int i,j,sum=0;
x[k]=1;
if(s+w[k]==m)
{
for(i=0;i<n;i++)
{
if(x[i]==1)
{
for(j=0;j<n;j++)
{
if(w[i]==arr1[j])
{
printf("%d",j);
}
}
}
}
printf("\n");
}
else if(s+w[k]+w[k+1]<=m)
sumOfSubset(s+w[k],k+1,w,r-w[k],n,m,x);
if((s+r-w[k]>=m)&&(s+w[k+1])<=m)
{
x[k]=0;
sumOfSubset(s,k+1,w,r-w[k],n,m,x);
}
}
int main()
{
int arr[]={6,5,4,3,2,1};
int n=sizeof(arr)/sizeof(arr[0]);
int i,r=0;
int x[n];
for(i=0;i<n;i++)
{
x[i]=0;
}
for(i=0;i<n;i++)
{
r=r+arr[i];
}
sumOfSubset(0,0,arr,r,n,r/2,x);
}
Here another method is used to find any number of missing numbers within a given range:
a. Get the min and max of the array.
b. Make the count array of size max.
c. Store INT_MIN values in the count array till min that is from 0 to min-1 as this is not the range to search for.
d. Make the rest of the elements from min to max to 0
e. At last increment the count for every value.
f. For those elements for which the count is 0 they are missing. Here is the code:
#include <stdio.h>
#include <conio.h>
#include <limits.h>
int findMissingElement(int arr[],int n)
{
int max=arr[0],min=arr[0],i;
for(i=0;i<n;i++)
{
if(max<arr[i])
max=arr[i];
if(min>arr[i])
min=arr[i];
}
int count[max];
for(i=0;i<min;i++)
count[i]=INT_MIN;
for(i=min;i<=max;i++)
count[i]=0;
for(i=0;i<n;i++)
{
count[arr[i]]++;
}
for(i=min;i<=max;i++)
{
if(count[i]==0)
{
printf(" %d ",i);
}
}
}
int main()
{
int arr[]={12,14,15,16,13,20};
int n=sizeof(arr)/sizeof(arr[0]);
findMissingElement(arr,n);
}
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 ...
The rotation question can also be done as:
- vgeek August 24, 2013