topgun.in
BAN USER- 0of 0 votes
AnswersGiven constant integers x and t, write a function that takes no argument and returns true if the function has been called x number of times in last t secs.
- topgun.in in United States for R&D| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Algorithm
The underlying idea is that XORing a number with itself makes it zero, i.e. a XOR a = 0
e.g. consider an array with elements from 1 to 5 in any order of which a number, say 3 (=x) is replaced with 7(=n). For simplicity let us assume that the nos. in the array are in order (it is not required).
1 2 7 4 5 -> arr[5]
1 2 3 4 5 -> Sequence from 1 to 5
XOR them all and identify n = 7 (>5)
y = 1^2^7^4^5^1^2^3^4^5
Note that, except for 3 and 7 all nos. appears twice in the XOR thus they will end up being zero. Hence the result of XOR is,
y = 7^3
Now, we can compute x as follows,
x = n ^ y
=> x = 7 ^ (7^3)
=> x = 3
XOR all the elements in the array and nos from 1 to 1000. Let x be the element replaced with n. After the operation we will be left with x XOR n, call it y. Since n>1000 , it can be easily determined by another scan ( or can be tracked while XOR operation). Once n is known, x equals n XOR y.
- topgun.in January 16, 2012Hashtable is for dictionary operations like INSERT, DELETE, SEARCH. whereas Search trees can be used for dynamic-set operations including SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT and DELETE. Thus, a search tree can be used both as a dictionary and as a priority queue.
- topgun.in January 16, 2010
Right. O(log n) solution is not possible. Since the numbers in the array are not ordered there is no way to split the input into two parts and be able to select one over the other.
- topgun.in January 24, 2012