Selmeczy, Péter
BAN USERTo make a design that works for the simple/good cases is easy. I go for the hard/bad cases, try to figure out what will could go wrong and make the design fail. Some call me "negative person", I call myself a "realist" ;) Think twice, work once.
You function must always return T*, so
if(root == NULL)
return;
should be
if(root == NULL)
return NULL;
"while(node !== null)" should be "if (node !== null)", otherwise it is a nice infinite loop - node is not assigned to a new value inside the loop ;)
- Selmeczy, Péter December 18, 2011Are you sure it works for 101? Actually to any number formed X0Y?
And for 0? [OK, this is easy to add]
Actually this "peak" stuff came into my mind as well during having lunch :)
Imagine that the numbers are heights on a terrain and you walk uphill/downhill. The end of the monotonous sequences are the peeks and valley-lows.
In other words:
Keep the first element. Then find the monotone growing or shrinking parts of the sequence and keep the last element from all of these sequences.
E.g.
1<3<5<6>2<8<9>3>1<7>3
^ ^ ^ ^ ^ this is where
the "directions" are changing.
So 1, 6, 2, 9, 1, 7, 3.
I found this solution but I don't see/can't prove why this is good :(
You cannot change the order of the elements in the sequence, you can leave out a few if you like, but not allowed to reorder.
- Selmeczy, Péter December 16, 2011I think this question is about to check if you know what a lexical unit parser is, how to define grammar rules and how to implement it. BNF notation is a must. To code it with a state machine is quite simple with one character look-ahead.
The other way around can be using regular expressions, and some RegEx class, but this is again about testing if you know how to define the expression of what a number is.
number := decimal_number | hexa_number | octal_number | binary_number
decimal_number: digits | digits . digits
digits := digit digits | digit
digit := 0|1|2|3|4|5|6|7|8|9
hexa_number := (0x | 0X) hexa_digits
hexa_digits := hexa_digit hexa_digits | hexadigit
hexa_digit := 0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F|a|b|c|d|e|f
and so on. Yes, well spot that decimal numbers cannot start with 0, that's what is for octals, so carry on and correct the rule :)
Most probably binary numbers are prefixed like 0B1100010101 or similar. At least if the hexa numbers are prefixed, and octals prefixed they should be - otherwise it is ambigous.
- Selmeczy, Péter December 15, 2011The permutations are just K-length "numbers" of radix-N (size-of-symbols), in the example 2-length numbers of radix 3, where the "digits" are 'A', 'B' and 'C' (0->A, 1->B, 2->C)
So if we create all K-lengths numbers of radix N we have solved the problem (just substiture digit-x with the xth symbol)
The number can be represented by an array of K integers, all 0 initially, this is number "00" that maps into "AA"
Now increment this number, the sequence generated will be (initial 00) then 01, 02, 10, 11, 12, 20, 21, 22 (all the 2-digit number using radix 3).
To increment the number represented using this array is a simple loop (adding one to the last digit, check for overflow, move the carry on, etc), same way as you have learnt in school. We know that we reached the highest representable number (in this case 22) when incrementing function will have a carry to the end.
This works properly if all the symbols are different and the number of symbols is smaller than the number that can be represented in an integer.
The real background of the story is about sequence points.
Increment operators are defined that the side-effect can happen anytime between the two sequence points where it appears. So j++ can happen anytime of the two ";"s that are "around" the assignment in question (; i = j++ + j++;) - the ;s define the sequence points - for more info check the C standard)
And it is sure that the two increments are applied after the ";" - the closing sequence point of the assignment statement.
Storing the parameters/local variables/return value on the stack frame is ONE technique, the compiler is free to choose to use registers, and many does, especially if optimization is for space.
- Selmeczy, Péter December 14, 2011"One Doubt:( On GCC compiler if i do sizeof('a') it gives 4 not 1..Why???"
printf("Size of %d\n", sizeof(char));
printf("Size of %d\n", sizeof('a'));
printf("Size of %d\n", sizeof((char)'a'));
The first sizeof is applied to a type - it gives the size of it correctly (1)
The second is applied to an integer expression, 'a' is converted to int whereever it appears in the code, so the size of int is returned (usually 4)
The third one, 'a' is converted to int and then to char, so sizeof will return 1.
If we know that the MAC address is well-formed (and should not handle error cases) then this will do
void MAC_to_ints(char *mac_addr, int arr[]) {
sscanf(mac_addr, "%x:%x:%x:%x:%x:%x", arr, arr+1, arr+2, arr+3, arr+4, arr+5);
}
And it is demonstrating that you know a bit more about the C I/O library than others.
- Selmeczy, Péter December 14, 2011You are right, I was concentrating so on the memory impact that I missed that point that tails has to be the same length. But usually list do or do not contain their lengths, but still if you have to calculate the length that is better.
- Selmeczy, Péter December 13, 2011Using a hashmap to store the addresses of the list elements is working but if the lists are huge this table will be huge.
If memory is the bottleneck and you are willing to pay for time you could do this:
Get the address of the first list item in list-A and search for it in list-B. If found -> bingo. If not get the next item in list-A and repeat. If you cannot find any of the addresses of the items in list-A -> they never merge. (And it does not matter which list you use as list-A and -B)
Actually they always merge in NULL aka the empty list :) but I am not sure all interviewers will love this answer although an empty list is a very nice list and he/she might not like if you ignore this special case on another problem ;)
The matrix contains numbers with fractions to make it interesting. All rows/cols add up to integers - sum of fractions per row/col is an integer (see many examples below)
Goal is to have only integers in the matrix, and the way to achieve it is to choose either ceiling or floor of the elements in the matrix (e.g. matrix element 1.32 -> 1 or 2, but nothing else) AND keep the sums (rows/cols) as it was in the original matrix.
And interesting issue is what could we do with elements that are already integers (my guess nothing), or with negative numbers.
Oh, bother :)
You hit it hard on my head - in spite I am not sure it is the best algorithm - that a simple BACKTRACKING will do the job. Forget about being efficient, but will solve the problem.
BACKTRACKING: Convert all elements to either ceiling or floor and check if the matrix is still OK (adding up the rows/cols). It is brute force but surely an algorithm that works although it is a "bit" exponential.
This bit counting is rather interesting
Perhaps
unsigned int bit_count(unsigned int x) {
unsigned int count = 0;
while (x) {
count += x & 1;
x >>= 1;
}
return count;
}
is a better one (a bit less operation performed).
But the real issue is that your algorithm is calling the bit counting N times, so it cannot be O(log N) - it is O(N)
To have a O(log N) algorithm you should think about a tree and not traversing but descending into it from the root at some "good" direction. This sounds crazy to descend from the root but trees in computers grow upside down :)
To start with consider a 2x2 matrix (A11, A12, A21, A22). Substracting X from A11 and A22 and adding X to A21 and A12 will keep the invariant property of the matrix given (sums of cols/rows give integer) whereever this 2x2 matrix is located in the original one.
If you apply this rule (where X is the fraction part of A11) recrusively you will end up with a matrix that has only integers.
Now the next step is to figure out how to do this to do this to end up with the ceil/floor values the original elements of the matrix.
I think an important part of the next step will be to consider that you can freely change the order of rows/column of these matrices and change the full row/col back after the transformations (sub/add/add/sub) applied.
Well, you are right from a certain point of view.
But if you want to solve the problem then it is better to think of the numbers as you do in classic arithmetic and in the implementation use an epsilon to compare two doubles (abs(x-y)<Eps) or think of the numbers as "Decimals" - capable of fixed point arithmetic without loosing precision.
At least this is what I'd do...
I think that the hash-table based solutions (suppose that they are not very trick) could work only if W1, W2, .. Wn are all different. If they are not something else should be considered or the hash items should contain a list of positions and should keep as many of these positions as many time Wk is repeated.
- Selmeczy, Péter December 19, 2011