smallchallenges
BAN USER1. Random number => no predictable pattern in numbers generated => the diff between the nos should not be the same, etc
2. Each number in between 0-999 has to have equal probability of occurrence. So, we should maintain frequency counts and verify that no single number stands out w.r.t. frequency.
A single Voicemail message has the following (common) characteristics :::::: Sequential read always, Read in full always, Possibly replayed, but rarely, Small file sizes.
Assuming that a vmail system has to be developed for many users, we need a way to select all messages belonging to one user i.e. no sharing of vmail messages across users.
So, a simple system of one dir per user, with some small files under each directory, is sufficient. I.e. a file system would be sufficient. In addition, backup, replication, dedup and other tools built for a file system can be easily used for the vmail system as well.
I do not much about DBMSes, but it seems to me that we do not have any complex query system that needs to be supported for a vmail system and neither does any complex relationship info maintained. So a DBMS seems like overkill to me.
Run it in a debugger and see where it is dying?
- smallchallenges January 17, 2014Write to a file
+ Most file systems serialize writes to a file. But, we cannot predict the order in which writes end up in a file. So, if you need absolute incoming order to be maintained, then serialize with a lock. This leads to a performance issue due to lock contention.
+ We can work around it by using something like mmap() and just protecting the write offset into the file and taking the actual write out of the performance path i.e. the lock will protect only the mmap offset movement. But, if we assume that the number of bytes logged is less, then we do reduce contention by much.
Write to a per-cpu in-mem buffer and transfer to a file offline.
+ Each cpu can log stuff into its own buffer i.e. no lock contention issues.
+ But, if you need ordering, you have to add a timestamp to each entry that can be sorted offline. This assumes that post processing of the log entries is an allowed relaxation of rules.
+ Still, when the in-core buffer is full, contents need to be written to the disk..so, will logging stall at that time? The usual solution for this is to have two buffers: live and frozen. While the frozen buffer is being written to disk, the live one continues to take the logging entries.
A binary Search tree is an ordered binary tree with *NO* duplicates. So, every digit will occur only once in the tree. So, frequency is 1/(total nodes in the tree). So, the problem, to me, boils down to counting the total number of nodes in the tree.
Am I missing anything people? Lemme know please. Thanks.
I like the trie approach as well, but my logic is slightly diff than Mr. Yoda's.
Create a trie with all the words in the dictionary (from the list)
For each letter from A->Z {
Walk the trie for current letter (say A)
Check if the next valid letter in the trie has a match in the periodic table.
If matches, then descend down the trie.
If not matches && we are at the leaf node in the trie, found a string
Check for biggest string.
}
Q: Is 455 allowed? 55 is repeating, but 455 is not.
- smallchallenges September 24, 2013Another constraint to check is how deep can the directory level get? If directory depth is too high, then a recursive solution may not be preferable.
print_amazon_file_names(directory)
{
add_dir_to_queue(directory);
whlie(queue not empty)
{
list = directory_listing(directory)
while (list not empty) {
if(x is directory and is not "." nor "..")
add dir to queue();
if(x is a filename ) {
if(substring(x, "Amazon"))
print(x);
}
}
}
}
The first thing to do is define the parameters of the cache.
+ What is it caching?
+ Object size
+ Cache size
+ How many users
+ Cache read/write frequency
Do you have more info on the above aspects?
Maybe I am missing something...but here goes my idea.
- smallchallenges January 17, 20141. Allocate one location in the auxiliary array for each color.
2. Pick a ball from the set of 10000 and place it in the auxiliary array.
3. If you get another ball of the same color, replace the one in the auxiliary array with the new one and push the old one back into the 10000 set, but remember not to pick this up.
4. As more balls are moved from the 10000 set to the 500 set, you can insert more from the 500 set into the 10000 set PROCESSED area using insertion sort say.
Is this acceptable?