CareerCup

On uniprocessor sleep may act as a way of synchronizing output from the two processes but that is not necessarily true Everytime in this scenario. On multiprocessor, the two processes can run on different cores and can execute in parallel doing the same thing means they might sleep at the same time. Overall the result after each loop is non deterministic and at the end will be 1000 when both processes are done.

The central server will post a query to each server, sth like this "Send me the count of users visited between t1 and t2" where t1 and t2 is the start and end time. Assuming all the servers are synchronized to the single clock. The central server will add up all these counts and see if it is more than 1Billion. If not, it will again send the query after some time asking for the count between "t2 and t3". The time intervals can be dynamically selected by the central server based on the cumulative count. For e.g. the first query can be to send the count of users visited between 2 am and 3 am. If the total count is way less, next time the server may ask for counts between 3 am and 6am in order to reduce the no. of time it has to poke all the servers. This also means that each local server has to maintain the logs of what all users visited during what time of day. Of course log sizes are limited so we need to make sure that the central server probes at the right frequency. After a series of such request there will be a request that will return the count that when added yields 1billion or more than that. So, now we know that during time t1 and t2 the condition was met so we can use binary search approach to break this interval in a much smaller interval and compare sort the time stamp among all the servers to find out the billionth user. This need the support from local server to maintain the information of no. of users logged in between a given interval.

Things to consider:
-More servers might get added in between
- Some servers might have a downtime so how to handle such cases. May be the server where the billionth user logged on just went down.

It is exponential and is a very good example showing how recursion can be bad at times. In such cases memoization is used to memorize what we have already computed and use it in further operations.

This is how I will implement it:

Take the greater of two numbers in this case b. Generate a random no between range [1,b] if this no is less than equal to a then output heads else output tails. So, if choose a = 5 and b =7 generate no between 1 and 7. If no is less than equal to 5 output heads. The probability of generating heads here is 5/7 i.e. a/b and probability of generating tails is 2/7 i.e. (b-a)/b

This question was on a phone interview.

Read the Question carefully. It says "Find the subset of perimeters in set U where all of the possible dimensions for a perimeter in the subset have areas common with the areas of one or more other perimeters in set U". Read last line AREA COMMON WITH ONE OR MORE OTHER PERIMETER IN SET U. So, if you chose 18 as one of the perimeter you can't chose 12.

Thanks for the correction. I guess u r right. I completely missed out that point.

Similar Question was asked to me while I was interviewing with Intel. Here is the Question and my answer to it:

Q: The operating system typically allocates memory in pages such that the base address of the pages is 0, 4K, 8K, .... Given two (virtual) addresses, write a program to find if they refer to locations on the same page.
Ans
Since the page boundaries are at 0, 4, 8k …we can see that the page size is equal to 4K. Now assuming we have a 32 bit address space, bits 31-20 will always be the same for one block of 4k bytes of memory since 4k is equal to 4*1024 which is equal to 12 lower order bits of the address. Given two addresses the only thing to be checked is their bits from 31-20. If they are same that means both the addresses lie in the same page. (Assuming int size is 4 bytes else we will use long to store the address)

bool AreOnSamePage (int *a, int *b)
{
Unsigned  int c = (unsigned int) a;
	Unsigned  int d = (unsigned int) b;
	 c = c & 0xFFFFF000; //masking the lower order 12 bits
	 d = d & 0xFFFFF000;
	 if(c==d)
		 return true;
	 else
		 false;
}

One of the solution is to run BFS but it won't be very efficient. One of the good way to solve this is to look the problem this way. Make a list of friends of A and make another list of friends of C. A and C are 2 degree friends if the two list we have made have at least one friend in common. This intersection can be efficiently done using O(n) time and memory complexity using a hash table.

One of the solution is to run BFS but it won't be very efficieint. One of the good way to solve this is to look the problem this way. Make a list of friends of A and make another list of friends of C. A and C are 2 degree friends if the two list we have made have at least one friend in common. This intersection can be efficiently done using O(n) time and memory complexity using a hash table.

str1 and str2 == 0 means if both the strings are NULL. In that case the program will output...Not Anagrams...

