sathishp123
BAN USER@confused_banda, May be because developers understand program better than reading the text :)
- sathishp123 December 01, 2013You should revisit this condition inside the while loop.
while (isset($array[$i]))
Reason: You're accessing the next two indexes of $i inside the while loop. But checking only the existence of $i.
- sathishp123 December 01, 2013Bloom filters?! (False positive matches are be possible, but there is no false negative);
- sathishp123 November 25, 2013Is it really a Google question?
- sathishp123 November 25, 2013@fafdu1992,
We can't do it without using extra space since
row_count != column_count
. i.e., its not a nXn matrix.
Correct me if I'm wrong.
Are you kidding?! :)
Well, we can do it if quantum computing comes practical!!
The below answer is for lookup for a BT in a list of millions of BT.
We can do it in O(1) time, but it requires preprocessing.
1) Create a string hash for each tree
2) Remember to separate the node values using some separator. for example use left brace & right brace. Also remember to maintain the some sorted order of child's values (either asc, or desc)
3) Insert into a HashMap<String, Tree> map;
During lookup operation, convert the input tree into string (as mentioned in step 2), and look for it in the map.
Complexity:
HashMap addition is O(1) - Amortized.
HashMap lookup is O(1) - Amortized.
Good one.
Its the first time I hear about running two horses in the same track :)
Good one Ajeet. Complexity of this algo is O(n);
Because, theoretically, we can say HashMap's complexity is amortized O(1) Not O(n);
There is a huge chance that this solution will lead into integer overflow.
For example, let s say each number in the array is greater than 6.
Then once we reach 500 million'th number, the total sum will be more than 2^32 (i.e., the sum will be greater than 4.2 billion);
Pls correct me if I'm wrong.
Hi,
What if the string itself contains "\n"?
For example,
stringVector1.push_back("Cracking\nProgramming");
This looks just like an another question. Search for "Find the nth most frequent number in array"
- sathishp123 June 15, 2012Maintain a HashMap<Integer, Integer> to store the number as key with its count as value. Use two other variables to keep track of the max count and its corresponding key.
For ex:
public static void main(String[] args) {
int[] a = {3,3,3,5,10,44,11,44,100,102,102,102};
System.out.println(getNthMostFrequent(a));
}
/**
* @param a - array of integers
* @return most frequent number in the given array. returns -1, if the array is empty.
*/
public static int getNthMostFrequent(int[] a) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int maxCount=0, freqValue = -1;
for(int i=0; i < a.length; i++) {
if(map.get(a[i]) == null) { //Insert new.
map.put(a[i], 1);
}else { //Already exists. Just increment the count.
int count = map.get(a[i])+1;
map.put(a[i], count);
if(count < maxCount) {
maxCount = count;
freqValue = a[i];
}
}
}
//incase all numbers are unique.
if(freqValue == -1 && a.length>0)
return a[0];
return maxValue;
}
Trie is the answer. try this wiki page: en.wikipedia.org/wiki/Trie
- sathishp123 June 12, 2012Have a flag in the node, set it to true once you visit it and increment the counter.
Finally the counter is the size of the list!!
I think O(2^n) because we've 2^n different possibilities. So its correct.
- sathishp123 June 15, 2011Windows doesn't allow to delete the files which are in use.
- sathishp123 June 15, 2011Adding to this: It is possible to find the top 3 horses in 7 rounds itself.
- sathishp123 June 15, 2011its good to test the numbers at their boundary conditions. for example, try with the max/min limit of integer (which may lead to overflow in the program). because the program may use i++ or i-- operators.
- sathishp123 June 15, 2011
Interval Tree.
- sathishp123 December 26, 2013