pc
BAN USER 0of 0 votes
AnswersFind out if there is cycle in Directed graph
 pc in United States Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures  1of 1 vote
AnswersGiven billions of Rectangle, find rectangle with minimum area overlapping to a given point P(x,y)
 pc in United States
There is a simple way to achieve answer in O(n) by processing each rectangle sequentially, but optimize it further provided large number of Rectangle array. Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures  0of 0 votes
AnswersHow to debug deadlock or heap corruption from DUMP using WinDbg tool?
 pc in United States Report Duplicate  Flag  PURGE
Microsoft SDE2 Debugging  0of 0 votes
AnswersDesign classes and interface for BookShelf
 pc in United States Report Duplicate  Flag  PURGE
Microsoft SDE2 design  1of 1 vote
AnswersGiven a file, read last n lines from the file
 pc in United States
string ReadNLines(sttring fileName, int n); Report Duplicate  Flag  PURGE
Microsoft SDE2 Algorithm  0of 0 votes
AnswersImplement Priority Queue
 pc in India Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures  0of 0 votes
AnswersImplement Least Recently Used Cache for IPAddress lookup. Assume max cache size is 1000 but it should scale well with larger number
 pc in India
Key of the cache is server name and value is IPAddress. Report Duplicate  Flag  PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures
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.
 pc June 13, 2015This 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.
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 n1
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?
Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for nonthreaded 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
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
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?
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[Length1  (n % length)] assuming it was left rotation
or a[(Length1 + (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
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)
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.
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 ( W150) 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 34 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 67 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.
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
}
}

pc
June 02, 2015 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
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
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
For (i>=k)
 pc April 08, 2016{
move to ik
}
for (i<k)
{
move to (nk+i)
}