I came up with the following points. I have only mentioned the ones that I feel are the most imp...

One of the variables is speed which is kind of a enumerated data type. Check for all the speeds and see if the blender works fine. The other variable can be different types of blades provided with the blender. You should be able to change the blades easily. Check if the all blades rotate smoothly and should never touch the jar.
Third variable can be the type of material put in the blender. It can vary from soft material such as banana to hard substance such as grains.

-- Combination testing - Use the above three variables in pair to do combination testing.

-- Performance Testing - Test how sharp are the blades are and effectiveness of blending different materials. The blender should not make a lot of noise. Check the specification for tolerable levels of noise. Check how the blender operates on low voltages.

-- Load Testing -- Stuff the jar to fill it completely and run the blender.

-- Do Stress testing. The jar should not be too heavy. If it slips out of hand it should not break. Try pressing several buttons simultaneously to see what happens. Try holding the blades with your hand and run the blender. See if its gets heated. If yes, then how much time it takes to get heat up and finally burst the coil. There should not be any explosion in such a case. This is imp to test as sometimes we may put sth in the blender that is not so easy to move and the blades might get stuck heating the motor. One of the test that can be performed is to leave the blender on with an empty jar and in another test case with a filled jar. It might be good to have a system in place that can turn off the blender when the motor gets too heat up. Try suppling power which is out of range. Its better to have a fuse to take care of such situations. Put a hard substance in the jar and run the blender to see the effect. The jar should be strong enough to handle even hard materials.

-- Internationalization - Your motor should be operatable worldwide on all the frequencies.

-- Localization - It should meet the local rules and standards. Different countries have different quality standards. It should meet all the quality standards.

-- Usability - It should have proper instructions that is easy to use. Anyone should be able to come and use it just by looking at the buttons. It should also mention nay safety hazards. You should also be able o easily assemble and disassemble blender parts for cleaning purposes.

--Safety and Reliability - Should be properly earth so as to avoid any shocks.
-- Try to run blender without placing a jar.

Here is my code...Some optimization might be possible though...

/* Reverse a Link list */
# include <stdio.h>
# include <math.h>
# include <stdlib.h>
struct nodes
{
	int value;
	struct nodes * next;
}node;

void sort(struct nodes * head);
void reverse(struct nodes * head);
void display_list(struct nodes *);
struct nodes * make_linklist(int size);
nodes* KReverse(nodes* head, int k);
nodes * kreverse(nodes *head,int k);

void main()
{
	int num = 10,k = 0;
	struct nodes *head, *p;
	printf("Enter the value of k \n");
	scanf("%d",&k);
	if(k < 0)
	{
		printf("Incorrect Input \n");
		return;
	}
	head = make_linklist(num);
	p = head;
	//display_list(p);
	//printf("Now Reversing\n");
	if(k)
		head = KReverse(head, k);
	//reverse(head);
	//sort(head);
	
	display_list(head);
}

nodes * KReverse(nodes* head, int k)
{
	int n = k;
	nodes *new_next = head;
	nodes *new_head = head;
	while(n-- > 1)
		new_head =  new_head->next;	
	while(head)
	{
		n = k;
		int count = 0;
		while(n-- >0 && new_next->next != NULL)
		{
			new_next = new_next->next;
			count++;
		}
		if(count < k)
			new_next = NULL;
		kreverse(head, k);
		
		n = k;
		nodes * temp = new_next;
		while(n-- > 1 && temp != NULL && temp->next != NULL)
			temp = temp->next;
		head->next = temp;
		head = new_next;		
	}
	return new_head;
}

nodes * kreverse(nodes * head, int k)
{
	int n = k-1;
	nodes * tail = head;
	while(n-- > 0 && tail->next != NULL)
		tail = tail->next;
	tail->next = NULL;
	reverse(head);
	return head;
}
void reverse(struct nodes *head)
{
	struct nodes *prev, *now, *future;
	prev = head;
	now = prev->next;
	while(now)
	{
		future = now->next;
		now->next = prev;
		prev = now;
		now = future;
	}
	head->next = NULL;
	head = prev;
	//display_list(head);
}

