Selmeczy, Péter
BAN USERhttp://www.linkedin.com/in/peterselmeczy
Sorting the array has overhead: time for sure + space, if you are be allowed to mess up the original array!
For most "fast" sorts O(n log n) has a big constant multiplier for small Ns. So it might or might not be feasible. For small Ns a simple (e.g. insertion) sort with worse asymptotic behaviour could be better.
Hash tables are quite generic stuff. You can use a hash table but the hash function should be a bit more sophisticated than the character value (with Unicode this is 16 bits, resulting in a potentially huge hash table). A hash functions to add up/XORing the two bytes of the unicode char will do, size of hash table is reasonable (256 items). This case the items are linked lists of (char, count) pairs.
- Selmeczy, Péter January 06, 2012Trie is the simple solution for the simple developers ;)
The small challenge comes when pressing 'J' to search should show you names like "John May" and "May, John" as well (two Tries can solve it somehow).
A bigger one comes when the 'J' can be anywere in the name. Trie is out of scope in this case (as far as I see).
And the real one comes when it is a phonebook with Chinese names (oh, yeah, the World is not ASCII, it is Unicode!) and you have to search for "li" (read: show names where the pronounciation of the stored Chinese/Unicode character starts as "li")
Another interpretation can be that the key sequence should match the letter that are on the key - e.g. '2' should be OK for 'a' or 'b' or 'c' and so on. So '25' should match "Al". The word "telephone keypresses" suggest this kind of interpretation.
Oh, and another issue to handle with Tries is the letters that are treated as equals when matching - like n and ñ, but they are different in the real names.
OK, let me re-word a bit: You have to test for "is a number" and "is an anagram"
These two are independent and I don't think it is a good idea to come up with mixed test cases (like anagram but not number)
Plus you need to consider the special cases like empty, very long, etc.
You test for the BOTH conditions and then/or before for the special cases.
At least this sounds logical for me - I am not a tester just a developer...
But testing for "is a number" requires a lot more clarification of what a number is e.g. for an engineer a complex number _is_ a number ;) so 3+4i and 4+3i are nice anagrams and .31415E+1 and +1.3514E1.
I'd definitely as what they mean by "two numbers"? Are they ints?
Can they be decimals? Floats/doubles? Signed/unsigned?
Or strings? (like the first comment suggested)
"case deafult:" should read as "default:" (spelling + no case)
Plus extra '('s in case 2 & 3 & default.
Do you really think (or the interviewer?) that a hash-table is the best for implementing a phonebook? I am quite puzzled after working with phonebook for about 12+ years...
The most used operation on phonebook is displaying the content fast and retrieving the contacts in some order (that varies) and with filtering for different conditions (like search for the first/few characters or pronounciation).
I doubt that a hash-table will help solving these fast.
Changing the content happens so rarely compared to retrieval that it does not really matter how fast/slow it is.
Of course this is just one point of view.
That is OK, but you haven't answered the question.
You answered the question: "What does immutable mean?"
The question was why STRINGS are immutable.
This is not correct. Constant strings might be allocated there, but not all strings. Otherwise how could you construct a new string?
- Selmeczy, Péter December 22, 2011Suppose that int is 32 bit (if not choose an integer-type that is)
1.
#include <stdio.h>
char *to_hex(int x) {
static char buffer[9];
sprintf(buffer, "%08X", x);
return buffer;
}
int main() {
int x = 0x1234ABCD;
printf("ToHEX: %s\n", to_hex(x));
return 0;
}
2.
include <stdio.h>
char *to_hex(int x) {
static char digits[] = "0123456789ABCDEF";
static char buffer[9];
int i;
for (i=0; i<8; i++) {
buffer[7-i] = digits[x & 0xF];
x >>= 4;
}
return buffer;
}
int main() {
int x = 0xF1234ABC;
printf("ToHEX: %s\n", to_hex(x));
return 0;
}
First of all it is important to know what removeElement(n) means. Should it remove ALL nodes where the value is n or just the first one.
Suppose that it should remove all AND suppose that removing really wants to remove items that were inserted into the queue and not called with infitine random values.
In this case you can build up hastable when removeElement(n) is called, add n there, and modify get() to skip the elements if found in the hashtable. Furthermore modify put so when "n" is added again remove it from the hash-table.
If removeElement(n) should remove only the first instance some modifications needed to the additional hash-table handling (get should skip the element and remove it from the hash table as well)
Using a stack is the obvious answer but this is pretty much equals to do-it-yourself-recursive.
- Selmeczy, Péter January 10, 2012