nosyDeveloper
BAN USER- 1of 1 vote
AnswersThere is an array of characters, say A[ ] and there is another array of doubles of equal size say W[ ]. Need to design a method called randomChar( ) that will return a character, but the probability of returning a character at index i ie. A[i] will be W[i].
- nosyDeveloper in United States
eg. A = ['a', 'b', 'c']
W = [0.3, 0.5, 0.2]
Then randomChar() called around 100 times should return approx 30 times 'a', 50 times 'b' and 20 times 'c'.
My approach was calculating cumulative probability for the array, eg. W' = [0.3, 0.8, 1.0], then generating random number between 0 and 1 and finally looking up the cumulative array for the right range of the number using binary search. The main problem was the modifications to the normal binary search to check the correct range of generated random number.| Report Duplicate | Flag | PURGE
Yahoo Software Development Manager Algorithm - 0of 0 votes
AnswersWe maintain stock prices of various companies. A stream of stock updates are coming in the form of ticker and value pair (example YHOO, 36.00). This value needs to be updated. We have a module of GUI that always displays top 5 stock prices at any given point of time. How would you maintain these values in memory?
- nosyDeveloper in United States
My solution was to maintain a max-heap and a map that maps ticker to the corresponding node in the heap. At every update, we look-up the node and update the value, but also note if it is an increase or decrease in value. If increase, we do a sift-up, if decrease, we do a sift-down on the heap for that node. For giving the top five values at any point of time, we don't want to disturb the order in the heap so we would copy the top five levels to a different memory and then perform 5 extract and heapifies on it.| Report Duplicate | Flag | PURGE
Yahoo Software Development Manager Data Structures - 0of 0 votes
AnswersWrite an interface for HashMap.
- nosyDeveloper in United States| Report Duplicate | Flag | PURGE
Yahoo Software Development Manager Java - 0of 0 votes
AnswersWe maintain stock prices of various companies. A stream of stock updates are coming in the form of ticker and value pair (example YHOO, 36.00). This value needs to be updated. We have a module of GUI that always displays top 5 stock prices at any given point of time. How would you maintain these values in memory?
- nosyDeveloper in United States| Report Duplicate | Flag | PURGE
Yahoo Software Development Manager Data Structures
public class NewTest{
// to search for the given range
static int binSearch(double[] W, int start, int end, double random){
if(start==end)
return start;
int mid = (end - start)/2;
if(random <= W[mid])
return binSearch(W,start,mid,random);
else
return binSearch(W,mid+1,end,random);
}
static char generateRandom(double[] W, char[] A){
double random = Math.random(); //random double between 0 and 1
return A[binSearch(W,0,W.length-1,random)]; //
}
public static void main(String[] args){
double W[] = {0.2, 0.3, 0.5};
char A[] = {'a', 'b', 'c'};
//calculating cumulative probability
for(int i=1; i < W.length; i++){
W[i] = W[i-1]+W[i];
}
//calling multiple times and counting - for test only
int count[] = {0,0,0};
for(int i=0;i<10000;i++)
{
char r = generateRandom(W,A);
count[r-'a']++;
}
for(int i=0; i<count.length; i++)
System.out.println((char)('a'+i)+" - "+count[i]);
}
}
The size of your List arr will be 100. Also, what if the probability of a character to appear is 0.001? You seem to round it to a 0 in your code.
- nosyDeveloper November 22, 2013O(n) sequential approach. Question is asking for a binary search approach.
- nosyDeveloper November 22, 2013As mentioned in question, these weights and characters are given once but the randomChar() is called multiple number of times. You are doing a O(n) for each of these calls. A good approach would be finding cumulative probabilities in one parse initially. And then whenever the randomChar() is called, you do a binary search with complexity O(logn).
- nosyDeveloper November 22, 2013@Niraj If u are passing same nodes of course it WILL and SHOULD return true and not check further. If they are not the same, then it returns true if BOTH nodes are NULL. Please support your down vote with another example. Did you care to do a dry run on any specific example?
- nosyDeveloper November 22, 2013if u or v are null, the u.left and similar operations will get u null pointer exception.
- nosyDeveloper November 22, 2013Yes it will. Do a dry run, for the root1 and root2 nodes, none of the if's will fulfill and therefore what will execute is:
return matches (left1,left2) && matches(right1, right2)
where matches(left1, left2) will return you a false, since left2 is null (3rd if).
Even though matches(right1, right2) returns a true, the output is false since it is an AND operation.
What if you have a stock value in top-5, say MSFT and the value goes down. You need to check if there is a new contender for the top-5 spot among all those other tickers that were discarded while building the heap last time. One way is to build it all over again - O(n). Expensive, isn't it?
- nosyDeveloper November 22, 2013How do u plan to find top-5 elements with min-heap?
- nosyDeveloper November 22, 2013Sorry did not understand what u meant by "finish the task". We do want the task to be finished, don't we?
- nosyDeveloper November 22, 2013My answer was a recursive function:
boolean matches(Node node1, Node node2){
if(node1==node2)
return true;
if(node1==null && node2!=null)
return false;
if(node1!=null && node2==null)
return false;
return matches(node1.left,node2.left)&&matches(node1.right,node2.right);
}
I don't think we need to often delete the tickers. And even if we need to, we can always update the value of stock to 0 to push it down.
- nosyDeveloper November 22, 2013My solution was to maintain a max-heap and a map that maps ticker to the corresponding node in the heap. At every update, we look-up the node and update the value, but also note if it is an increase or decrease in value. If increase, we do a sift-up, if decrease, we do a sift-down on the heap for that node. For giving the top five values at any point of time, we don't want to disturb the order in the heap so we would copy the top five levels to a different memory and then perform 5 extract and heapifies on it.
- nosyDeveloper November 22, 2013What does a HashMap with three arguments supposed to mean?
- nosyDeveloper November 22, 2013My approach would be to use a Map, say positionMap of type <int position, MapAndHeap>
The MapAndHeap class will have a map and root of max-heap:
class MapAndHeap{
Map<char, HeapNode> charToNodeMap; //character in a heap
HeapNode max_heap_root;
}
The inserts will be done like this:
Parsing every new line keep a counter of which character number are you reading from the left. Check positionMap to see if you have a value for the key position number. If not create a MapAndHeap object (set right values) and insert. If present, check in the charToNodeMap if this character has a value in the map, if yes, increment it and do a sift-up. If not, insert a new node with frequency 1 from the root of the max-heap.
Making suggestion / Look-up:
If the user has typed till position p, you want to suggest character for p+1 position. Look up positionMap and get the root of the max-heap.
One important thing to question the interviewers at this point is, for a particular class, say A, are all the calls of method printA() for the same object or do each of the threads have their own instances? In case, which is most likely the case, that all threads have their own objects, printB() methods will take much less time.
Since the methods are synchronized, the caller thread needs to acquire a monitor for that method. In case of the method being static, this monitor is class-specific, so essentially every thread tries to acquire a single monitor.
In case the method is non static like printB() each of the objects have their own monitors for the method. Since every thread is the only entity trying to acquire lock on object specific method-monitor in respective objects, these threads can work parallely.
Result, printB() takes much less time.
[Corrected, thanks to user fReaK]
Hope you can explain what a BST is. It is a binary tree ie. each node has at most two child nodes. And the other criteria are that the left child is less than or equal to the root node value and the right child is greater than the root node in value - for each node.
Since it is not balanced, the time complexities will be following for worst case:
Lookup/Search = O(n)
Insertion = O(n)
Deletion = O(n)
You can also mention that the worst case occurs when all nodes are inserted on only one side of previous nodes - ie. they become more like a linked list.
Don't you think you should store value in your MIN-HEAP rather than Time? And moreover, time is not something that is given as a value - the problem statement is giving you a set of stock value for various companies that were observed over a period of time.
- nosyDeveloper November 19, 2013Good algorithm. But why did u create an additional level of Map structure to store number of characters and then the Map of keys and word lists? You could have just had a HashMap<String,ArrayList<String>> to store your key and list of words that are anagrams.
- nosyDeveloper November 19, 2013I liked the algorithm, however I think the worst case lookup time for this approach can be of the order O(n). Consider the case when your stream has all distinct characters for the first half and the same stream repeats in the next half and there is just one more element at the end that is appearing the first time.
eg. c1,c2,c3,c4,...,cN,c1,c2,c3,c4,...cN,c(N+1)
In this case, your linked list would be value(c1)->value(c2)-> ... -> value(cN)->value(c(N+1))
The lookup will be of the order of O(N) since all the values are null from the root till tail except the last one since those had duplicates.
Of course, you can argue that number of characters are distinct constant. If that is acceptable assumption, O(1) stands good.
@Aasen start/end pointers may actually not work because you are juggling the characters in the string for every permutate() call. start/end indices can not really specify the two parts of the string given the order of characters will change.
- nosyDeveloper November 17, 2013The interviewer is obviously trying to test your knowledge on various types of testing techniques. It would be wise to talk about testing each feature separately (unit tests) - you can give examples here like : Searching for products and filtering them by brands, price etc while covering corner cases eg. in case of price, if the exact price entered is included or not? Once you have made sure all features are working fine, you would want to perform what is called Integration Testing, features that are interdependent on each other, work file together or not? Again give examples here like after placing an order do I get an email with appropriate details? Then there are more types of testings that are done. Like security, where you run tools to hack into the website. Stress Testing, where you are trying to check performance of the website under high load, say on Black Friday?! Checkout various other testing techniques and try to give as many examples as possible in context of Amazon.com.
- nosyDeveloper November 17, 2013This solution uses 3 pointers - current, result and next. It is as good as using next, previous and current (in fact, the same approach). Although it works fine, it doesn't fulfill the "1 pointer" criteria of the question.
- nosyDeveloper November 06, 2013There is really no point for recursion here. I think that using recursion at these places is actually not a good practice. Though on a similar lines using iteration, this code looks more efficient to me:
Nodeptr nthInInorder(Nodeptr root, int x){
Nodeptr curr = root;
int countedIn = 0, leftchildren = 0, currIn=0;
while(curr!=NULL){
if(curr->left == NULL)
leftchildren = 0;
else
leftchildren = (curr->left)->data + 1;
currIn = countedIn + leftchildren + 1;
if(currIn == x)
return curr;
else if(currIn > x)
curr = curr->left;
else if(currIn < x)
{ countedIn = currIn + 1;
curr = curr->right;
}
}
return NULL;
}
#include<stdio.h>
typedef struct nod *Nodeptr;
typedef struct nod{
int data;
Nodeptr next;
} Node;
void printList(Nodeptr curr){
while(curr!=NULL)
{printf("%d\t",curr->data);
curr=curr->next;}
}
Nodeptr makeNode(int data){
Nodeptr newnodeptr = (Nodeptr)malloc(sizeof(Node));
newnodeptr->data = data;
newnodeptr->next = NULL;
return newnodeptr;
}
void kReverseList(Nodeptr *root,int k,int m){
Nodeptr prev,curr,next,prevtofirst,lastnode;
curr = *root;
prevtofirst = NULL;
int counter=0;
while(curr!=NULL){
counter=0;
prev = NULL;
lastnode=curr;
while(counter++<k&&curr!=NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
} //end of k counting
if(prevtofirst == NULL)
*root = prev;
else
prevtofirst->next = prev;
lastnode->next = curr;
counter =0;
while(counter++<m&&curr!=NULL){
prev = curr;
curr=curr->next;
} //end of m counting
prevtofirst = prev;
}
}
int main(){
Nodeptr root = makeNode(10);
Nodeptr x1 = makeNode(20);
Nodeptr x2 = makeNode(30);
Nodeptr x3 = makeNode(40);
Nodeptr x4 = makeNode(50);
Nodeptr x5 = makeNode(60);
Nodeptr x6 = makeNode(70);
Nodeptr x7 = makeNode(80);
Nodeptr x8 = makeNode(90);
Nodeptr x9 = makeNode(100);
root->next=x1;
x1->next = x2;
x2->next = x3;
x3->next = x4;
x4->next = x5;
x5->next = x6;
x6->next = x7;
x7->next = x8;
x8->next = x9;
printList(root);
kReverseList(&root,3,2);
printList(root);
return 1;
}
using this sort of circular queue will make the worst case comparisons as 2*n, ie. when the last value is the only solution, this is still in the order of O(n)
- nosyDeveloper January 27, 2013
- nosyDeveloper June 12, 2016