struct nodes * make_linklist(int size)
{
	struct nodes *prev, *now, *head;
	head = (struct nodes*) malloc(sizeof(nodes));
	head->value = 100;
	prev = head;
	for(int i=0;i<size-1;i++)
	{
		now = (struct nodes*) malloc(sizeof(nodes));
		now->value = i;
		prev->next = now;
		prev = now;
	}
	now->next = NULL;
	return head;

}
void display_list(struct nodes * p)
{
	while(p)
	{
		printf("The element is %d \n",p->value);
		p = p->next;
	}

}

3 Solutions

1. Everyone knows about the ineffecient O(n2) solution
2. Sort the numbers and keep two pointers one to the start and the other at the end and move them accordingly.
3. See the above post of using hash tables in O(n) time.

I am using additional memory but we can do it without using additional memory in that case we will have to scan through the entire array twice..In that case in first scan we replace all zeroes in the array by a special character and in the second scan we replace each row and column containing that special character to Zero..


#include<stdio.h>
#include<stdlib.h>
void main()
{
int a[100][100];
int n;
printf("Enter the number of elements of the array in one dimension\n");
scanf("%d", &n);
printf("Enter the elements of the array \n");
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d", &a[i][j]);
int * i_index = (int *) malloc(sizeof(int) * n);
int * j_index = (int *) malloc(sizeof(int) * n);

for(int i=0;i<n;i++)
{
i_index[i] = -1;
j_index[i] = -1;
}
for(int i =0; i< n;i++)
for(int j=0;j<n;j++)
{
if(a[i][j] == 0)
{
i_index[i] = 0;
j_index[j] = 0;
}
}
for(int i=0;i<n;i++)
{
if(i_index[i] == 0)
for(int j=0;j<n;j++)
a[i][j] = 0;

if(j_index[i] == 0)
for(int j=0;j<n;j++)
a[j][i] = 0;
}

printf("The new elements of the array are \n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%d", a[i][j]);
printf("\n");
}
}

I guess that's the solution...

void convert_to_linklist(tree_node * root)
{
	if(!root)
		return;
	tree_node * temp = root->left;
	if(temp)
	{
		while(temp->right)
			temp = temp->right;
		temp->right = root;
		temp = root->left;
		root->left  = NULL;
		convert_to_linklist(temp);
		
	}
	
	temp = root->right;
	if(temp)
	{
		while(temp->left)
			temp = temp->left;
		tree_node * te = root->right;
		root->right = temp;
		convert_to_linklist(te);

	}
}

Since the array is sorted pick up the middle element and then for its left and right child again pick up the middle element from the two partition. In this way we can ensure that the tree is balanced.

Use a hash table for finding a suitable index for all the pairs. So if the string is of length l then you can have atmost l-1 distinct pairs. Start from first character and hash the first 2 character and then increment the counter and pick up the 2 and 3 char and hash it. If the pair is already present then print it. This takes o(l) space. Is there a better solution than this....

leaf(node *root)
{
if(root == NULL)
return;

if(root->left == NULL && root->right== NULL)
{
printf("Leaf is %d", root->val);
return;
}
leaf(root->left);
leaf(root->right);
}

You can assign a dewy ID to each node as you scan the tree and then find the common substring between the deweyIDs for the two leaves given. That will give the LCA. Another approach is to label all the nodes based on the level and then find the Euler tour and then determine the LCA. The following link should be useful....
coursesdotcsaildotmitdotedu/6dot897/spring03/scribe_notes/L11/lecture11dotpdf

Here is my version

#include <stdio.h>
void combinations(char * str, int start, int * result, int len, int k, int count);
void main()
{
	int i=0,k=0, count = 0;
	char str[100];
	printf("Enter the string \n");
	gets(str);
	printf("Enter the size of the combinations to be produced \n");
	scanf("%d", &k);
	while(str[i] != '\0')
		i++;
	int result[100];
	combinations(str,0, result, i, k, count);
	printf("\n");
}

