CareerCup

log(N) time. sorry again.

Forgot to mention the constraint. solution should work in O(N) time.

This junk site not allowing to edit existing questions. Sorry for the late clarifications.

yes the output list also should be sorted.

how this ensures minimum number of comparison... ?

do a level order traversal, once reached the target node, return next node in the same level if exist.

@ Erasmus - For DFS, you should know the root node. How you find the root from adjacency list ??

Yes you are correct. It was a typo mistake.

1. take an array of size 256 and initialize it to zero.
2. scan the input string from beginning and increment corresponding index of array(ie array[input string[i] ]++ ).
3. scan the input string from beginning and check 1 == array[input string[i] ]. if such exist, input string[i] will be the answer.

Please read the question again....relative position not keeping.

Virtual pointers are implemented by virtual table. For each derived class, there will be one virtual table. So this single table will be applicable for all objects created from the same derived class.

virtual table not related to objects, it is related to derived class.

if the LL is read only - there is another way.
1. traverse list form start to middle and put the data to a stack.
2. from middle to end, pop the data from stack and compare to the current node.

Note: needs to take care about even and odd size list.

This will take O(n) space.

Actual question behind this question is do you know how to serialize and de serialize a binary tree.

There are several mechanism available for the same. Do any traversal(pre\in\post) and represent a null child with a special delimiter(a bit or any special character). Do the reverse to de serialize the tree taken care of delimiter.

1. take 2 pointers which points to the beginning and middle element of LL
2. reverse the LL from middle to end of LL
3. now compare the values pointed by beginning and middle elements. is same increment both pointers. else not a palindrome(break)
4. continue step 3 until second pointer reaches the end
5. reverse the second half of the LL to restore the original LL.

1. initialize smallest_range as MAX_INT
2. keep 3 pointers/index p1, p2 and p3 which points to the first elements of lists L1, L2 and L3 respectively.
3. get the sum of minimum difference using pointed/indexed by p1, p2 and p3
4. compare it with smallest_range and update it, if found smaller.
5. increment the pointer/index of min value found in step 3.
6. repeat step 3 to 5 until the pointer/index of min value is in range.

@Learner - step 2 can be done in constant space. Please check the merge procedure of linked list merge sort.

This can be done in 3 steps:
1. covert the BSTs to sorted linked list (this can be done in place with O(m+n) time)
2. Merge this two sorted linked lists to a single list (this can be done in place with O(m+n) time)
3. Convert sorted linked list to balanced BST (this can be done in place with O(m+n) time)

@aka - yes, you are correct, i dint thought of all the possible cases. I think we can consider the same approach after little modifications. for every element we should consider only a window size of n only.
so for 1,2,3,0,6,1,2,3,0,6, if we considers first 0 as the start point, consider elements only up to second zero(window size 5). this will resolve the issue.

i would say, append the input array to the end of input array. Now the input array becomes a bigger array of size is 2n.
5 4 3 2 1 becomes 5 4 3 2 1 5 4 3 2 1.
Now apply LIS algo. it would give the circular LIS 1 5 .

5 6 7 1 2 3 becomes 5 6 7 1 2 3 5 6 7 1 2 3 and gives the result - 1 2 3 5 6 7.

your approach is right, but there are potential bug in the code:

if(root == NULL) {  
    if(!IsEmptyQueue(Q)) 
      EnQueue(Q,NULL);
      if(root->left)                --> root is null, so will crash it here.
        print("%d",Q->left); --> right node can be the leftmost 
  }

this should be changed to:

if(root == NULL) {  
    if(!IsEmptyQueue(Q)) {
        print front element of the queue
        EnQueue(Q,NULL);
     }
  }

your solution is correct, here the pit falls is how to map a -ve no to the corresponding bit in the bit map.

For each X in the array, you should add 2^(n-1) to get the correct bit position in the bit map. Here n is the no of bits used to represent X (ie, 8*sizeof(X))

Since the modulo operation is distributive, we can reduce the overflow chances further as below

int calp(int x,int y,int z)
{ 
   int t = 1;
   x = x % z;
   for(int j = 0;j< y;j++)
      {
          t = (t*x)%z;
       }
      return t;
}

Hint : (ab) mod n = ((a mod n) (b mod n)) mod n.

here the real question is how to sort a set of numbers based on their MSB.

it can be done by finding all permutation of the given digits without rep, then add each numbers formed. there are totally 4! numbers to add.

Let number = 1234
let sum = 1234.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
5. sum = sum + newly formed number on step 4.

doors with numbers 1, 4, 9 ...
Basically door numbers which is a perfect square is the answer.

