kasi.beck
BAN USERI think solution should be some program using IO (but not one like scanf) or network connection or DB connection.
e.g.
1) program that will follow this,
a) write 1 byte at a time to a file upto XYZ MB or kb
b) delete that file
c) repeat steps a, b N number of times, depending on how long you want your prog to run.
2) Keep Sending XX bytes of data to some random ip address (not internal)
3) Assuming you have some RDB connection,
create small table in database and keep inserting and deleting single record in that table.
I think solution should be some program using IO (but not one like scanf) or network connection or DB connection.
e.g.
1) program that will follow this,
a) write 1 byte at a time to a file upto XYZ MB or kb
b) delete that file
c) repeat steps a, b N number of times, depending on how long you want your prog to run.
2) Keep Sending XX bytes of data to some random ip address (not internal)
3) Assuming you have some RDB connection,
create small table in database and keep inserting and deleting single record in that table.
Anon is right, its just moving tail to head.
lets say snake is of size 3 at HEAD->(2,2)->(3,2)->(4,2)->NULL,
then on MoveUp we,
1) update 4,2 => 1,2
2) (1,2) points to (2,2)
2) (3,2) ->NULL
so new list is
HEAD ->(1,2) -> (2,2)->(3,2)->NULL
There will be check to see if snake reaches 0th row, in that case he will die.
Also seperate thread will be adding new elements at the end of LL after N seconds.
to implement moves across all directions it needs to be double LL.
algos solution is good. But to optimize insert and add to O(1) we have to implment our own hash. So it will be array of size (lets say 65535). For any elemtent array index K will be key an value will be array[K]
In that case we need our own hash function, for which we can use md5. So add and remove remains O(1) and getRandom can be pure random by fetching any value of rand(size of array)
We can have array of size 65535.
hash function => decimal value of ( last 4 bytes of md5 ) // maximum will be FFFF which is 65535.
For hash function collision, we can use chaining. So each array element will be linked list of data. If array index chosen by random function has more than 1 element, we can again choose rand(size of linked-list) to get Nth element in that linked list.
I think there can be words of size 1 to n. So big Oh of this is polynomial time.
Algorithm/sudo code,
for i in 1 to 10
{
//search all words of size i in the entire string
find_words(int size,String inputString)
}
Followup question could be how would you optimize it.
Ans : We can run find_words across n threads OR n map-reduce jobs. I am not saying map reduce just because its google, but this is perfect candidate for map reduce.
What if someone wants to search by address or company name or any attribute other than name or number ?
- kasi.beck March 22, 2013I think we need to create trie. There will be contact object.
Contact {
String Name,
String lastName,
String companye,
int[10] phone,
int[10] mobile ...
String address( we can also create address object and add more details if we want)}
there will be seperate trie for each attribute pointing to this object. So phoneTrie, nameTrie,
..etc.
For every update/delete/insert these trie will be updated.