CareerCup

solution for two array list:-
- O(N^2) - brute force match between two array.
- O(nlogn) - sort both array in O(NlogN), then compare both the list, that will take O(N)
- O(N) - if array is not too big, then store contain of first array in hashmap, then iterate through the second array and check whether number is there in the hashmap or not.


for N integer array , take two array and use above solution, then create a new array with the intersection then use that with next array to find intersection.
repeat the steps till all array is covered.

There are many approach to solve this problem:
- O(N^2) - brute force match between two array.
- O(nlogn) - sort both array in O(NlogN), then compare both the list, that will take O(N)
- O(N) - if array is not too big, then store contain of first array in hashmap, then iterate through the second array and check whether number is there in the hashmap or not.

hi John, can you elaborate the question, as what we have to find. as the statement, find out what numbers comes before- positive or negative. before what.?

you can iterate through the list one checking inadvance with its 3 successor in the list.
if both consecutive it same, then you can discard this, similarly if three consecutive is incremental then discard them.

if you find 'A', then replace with the previous card and assume that can be discarded.

this can be done in O(n). just one iteration of the list.

void fixNode(node *head) {
  if (head == nul) {
    return null;
  }
  if (head->next == null) {
    return null;
  }
  node *temp = head;
  while (temp->next!=null) {
    if (temp->value > temp->next->value) {
	  temp->next = null;
	  return;
	}
	temp = temp->next;
  }

some minor change

How do you plan to return for some number where it can have more than 2 alphabets.

when you vote down, can you explain about your concern.

boolean isBST(node root) {
	if ( root == null || (root.left == null && root.right == null )) {
		return true;
	}
	if ( root.left == null && root.right == null ) {
		return true;
	}
	if ( root.left > root.right ) {
		return false;
	}
	return (isBST(root.left) && isBST(root.right));
}

what if array contains negative numbers.

Thanks X for finding that out...
in that case we have a pointer to the first node from where element are going to duplicate. if temp == firstDupNode, then list is having loop.

if let say more than one elements are duplicate then we have to maintain the firstDupNode to the node which has the duplicate value as temp node.

Can you elaborate how it will fail.

traverse through the array.. keep multiplying all the element, and before mulitplying check whether that product is divisible by the element or not, if yes that element is duplicate.

boolean checkPrime(int []arr, int length) {
  for (int i = 0; i < length; i++) {
    int duplicate[length] = {0};
    int j = 0;
    int product = 1;
     if (product % arr[i] == 0 ) {
        duplicate[j++] = arr[i];
      } else {
         product = product * arr[i];
      }
   }
   if ( j == 0 ) {
      return false;
   } else {
     return true;
   }
}

duplicate will contain all the duplicate prime number.

Can you elaborate this..

add two array in store in one array.

to find median of this new array in o(n+m), you can use median of medians algorithms

en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

you can try this.

stackoverflow.com/questions/9368764/calculate-size-of-object-in-java

what if substring need to be replace?

this will find whether there is loop or not in sorted linked list

boolean isLooped(node *head) {
  if (head == nul) {
    return false;
  }
  if (head->next == null) {
    return false;
  }
  node *temp = head;
  while (temp->next!=null) {
    if (temp->value < temp->next->value) {
	  return true;
	}
	temp = temp->next;
  }
  return false;
}

void fixNode(node *head) {
  if (head == nul) {
    return null;
  }
  if (head->next == null) {
    return null;
  }
  node *temp = head;
  while (temp->next!=null) {
    if (temp->value < temp->next->value) {
	  temp->next = null;
	  return;
	}
	temp = temp->next;
  }
}

void fixNode(node *head) {
  if (head == nul) {
    return null;
  }
  if (head->next == null) {
    return null;
  }
  node *temp = head;
  while (temp->next!=null) {
    if (temp->value < temp->next->value) {
	  temp->next = null;
	  return;
	}
	temp = temp->next;
  }

if loop is there in linked list which is sorted and you want to remove it then,
just check if any node whose next node value is less than current node value, if it is true then point the next pointer of current node to null.

I linked list is sorted then, just iterate through the list and check if you get any node with lower value then the previous node, if yes then linked list has a loop.


if linked list is not sorted then you can you two pointer fast and slow to check the loop

have two pointer faster and slower, increase one node for a slower and two nodes for faster pointer and see when faster pointer reach the starting node again, slower pointer will point to the middle element.

it is applicable only if you have doubly circular linked list.

traversal means iteration. for recursive we have to go to each elements only once, so traversal will be one.

try it recursively..
first go to end of both the list.
from there start adding number and return the carry number.
while in each recursion add the numbers and carry number.
at the end when we reach to the first nodes i.e. the MSB of the number add these and get the carry number. if that carry number is non zero then add one more node to the head with that value.

Y min heap... y not max heap.

return the integer value of that node which is ancestor to both

This is to find least Common ancestor(LCA problem).

have you atleast tried for dry run before giving a negative vote..

Create 3 different list, each containing vowel , digit and consenent.
after that merge all this three list.

Push into stack in sorted order.
As you can modify PUSH and POP.
implement both in sorted fashion.
the top of stack will have minimum element.
so every pop will give you the minimum element.

int stepCount(int stepRemaining) {
    if( stepRemaining == 0 ) return 0;
    if ( stepRemaining == -1 ) return -1;
    return totalNumberOfStep = stepCount (stepRemaining -1 ) + StepCount (stepRemaining -2);

for measuring:
-  an hour 
	- just burn a stick. it will be totally burnt in 1 hour.
- half an hour
	- burn a stick from both side, in half an hour it will be completely burnt.
- for 45 mins
	- burn a stick from both side(stick1). and other stick(stick2) only one side. once stick1 is completely burnt, stop second stick to burn and start burning that stick from both side. it will again take another 15 mins. so total you can complete it in 45 mins.

what if both all balls are more than a kg..:)

i think the question is incomplete. it was find among the five which one is heavier or lesser, that means others are of same weight.

to be more clear..
let say u have a,b,c,d,e.. 5 ball.
take a and b, c and d together and compare the weight between these two sets.
if both are equal so, e is heavier.
if set a and b is heavier then compare the weight between then and find the heavier one, otherwise compare the set of c and d.

take any four ball and compare the weight having in pair of two.
if bith set of ball is equal then the fifth one which is not measured is heavier.
if one of the set if heavier then compare between that two ball.

Can you check now..
updated after .<--> comment.

have a class restReservation, which will have method as,
- tableIsEmpty( int) , will take the number of person for which emtpy table has to find, it will return 0 if all are full, otherwise table number.
- tableBookFor(int starttime, int endtime)


it will have following member,:
- array of elements.
each element will have, table number, table capacity, isBooked, int startime, int endTime,.

its a DP problem, similar to coin change problem, only change is that denomination should not be repeated..

An IEnumerator is a thing that can enumerate: it has the MoveNext, Current, and Reset methods (which in .NET code you probably won't call explicitly, though you could).

An IEnumerable is a thing that can be enumerated...which simply means that it has a GetEnumerator method that returns an IEnumerator.

Which do you use? The only reason to use IEnumerator is if you have something that has a nonstandard way of enumerating (that is, of returning its various elements one-by-one), and you need to define how that works. You'd create a new class implementing IEnumerator. But you'd still need to return that IEnumerator in an IEnumerable class.

For a look at what an enumerator (implementing IEnumerator<T>) looks like, see any Enumerator<T> class, such as the ones contained in List<T>, Queue<T>, or Stack<T>. For a look at a class implementing IEnumerable, see any standard collection class.

int multiply( int a, int b) {
  if (a==0 || b==0)
    return 0;
  int sign = 0, result;
  if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
    sign = 1;
  }
  int a1 = abs(a);
  int b1 = abs(b);
  while (b1--) {
    result + = a1;
  }
  if (sign) {
    return result/(-1);
  } else {
    return result;
  }
}

Use trie structure to store number and while typing the number traverse through all the nodes till all the leaves.

how does it matter, whether the array is rotated or not, if you have to search in rotated array, just do normal search in array...

FindPath of both the nodes from root.
then search for the last common nodes in both the path, that will be the LCA in a tree.

i dnt see the use of factorial in your code.

It is a DP problem, modified version of coin change problem..

how you are sorting and making the bucet in range in linear time..
?
Can you elaborate that

do radix sort and append the digit..

can you elaborate, how this method takes O(n), its goin to take O(n^3)