Read this 2 files to 2 linked lists. Each node in the linked list will store a digit of the big number.
Now we have 2 linked lists representing 2 big numbers. Now the problem became, addition of 2 linked lists and store the result in 3rd list. This can be done in O(M+N) complexity.

Potential bug in the program. program will crash for input "a" because of ( *(p+1) == 'c').

not handled all cases. Please try with {-3, -2, 1}

here the problem is, to add the next biggest no, we need to check that it is not an adjacent element of already added elements. This will take more time.

Pseudo code :

int maxsubsetsum(int* lst, int numItems) {
	if (numItems < 1 || NULL == lst ) {
		return -1; 
	} else if (numItems == 1) {
		return lst[0];
	}
	else if (numItems == 2) {
		return Max(lst[0], lst[1]);
	}
	else if (numItems == 3) {
		return Max(lst[0], lst[1], lst[2], lst[0]+lst[2]);
	}

	int S[numItems] = {0};
	S[0] = lst[0];
	S[1] = lst[1];
	S[2] = Max(lst[0], lst[2], lst[0]+lst[2]);

	for (int i = 3; i < numItems; i++) {
		int subMax = Max(S[i-2], S[i-3])
		S[i] = Max(lst[i], subMax, subMax+lst[i]);
	}
	return Max(S[numItems-1], S[numItems-2]);
}

please read the question carefully. "you may not use adjutant numbers to count in sum"

@- sameep
how this possible ??
in A[ ] = { 1,2,3,4, 5} max sum i s 1 + 3 + 8 = 12. Here 8 is not there in the input array. did you mean 1 + 3 + 5 = 9 ??

@Ashish - corrected the code.

Node* kSmallest(Node* curr, int* k){
	Node* result = NULL;
	
	if (NULL != curr) {
		result = kSmallest(curr->left, k);
		
		if (NULL == result ) {
			(*k)--;

			if (k == 0) {
				result = curr;
			}
			else {
				result = kSmallest(curr->right, k);
			}
		}
	}
	return result;
}

Node* findSmallest(Node* curr, int k) {
	int smallest = k;
	return kSmallest(curr, &smallest);
}

need some more clarification for void Checkin(long long number) - will it accept already existing number in the pool ??

use a min heap to store the values. so CheckOut() will work in constant time and Checkin() will work in log(N) time.

geeksforgeeks.org/median-of-two-sorted-arrays/

Construct the matrix.

Logic is simple:
Take 2 pointers which initially points to the start of the array. Here first one represents the end of string without 'b' and 'ac' and first represents the current scan position.
scan the array from the start to end
if the current characters is 'b' or 'ac', increment only second pointer appropriately
if the current characters is not 'b' and 'ac', swap characters pointed by two pointers and then increment both pointers.
result will be the string from the start of the array to the location pointed by first pointer.

void removeBandAC(char *p, int size)
{
	int i = 0;
	int j = 0;

	while( i < size )
	{
		if (p[i] == 'b')
		{
			i++;
		}
		else if ((p[i] == 'a') &&  (i+1 < size) && (p[i+1] == 'c'))
		{
			i += 2;
		}
		else
		{
			if (i != J) swap(p[i], p[j]);
			i++;
			j++;
		}
	}

	p[j] = '\0';
}

what abt if all are -ves ?

hi Nitin,

Please check in geekforgeeks about tree diameter. your solution is right, but height and diameter can be found in a single pass.

if the array contain duplicate elements, how this will work ??
suppose the array is : 1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1
This is also a sorted array with rotation.

This is O(N) solution. They are asked for a solution with less than O(N) complexity.

@Dilbert Einstein - there is one more case - the largest 3 nos include 1 -ve and 2 +ve values. so you have to scan the array multiple time.

I think the interviewer asked to find the tree diameter. Tree diameter is the max distance between any two nodes in the tree. This can be found in O(n) time.

No. right children of the given node - if right sub tree exist. otherwise left node is the answer.

@code_monkey - if the array contains duplicates, linear search is required.

all prime numbers(except 2 and 3) are either of form 6k+1 or 6k-1 for some integer k.

@coder - updated the solution.

The efficiency is O(N log1000). since log1000 is a constant, complexity is O(N) only.

public void changeTree(BinaryTree root, int rightSum) {

		if (root != null) return 0;

		int rightValue  = changeTree(root.right, rightSum);
		root.data += rightValue + rightSum;
		changeTree(root.left, root.data);

		return root.data;
	}


initial call should be changeTree(root, 0);

@m3th0d.itbhu - step 14 to 17 will be executed only once for your input. That is when A[i] is 7. Then how the output will be 1*11*12 ???