CareerCup

For (i>=k)
{
move to i-k
}

for (i<k)
{
move to (n-k+i)
}

you are using additional O(n) space.
I am not sure about correctness of your algorithms. Can you explain why you want to move towards minChild or maxChild?

Interviewer has asked not to change the heap

changing heap is not allowed

Let me tell you, customer environment does not entertain you for debugging. You can ask to get logs or other data in a minimal way. Depending upon how mission critical situation is, customer might allow you to do left and right, but in general avoid going into depth at customer end. Just capture the steps customer has taken to reproduce the issue and request for any additional logs might be useful.

While most folks answered to find out two such elements, there is a edge case when both elements to be swapped are adjacent to each other. You need to handle that can as well since you will fin only one instance of value out of order.

This is an O(nlogn) Time complexity solution with O(1) space complexity

1. Sort the array
2. Take two indexes from start and end
3. If values of indexes is equal to sum, this is the answer
else if value is > sum, Move last index down
else as value < sum, move start index up.

This algorithm will change the array.

Just iterate through array, keep two index from start and end for mod%0 and mod%2 sub array. Depending upon where current item should belong, swap it with mod%0 index or mod%2 index, If value is mod%1, do nothing.

Yes this is same Dutch national flag problem

what is the time complexity to access an item from cache? Heap it not good for retrieval of the item

+1
Thanks Binary, With the help of aux array it turns into O(n) algo.
This is something I thought originally but missed to leverage it

As bob said, use a min heap to cache the Jobs.
1. When new Job is added into the cache,
If Heap size is max cache size, remove root and replace with newly added Job. Use current timestamp as node value for comparison. With that new node will move down to leaf node.
2. When an item is accessed from the cache, update it's time stamp to the current time and that will cause it to move down.

However this will not solve the problem of searching an element with O(1) from cache. Therefore an additional Map might be required to point into Heap for efficient retrieval

Lets start with an O(n2) solution.

1. Start from index 1 and iterate through n-1
2. Maintain Left(max) and Right(min) at any point of time
3. If the current element in question is >= Left(min) and <= Right(max) then it is a magnitude pole.
4. As we move right, update Left(max) as max of previous max and current value
5. Right(Min) will be changed iif next element = Right(min), essentially min element of the right list is going to be in the middle. in that case you will have to iterate through Right array to get next min.
Repeat steps till be reach second last element of the array.

The worst complexity is O(n^2) because of the need updating the min of right list.

I am thinking ways to avoid it. One solution could be to copy array into another array and sort it. That way you can know next min number from it, however you will need to maintain both min and max for left and right sub array.
With that it will be O(nLogn) time complexity with O(n) memory complexity

Any other suggestion?

this is a good answer to start with.
However you also need to think for collision. Hash can not be guaranteed to be unique for each unique key

what about collision?

Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.

Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.

One of HashMap's subclasses is LinkedHashMap, so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn't be as easy if you were using Hashtable.

If synchronization is not an issue, use HashMap. If synchronization becomes an issue, you may also look at ConcurrentHashMap, besides HashTable

Are we talking about //en.wikipedia.org/wiki/Search_engine_optimization

Does it mean find first word in the file which is only occurrence in whole file?
2n complexity solution
Can use a map to mark occurrence for each word in the map. in next iteration find the word with count 1.
You can optimize it further to one iteration by maintaining additional metadata of words with 1 count

what is complexity of enqueue and dequeue?

Keep a counter and set it to 0
Assume you have a string or char array of secret password

Read the number from input keypad
If it matches with first digit secret[count] of the password increase counter by 1
If it does not match, resent counter to 0

At any point say counter = k, if input number does not match with secret[k] of the password then resent count to 0; back to square one

Does this answer the question?

Check this http : //ideone.com/VsYvX8

Don't bother about IP Address, focus on a LRU cache with max size. Cache can store any key value pair. IP Address is an example

This is working code, but needs to add check for invalid inputs
like when n <= 0 or a is null

This doesn't look like attempting to solve the problem

This is BFS solution. Traverse the tree by each level and queue it.
In each iteration for each node in the queue, add it's children into queue, and print the node

Is this a trick question? If N is given (number of time rotation done to sorted array), why can't i just access the element at a[Length-1 - (n % length)] assuming it was left rotation
or a[(Length-1 + (n % length)) % length] if it was right rotation

Other answers apply if n is unknown.
Start from mid of the array.
Check both sides of array
if both array first element <= last element, this is the answer
otherwise move towards the array where first element > last element

How does it ensure that Jobs with same priority follow FIFO rule?

How does it ensure that Jobs with same priority follow FIFO rule?

I had another algorithm with O(1) space and O(n * Log k) time complexity.

1. Start with a window of min(2k, items in array). Sort it.
2. First k elements are sorted
3. Move window min(k, items left in array) index ahead
4. Goto step1 till items remaining in the array

sorting 2k Elements O(2k log 2k), n/k times
O(2k * n/k log 2k) = O(2n * log 2k) = O(n log k)

This is good answer but also requires extra space O(k).

Can you elaborate your algorithm, how will to modify the original Insertion sort to sort array in O(N x K) time?

Not sure how this will work? Can you summarize your algo first

Here is a O(logn) solution
1. Start with [0][0] Location and check max value of the Row and Column i.e. [0][ColMax] and [rowMax][0]
2. If the value is outside the range Move diagonally down e.g. Matrix[1][1] and Goto Step 1
If reached last diagnol then return with value not found
3. Search within the Row and Column

Moving along the diagonol is O(log(n)) . Then searching element in the row or column is O(logn) + O(log n) = O(log n). So overall it is O(log n ) algorithm where n is size of the col/row

In this problem I think you are given a Straw being moved by the player and will be asked if it touches any other straw

