anuj.charm's blog

By anuj.charm, history, 10 days ago, In English,

In the case of implemenataion of dictionary we can use any one among two of important DATA STRUCTURE and they are TRIE and hash table. Implementation of Dictionary using Hash table and TRIE:-------------------- If you want to store wrods and only check whether any word exists in Dictionary then we must use hash table for that purpose. This will provide best space usage and performance. BUT if you want to be able to check prefix existence and count of words or some missing character from word then you have to use trie for this requirement. *Space complexity of TRIE is higher than that of HASH TABLE.

Read more »

 
 
 
 
  • Vote: I like it  
  • -11
  • Vote: I do not like it  

By anuj.charm, history, 3 weeks ago, In English,

This is a very cool approach to overcome a worst case, where time doesnot make such impact as the cost does.

Suppose I have to conduct an interview for hiring candidates for my company. I am not personally able to conduct the interview, as I have failed to do so. So I have hired an employment agency to help with hiring the candidate. Each day the agency will send me a candidate from among n candidates. For any candidate Ci I should only hire him if his is better than all previuos candidates 1...Ci-1. So, for this we have following Algo:

best=0 // The candidate with the least quality (a dummy candidate at start) for i=1 to n
If (Ci>best) //the candidate is better than the best valued candidate, I should hire him
best=Ci

return i; ----------------------------------------------------------- I have gone through many observations, such as the agency will send the candidate randomly and in the worst case we have to hire all the candidates, then the hiring cost will be higher as each candidate came in an order of increasing quality. that worst case is when input is as : 1, 2,.....,N. generating worst case of hiring all n candidates. Here I go for randomized algo which ensures that I could hire maximum of lgN candidates if input of the candidates are in random order. Suppose Ci is the interviewed candidate at any random instant, now if I calculate probability that it is best among all than that is 1/i, and hence same is the probability of his hiring. Now, if I sum up for all candidates, I came up with complexity of 1 + 1/2 + 1/3 +....+ 1/N = lgN. In above approach I must have to ensure that input will be in random order and that can be done with any randomized algo.

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it