void combinations(char * str, int start, int * result, int len, int k, int count)
{
	if(start == len)
	{
		if(k==count)
		{
			printf("\n");
			for(int j=0;j<len;j++)
				if(result[j] == 1)
					printf("%c", str[j]);
		}
		return;
	}
	for(int i=0;i<2;i++)
	{
		if(i && count <= k)
		{
			result[start] = 1;
			count++;			
		}
		else
			result[start] = 0;
		combinations(str,start+1,result,len,k,count);				
	}
}

I guess we will have to maintain 2 data structures, one can be a self balancing tree and the other a hash table. The first tree will store the word as they come in sorted order so that the words can be inserted and extracted in O(lgn) time. Along with that whenever a word is inserted its count is incremented. So then in order to select the topmost k high frequency words we have to just select the top k largest counts from the hashtable which can be done using Randomized Quicksort in O(n) time. Instead of a hashtable we can also use a self balancing tree whose nodes will have a count variable and size variable where size will denote the total no of nodes beneath that node including the node itself. And then we find the kth Largest element in using the tree and thus obtains pointers to top k high frequency words.

Anyone with a better Solution????

If you use hash you are using additional memory and the question is asking for o(1) space complexity..

If n =5 and all the numers in array is 2 then

Sn = 15
n = 5
sum of array is 10
x as per your formulae = 10+5-15 = 0 which is incorrect. Let me know if I am doing something wrong here..

Here is my version

#include<stdio.h>
#include<stdlib.h>
char * strtok(char * s, char *comp);
void main()
{
	char s[100], *p, delimit[20];
	int i=0, len=0;
	printf("Enter the input string \n");
	gets(s);  
	printf("Enter the delimiter string \n");
	gets(delimit);

	while(len++ != '\0');
	p = strtok(s,delimit);	
	while(p != NULL)
	{
		printf("%s \n", p);
		p = strtok(NULL, delimit);			
	}
}
char * strtok(char * str, char *comp)
{
	static int pos;
	static char *s;	
	int i =0, start = pos;

	// Copying the string for further calls of strtok
	if(str!=NULL)
		s = str;
	
	i = 0;
	int j = 0;
	//While not end of string
	while(s[pos] != '\0')
	{
		j = 0;	
		//Comparing of one of the delimiter matches the character in the string
		while(comp[j] != '\0')
		{		
			//Pos point to the next location in the string that we have to read
			if(s[pos] == comp[j])
			{
				//Replace the delimter by \0 to break the string
				s[pos] = '\0';
				pos = pos+1;				
				//Checking for the case where there is no relevant string before the delimeter.
				//start specifies the location from where we have to start reading the next character
				if(s[start] != '\0')
					return (&s[start]);
				else
				{
					// Move to the next string after the delimiter
					start = pos;
					// Decrementing as it will be incremented at the end of the while loop
					pos--;
					break;
				}
			}
			j++;
		}
		pos++;		
	}//End of Outer while
	s[pos] = '\0';
	if(s[start] == '\0')
		return NULL;
	else
		return &s[start];
}

Here is my code..

#include<stdio.h>
void main()
{
	char s[100];
	int i =0,j=0;
	printf("Enter the string\n");
	gets(s);
	while(s[i] != '\0')
	{
		if(s[i+1] != '\0' && s[i+2] != '\0' && s[i] == '\'' && (s[i+1] == '<' || s[i+1] == '&' || s[i+1] == '>') && s[i+2] == '\'')
		{
			s[j++] = s[i+1];
			i = i+3;
		}
		else
			s[j++] = s[i++];
	}
	s[j] = '\0';
	printf("The new string is %s\n", s);
}

What I initially though of is that we construct a max heap which will take o(n) time. Now at the first level of heap we have only 1 element. At second level we have 2 and at h height we have 2^h elements. We also know that elements at each level are smaller than the elements that are one level above. If we just want to pick top i million numbers without caring that they should be sorted we can just scan through the heap printing elements till we have reached the 20th level. This is obtained as follows: 2^0 + 2^1 + 2^2 + ----+2^h = 1 million -->Applying GP 2^(h+1) = 1 million = 2^20 and so h = 19 .So we only need to scan till level 19th and we have top 1 million elements(a little more than a million) and obviously not sorted. Any comments??

Construction of heap takes O(n) time. Its a tighter bound. Refer to Cormen for more details.

