rmn
BAN USERMost people suggested to use a TreeMap. If you use a TreeMap, both insertion and query will cost O(logN)
It's possible to do insertion in constant time by using a List of the below struct:
struct Order
{
DateTime time;
long orderCount;
long cumulativeOrderCount;
}
This list will be naturally sorted by time.
Whenever a query is performed, do a binary search on the list to find start time and end time (or the closest values) and return the difference in cumulativeOrderCount values.
This way, insertion is constant time, and only query is O(logN).
Actually this is a pretty standard question, so I disagree with the disclaimer. The exact same question (worded differently) can even be found in Gayle's Cracking The Coding Interview book.
Answer is 10, every pig will represent a bit, and you need 10 bits to represent 1000 numbers.
class CircularQueue<T>
{
int cap;
int count = 0;
int front = 0;
int rear = 0;
T[] arr;
public CircularQueue(int cap)
{
this.cap = cap;
arr = new T[cap];
}
public bool Enqueue(T item)
{
if (count == cap)
return false;
arr[rear] = item;
rear = (rear + 1) % cap;
++count;
return true;
}
public T Dequeue()
{
if (count == 0)
return default(T);
T ret = arr[front];
front = (front + 1) % cap;
--count;
return ret;
}
}
I cannot think of an in-place algorithm right now. but what we can do is:
1. Find the median in O(n) time using quickselect.
2. Using two pointers (one for the elements smaller than the median and one for the larger) copy the elements over to a buffer array preserving the relative order. Smaller elements will be placed in the buffer starting from index = 0 and larger elements will be placed in the array starting from n/2
We also need to handle both of the cases where the original array has even/odd number of elements.
Trivial Method:
a. DFS both trees and save the leaves of each tree in two separate lists
b. Compare the two lists one-by-one and return the first non-matching pair.
I feel like the method above is very inefficient. Because you have to make a list of all the nodes in every case unnecessarily when you have a chance to early exit.
One thing I can think of right now is to use multi-threading. By the help of a mutex, each tree will traverse (depth-first) 1 leaf at a time, save it to a common container, and return when there's a mismatch.
For example:
- Tree 1 starts DFS, finds a leaf, saves it to a tmp variable, releases the mutex.
- Tree 2 gets the mutex and does DFS until it finds a leaf, and compares the leaf value to tmp. If there's a mismatch, function returns, if it's matching, it releases mutex, and Tree 1 takes the mutex, and back to step (1).
Ravi, yes, I was just going to mention bloom filter, I think it's the perfect application for it.
- rmn November 27, 2016Instead of making an expensive data store look up to see if a card is fraud every time somebody makes a transaction, which there would be many, we should keep a bloom filter in the memory.