Selmeczy, Péter
BAN USERThis does not work if array is only 0s (or 1s), it will crash with index out of range.
Furthermore swaping 0 and 1 could be simplified (just write 0 to "begin" and 1 to "end"
If the range is 1..100 then count in phase one, and the rewrite (fill) the array with the numbers - O(N) time, O(1) space
Naturally this does not work if the numbers are just keys, in that case count sorting - which is pretty much the same - works.
This solution works only if the repeat-count is one-digit, it is easy to change it to handle cases when repeat-count is 1+ digits
#include <stdio.h>
void convert(char *s);
int main() {
char string[] = "aaabbcccccccccddffffggaaaa";
convert(string);
printf("New string = %s\n", string);
return 0;
}
void convert(char *s) {
char *p = s; // points to the character to process in the original string
char *q = s; // points to where the result (char + repeat-counter) comes
int c;
int counter;
while (*p) {
c = *p;
counter = 0;
while (*p && *p == c) {
p++;
counter++;
}
*q++ = c;
*q++ = counter+'0'; // simple solution if < 10 chars repeated
}
*q = 0;
}
A string is immutable in Java or C#, but not in C ;)
So if you have a mutable string you can do it easily - given the condition that it is guaranteed that all characters happen more than once in the sequence as you can use the 2nd, 3rd, etc occurances to store the count (and beware of counts where it is >9!)
private static void SortZerosAndOnes(int[] array, int size) {
int low = 0; int high = size-1;
while(low < high) {
if (array[low] == 0) {
low++;
continue;
}
if (array[high] == 1) {
high--;
continue;
}
// now array[low] == 1 and array[high] == 0, change them and move both pointers
array[low] = 0; array[high] = 1; low++; high--;
}
}
Note: you can eliminate the size parameter and use array.length-1 as the initial value for high
- Selmeczy, Péter February 13, 2012Assertion is used to check the state of a program, test for a condition (mostly pre- and post- and in- conditions). Assert check it and if it does not hold it throws an exception.
The most common way to use it is to add asserts to the beginning and end of methods to check that the state of the object is OK at the beginning and it is OK when ending. But you can use it in loops as well.
These tests are guaranteeing that your algorithm works as it should (see some books on algos that teaches about pre-, post- and maintenance conditions :)
Search for what? Name? Full name or partial match? What is considered a partial match (e.g. firstname/lastname split)?
Or search for the phone number (the name having a phone number)? Or just part of the phone number - number matching?
This is the classic solution from the times when a character was 8 bits. These days you should consider Unicode, too.
- Selmeczy, Péter February 13, 2012I honestly do not understand how this is not terminating when the size of the interval gets smaller and smaller at each and every step. Can you give an example?
- Selmeczy, Péter February 02, 2012Almost, first convert the two pointers to char *, otherwise you will get 1 (this is how pointer arithmetic works)
X array[2];
char *first = (char*)array; // which is &array[0]
char *second = (char *)(array+1) // which is &array[1]
return second - first;
This works because sizeof (char) is defined as 1, and it is one of the very few implementation dependent type sizes in C.
The binary-search idea is leading to this:
Split the interval of [a, b] into two half and use the first-half if rand() gives 0 and use the 2nd half if it gives 1. Continue this until the size of the interval is 1, and this will be the random number.
Even the splitting (when the size is odd) must use rand() on which mid to use (lower or upper-mid), otherwise (e.g. using always the lower-mid) leads to wrong distribution.
An even better solution is to use real numbers when splitting - until the interval contains only one integer (size of interval becomes less than 2)
Perhaps it is worth to tell how this macros should have been written
#define SQUARE(x) ((x)*(x))
Errrr... There is time complexity and space/memory complexity. So you are right that there are quite a few O(N) algorithms (time!) but we should consider memory usage as well.
Without knowing the overall number/distinct number/distribution/etc of the words it is hard to tell more.
The funny side of it is that most probably the answer is always "a", "the", "in" for books written in English (or something like that) :-) and if I am not mistaken very similar list-of-3-most-common-words can be compiled for all languages.
1. Intersection should read as union (with eliminating the 0s if it is stored as a linked list)
2. List or array depends on what is the expected number of non-zero tags, for large polynomials it is usual that there are only a few, so linked list is usually a better option.
4 should be sizeof(int) - or sizeof(whatever-type-you-convert).
But if the size of integer is known it is much better (and faster to execute) to write a macro to swap the bytes.
// if sizeof(int) == 4
#define SWITCH_ENDIANNESS(i) ( \
((i)<<24) | \
((i<<8)&0x0000FF00)) | \
((i>>8)&0x00FF0000)) | \
((i>>24)&0x000000FF)) )
Alternatively swap the last-byte with first, and the middle-bytes.
// suppose that sizeof(int) == 4
void switch_endianness(int *i) {
char *c = (char *)i;
int temp;
// first swap 0th and 3rd byte
temp = *c; *c = *(c+3); *(c+3) = temp;
// and then swap 1st and 2nd byte
temp = *(c+1); *(c+1) = *(c+2); *(c+2) = temp;
}
Well, even with possible 5 different subjects the subjects should go into another table. And then join the student table with the subjects table for the query.
select distinct studentName from students, subjects where students.id = subjects.id and (subjects.title = 'DS' or subject.title = 'Networking')
If y is 2^n then x ^ y is x multiplied with itself and then the result is multiplied with itself, etc for n-1 times. This is not recursive but can be done with n-1 multiplication.
Another issue is that with ints this is a maths questions because of the overflow happening very fast :)
The question is about the time of calculating the index of the item, both (should be) two "identical" loops, printing all elements of the matrix - row-wise and column-wise.
- Selmeczy, Péter January 19, 2012Normally processes have their own address spaces and this address space is not visible from other processes (but read: interprocess communication - how to create a visible address space that is shared between two or more processes). This is the usual case but there are operating systems (some embedded systems for example) where it is not the case, protected memory/separate address space is "expensive" (read: task switch penalty)
Threads do share the same address space, so in case of threads the answer is yes.
Carol, you are right from some point of view, but should we consider a negative value anywhere in the array? I don't think so... But it is good to tell the interviewer that your assumption is that all digits are decimal digits - so 0<= number[i] <= 9
- Selmeczy, Péter January 07, 2012
Nothing is wrong with it but it goes through the array twice. In other words the constant factor of O(N) is twice as big as the one-pass solutions. And if there are two O(X) algorithms the one that has smaller constant tag is considered a better one.
- Selmeczy, Péter February 14, 2012