Numbers in the array will act as keys and their index will act as values. So, if you have an array like 2,2,2 insert 2 the first element as (2,1). When adding second 2 check if it is there in the hashtable, if yes go to that location and update the value as (1,2) so now it will look like (2,(1,2)) and when third is added (2,(1,2,3)). So, if some number pair up with 2 then we can form 3 pairs with 2 at index 1,2 and 3.

The above can be done by taking each node in a heap as a structure which contains the string and the variable count. Modify the heap functions so that when you want to search for an element it is searched on the string and when you want to heapify it it is done using the count. So, when you want to add a string first check in the heap if it is there increment the count else put in the heap with count as 1 and heapify.

#include<stdio.h>
#include<stdlib.h>
void main()
{
	char str1[1000], str2[1000], len1 = 0, len2 =0, a[256];
	int flag = true;
	printf("Enter the first string\n");
	gets(str1);
	printf("Enter the second striing\n");
	gets(str2);

	for(int i =0;i<256;i++)
		a[i] = 0;

	while(str1[len1] != '\0')
	{
		a[str1[len1]] = a[str1[len1]] + 1;
		len1++;
	}

	while(str2[len2] != '\0')
	{
		a[str2[len2]] = a[str2[len2]] - 1;
		len2++;
	}
	if((len1 != len2) || str1 == 0 || str2 == 0)
	{
		printf("Not an Anagram\n");
		exit(0);
	}

	for(int i =0;i<256;i++)
		if(a[i] != 0)
		{
			printf("Not an Anagram\n");
			flag = false;
			break;
		}
	if(flag)
		printf("The two strings form an Anagram\n");	
}

I guess the best thing is to check if Triangle Inequality holds which states:
1. Sum of two sides should always be greater/equal than the third side.
2. Any side should be greater than equal to the difference of the other two sides.

Here is the working sample. I tried on several inputs and seems to be working. Let me know if I missed some case.

#include<stdio.h>
int getval(char s);
void main()
{
	char s[100];
	int val = 0, val1=0, val2=0, val3=0, val4, i = 0, flag = false;
	printf("Enter the Roman Number\n");
	gets(s);
	while(s[i] != '\0')
	{
		val1 = getval(s[i]);
		if(s[i+1] == '\0')
			val2 = 0;
		else
			val2 = getval(s[i+1]);

		if(s[i+2] != '\0')
			val3 = getval(s[i+2]);
		else
			val3 = 0;

		if(s[i+3] != '\0')
				val4 = getval(s[i+3]);
			else
				val4 = 0;

		//Checking for the case where a numeral repeats more than 3 times
			if(val1==val2 && val2==val3 && val3==val4)
				flag = true;

		//Pick up the first two characters
		if(val2 !=0 && val1 < val2)
		{
			//Only subtraction of powers of 10 is allowed so V or L can't be there before the larger number
			if(s[i] == 'V' || s[i] =='v' || s[i] == 'L' || s[i] == 'l')
				flag = true;
			//do not subtract a number from one that is more than 10 times greater
			if(val2 > val1*10)
				flag = true;
			//If another letter follows the larger one, it must be smaller than the number preceding the larger one.
			
			if(val3 > val1)
				flag = true;

			if(flag)
				break;
			
			else
			{
				val = val + (val2 - val1);
				i = i+2;
				flag = false;
			}
		}//END OF INNER IF
		else
		{
			val = val + val1;
			i++;
		}//End of OUTER IF
	} //End of While
	if(!flag)
		printf("The Integer Value computed is %d \n", val);
	else
		printf("Incorrect Input\n");
}

int getval(char s)
{
	switch(s)
	{
		case 'I': return(1);
					 break;
		case 'V': return 5;
					 break;
		case 'X': return 10;
					 break;
		case 'L': return 50;
					 break;
		case 'C': return 100;
					break;
		case 'D': return 500;
					  break;
		case 'M': return 1000;
					  break;
		case 'i': return 1;
					 break;
		case 'v': return 5;
					 break;
		case 'x': return 10;
					 break;
		case 'l': return 50;
					 break;
		case 'c': return 100;
					break;
		case 'd': return 500;
					  break;
		case 'm': return 1000;
					  break;
	
	}	

}

