kanukadze
BAN USER- 1of 1 vote
Answersdetermine whether a word is in a stored list;
- kanukadze in United States
the list doesn't fit into memory;
no disk access allowed, for lookups, memory access only;
no false positives allowed, false negatives ok| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersDesign a service to generate unique 64 bit IDs
- kanukadze in United States| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer System Design - 0of 0 votes
AnswersWrite code for transforming equation into canonical form. An equation can be of any order. It may contain any amount of variables and parentheses.
- kanukadze in United States
The equation will be given in the following form:
P1 + P2 + ... = ... + PN
where P1..PN - terms that look like:
ax^k
where a - floating point value;
k - integer value;
x - variable (each term can have many variables).
For example:
x^2 + 3.5xy + y = y^2 - xy + y
Should be transformed into:
x^2 - y^2 + 4.5xy = 0| Report Duplicate | Flag | PURGE
Coding
@ChrisZ
thanks for walking me through this.
you're right 1<<21 does look strange. there wasn't any explicit cap on memory except fitting into a single box, so prob. just miscalculated. "<<;6" must be a website's formatting issue, no ';' there.
# of words was in billions, and there was a hint of using a hash function with lots of collisions which I interpreted as a way to limit the range => bitarray size.
it was of the two technical questions on a phone screen for senior dev with MS big data team
this is what I came up with, but seems it wasn't good enough:
class WordList
{
const int mask = (1<<6) - 1;
ulong[] ba;
public WordList(string[] l) {
ba = new ulong[1<<21];
foreach(string w in l) {
int h = Hash(w);
ba[h>>6] |= 1ul<<(h & mask);
}
for(int i = 0; i < ba.Length; ++i) ba[i] = ~ba[i];
}
public bool Contains(string w) {
int h = Hash(w);
return (ba[h>>6] & 1ul<<(h & mask)) == 0;
}
int Hash(string s) {...}
}
Each box in the server farm to generate sequential IDs prefixed with unique box id.
class UID
{
static ulong srvId; //unique server id
static ulong mask; //mask to | srvId and val
static long val; //current uid value
public static void Init(int id, int lenght) {
mask = ~0ul >> lenght; //size of id in bits
srvId = ((ulong)id) << (sizeof(ulong) * 8 - lenght);
}
public static ulong Get() {
Interlocked.Increment(ref val);
return (ulong)val & mask | srvId;
}
}
Parsed input into list of Term object (coefficient and mapping from var name to its power value), recursively parsing inside parentheses. Combined likes by mapping from strings representing terms without coefficients (x2y3z) to List<Term>. Sorted by term's highest power value.
- kanukadze October 18, 2016
@ChrisZ
- kanukadze October 19, 2016use of the IDs or desired structure/distribution not specified; the only requirement is uniqueness for as long as possible.