bool isIsolated(Straw s, []Straw allStraws)
{
// Iterate over all straw and tell if there is any other Straw touching it
return true or false;
}

However other approach could be to preBuild this information at the start of the Game. So you already have information say number of Straws connected to a straw or just a flag to indicate if straw is in isolation

1. Develop an Algorithm to find if two given Line segments intersect
Given two points find
y2 - y1
m1 = ------------- and like wise m2 for line
x2 - x1

Now Line can be y = m * x + b
You get such two equations for each line. Subtract both equations to get y and x of intersection.

2. Check if the Intersection point is actually fall within the rectangle of intersection of both line segments . To do that make sure X is within Min of Right X and Max of the left X. Like wise make sure that Y is within max of bottom Y and Min of Top Y.

Well above two steps tell you whether two lines intersect or not. Now lets build the solution for game using it.

1. Develop an Algorithm to find if two given Line segments intersect
Given two points find
y2 - y1
m1 = ------------- and like wise m2 for line
x2 - x1

Now Line can be y = m * x + b
You get such two equations for each line. Subtract both equations to get y and x of intersection.

2. Check if the Intersection point is actually fall within the rectangle of intersection of both line segments . To do that make sure X is within Min of Right X and Max of the left X. Like wise make sure that Y is within max of bottom Y and Min of Top Y.

Well above two steps tell you whether two lines intersect or not. Now lets build the solution for game using it.

Lets first talk about the solution and the code also

The original question is about a stream of 1 and 0 and when you say stream i guess we are not talking about the classic compression algorithm here.

Also the program you have written, first you should provide subjective description of the solution rather jumping directly into the coding which most of the interviewer don't like

The answer provided by Tom will work here.
As an extension to the problem assume If I also want to optimize the algorithm to transfer max weight as early as possible or say there are chipper options available if the Weight being transferred is lesser then max capacity of 150

I will take this approach in that case:
1. Sort the Boys by Weight in O(nLogn)
2. Iterate over array for each W from highest weight
3. Search for ( W-150) or just smaller to it
4. Transfer the couple of Boy and mark boys transferred. Hire the boat based on sum of weight of both boys
Repeat steps 3-4 till all boys are moved.

This have additional complexity but it is still O(nLog(n))

The problem statement says given bunch of tickets. This needs to be clarified if all given tickets represent a path or there could be tickets which are unrelated or there could be group of tickets for different path.
Lets assume simple case where all tickets are guaranteed to create a path from start to the end,
We can either use Directed Graph approach as Nitin pointed out, but for this problem that would be complex. Alternatively we can use simple approach.
e.g. Going from A to E via B, C, D (A, B) (B, C), (C, D), (D, E)
1. Iterate through each ticket
2. Add source and Destination into the Set. Also keep additional metadata to indicate if added entry is source or destination.
3. However If source of Destination is already in the set remove it.
4. Add Entry into the Map with Key Value as Source and Destination
5. At the end you will have two nodes in the set, start and end point.

Well, now you are loaded with start and end of the tour, just get started.
6. Start from Source left in the Set.
7. Look in the Map for destination which is B
Repeat Step 6-7 till you reach to E.

Note: There is possibility of the Loop within the tour say
e.g. Going from A to E via B, C (A, B) (B, C), (C, B), (B, E)
You will need to handle this case and solution will become more complex. Above problem is just loop of length 1 but it can actually be very large.

I am not clear about the question, actually answer. The combination of output is confusing. Can you provide full set of output for a simple example say "Google"

Will all these be part of the output?
g1ogle
go1gle
goo1le
goog1e

Assuming both streams have equal number of digits, provided smaller number can have sufficient padded 0 to accommodate the difference, I will use this algo

While (GetNextA and GetNextB)
{
   int result = a - b;
  if (result < 0)
 {
   subtract one from previous digit in the result; 
   It should also handle the case of 0 being previous digit, iterate through first non zero 
   Add 10 to the current result digit and append it to the result 
 }
}

b = (s_b.hasNext()) ? s_b.next() : 0;
this doesn't seem correct assumption
Lets say is a is '3' 5' '7' '4'
and b is '5'
you will actually provide result for
4753 -
5000
which is incorrect.

My guess is both stream will be of same length, otherwise it is difficult to calc subtraction

It is not possible to trace -N node from given node in the tree.
However if Head of the list is provided, then it is simple
1. Move one pointer N ahead from head
2. Now Move one pointer from head and another from N, one by one till Given node is found.
3. At this point, you have previous pointer pointing to -N position

This is O(n) solution

head is not provided

how do you know where is 1?

A singleton class will not work as Singleton in these situations
1. If not coded Thread safe
2. Across Process. Each JVM will have it's own Instance of Singleton
3. Using Multiple Class loaders can lead to multiple instances of same class
4. JVM before 1.2, Garbage collector will collect it if not maintained reference of Singleton

We are not running whole quick sort but an iteration of it. Actually doing partition of the array using a virtual 0 partitionIndex, so it should be O(n)

Seems like this is a simple problem of sorting the array and figuring out the gaps in sequence which can be achieved in O(nlogn) + O(n) = O(nlogn)

This problem can be solved recursively as mentioned by Anqshu
Essentially Preorder traversal of a tree looks something like this

Root {PreOder of Left Tree} {PreOrder Of Right Sub Tree}
Find the index of Right Sub tree using number immediate > then root.
And then recursively find preorder traversal of left and right tree

You can use recursive approach to solve this problem. Here is a pseudo code

IsBST(Tree t, int min, int max)
{
  // if (t == null) {
      return true;
   }
   if (t.data < min || t.data > max)
   {
     return false;
   }
  IsBST(t.right, min, t.data) && IsBST(t.left, t.data, max);
}