The output should be a subsquare surrounded by all black pixels. This can be done by keeping a list of all white squares and running BFS from each white square. The white squares can not be from first row or column and last row or column. When running BFS pick up any one node and travel level by level eliminating branches that cannot satisfy the constraints. Also eliminate these nodes from the list of white squares. If you are able to find an enclosed boundary then just check if the enclosed boundary has k*k dimensions.This can be done by keeping track how much we have moved in y direction and x direction.

We can also do this by taking XOR of the number we need to check with all the numbers in the array. If it comes to 0 then the no is there else it's not there in the array. This method is good only when you need to do the find operation few times but if you want to the find operation a lot many times then vijay's solution is the best.

Here is the code to convert a binary tree to a single link list. Now in order to convert it to a doubly linklist we simply need to scan it once and assign prev pointers....


void main()
{
tree_node * temp = root;
while(temp->left)
temp=temp->left;
convert_to_linklist(root);
root = temp;
//siblinglink(root);

while(root->right)
{

printf("value is %d\n", root->val);
root = root->right;
}
printf("value is %d\n", root->val);
}
void convert_to_linklist(tree_node * root)
{
if(!root)
return;
tree_node * temp = root->left;
if(temp)
{
while(temp->right)
temp = temp->right;
temp->right = root;
temp = root->left;
root->left = NULL;
convert_to_linklist(temp);

}

temp = root->right;
if(temp)
{
while(temp->left)
temp = temp->left;
tree_node * te = root->right;
root->right = temp;
convert_to_linklist(te);

}
}

Here is the code to convert a binary tree to a single link list. Now in order to convert it to a doubly linklist we simply need to scan it once and assign prev pointers....

void main()
{
        tree_node * temp = root;
	while(temp->left)
		temp=temp->left;
	convert_to_linklist(root);
	root = temp;
	//siblinglink(root);
	
	while(root->right)
	{
		
		printf("value is %d\n", root->val);
		root = root->right;
	}
	printf("value is %d\n", root->val);
}
void convert_to_linklist(tree_node * root)
{
	if(!root)
		return;
	tree_node * temp = root->left;
	if(temp)
	{
		while(temp->right)
			temp = temp->right;
		temp->right = root;
		temp = root->left;
		root->left  = NULL;
		convert_to_linklist(temp);
		
	}
	
	temp = root->right;
	if(temp)
	{
		while(temp->left)
			temp = temp->left;
		tree_node * te = root->right;
		root->right = temp;
		convert_to_linklist(te);

	}
}

Allocate 32 signed long variables for taking a count of 0 and 1. Total memory taken so far is 8*32 = 256 bytes. Now input the numbers one by one and scan the bit pattern of the number. Highest MSB corresponds to the integer 32 and LSB corresponds to integer 1. Now if the MSB is 1 increment the value of integer 32. If it is 0 decrement it by 1. Do it for all the bits. After you finish scanning all the numbers in the file, go through integers 32 to 1 and that will give you the bit pattern of the number missing in the file. This solution is based on the assumption that the total number of numbers is a power of 2 and the fact that when we write bit pattern for all the numbers all the column in the bit pattern will have the same number of 0s and 1s.

Please correct me if I am doing something wrong above.

Care must be taken while calculating the slope as it can be infinity too i.e. when line is perpendicular to x axis...

The solution to the above problem is as follows:
You have to divide the total no of floors into groups in such a way that the worst case never increases across the groups. For e.g. lets say u decide to have the first group as floors 1 to 14. In the worst case this will take 14 trials. Now you have to choose the second group if you choose the second group of the same size as of the first group then the worst case will have 15 trials. So you have to chose the next group with size less by one than the size of first group. So you will end forming groups of sizes 14,13,12----1 which is nothing but a series. So what should be the optimum size of the first group. That should be equal to the no. of groups you can divide all the floors into. With 14 groups you can include all the 100 floors. If you think of 13 as the solution then its not possible as you can not divide 100 floors in 13 groups and ensuring that each group size is less by one than the previous group.

oh ok got it u r doing in 7 steps I forgot that part....