Cerberus14's blog

By Cerberus14, history, 6 weeks ago, In English,

There are n basketball teams in the world. The ranking of these teams from the previous year is available. This year, some of these n teams played against each other and the winner of each game was determined. There were m games in total. The International Basketball Association wants to introduce a new performance criterion, called “domination factor”, defined as follows: Team i is said to “dominate” team j if we can find a chain of games such that j was beaten by a team that was beaten by a team that was beaten by a team ... that was beaten by i (observe that, according to this definition, domination can be bi-directional, i.e., i and j can dominate each other). Then, for each team i, the domination factor Di is defined as the rank of the best team (that is, the highest ranked team according to last year’s rankings) that is dominated by team i.

Use DFS to devise an O(m + n) time algorithm to compute the domination factor for all the n teams.

Read more »

 
 
 
 

By Cerberus14, history, 8 months ago, In English,

Given a string s with size n, how do I find the minimun range (p,q) such that all the characters in s occur in that range. Looking for an O(n) solution.

Read more »

 
 
 
 

By Cerberus14, history, 8 months ago, In English,

The array A is not sorted and has n distinct integer elements. Our aim to find k<=n elements that are closest to the median of this array. The distance is in terms of absolute value of the element and median's difference. The algorithm asked must have O(n) complexity.

Read more »

 
 
 
 
  • Vote: I like it  
  • +18
  • Vote: I do not like it  

By Cerberus14, history, 16 months ago, In English,

Hello everyone! I encountered a problem at work. I have to search from 1000000 strings that are built from only 0's and 1's if any of them is at least %80 percent similar to an arbitrarily given string. By similarity I mean hamming distance. The thing is linear searching is no good enough to make it in at least 0.2 seconds. All strings are of the same length which is 64 characters. Any help or suggestion is welcome, have a nice day!

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it