JonathanBarOr
BAN USERIt's not wrong. You determine that all lights are turned off when the beginning position has been turned off. Explanation: each time you go left and turn off the lights you see, while the start position's light is on. When returning to the starting position, if it has been turned off - it means that you went a whole circle to the left! Then you can be sure that all lights are indeed turned off.
- JonathanBarOr November 05, 2015Shortest code:
def f(n): return 1 if n<=2 else f(n-2)+f(n-1)
Via reflection.
- JonathanBarOr November 04, 2015Do the following: turn on the light at starting position. Now, let's keep in mind a variable k, initialized as 1 and increased in each iteration. This is the algorithm:
1. Go left k steps, turn off the light in each cart.
2. Return k steps right (not touching any lights).
3. Now you're at the starting position. If the light is turned off - quit the loop.
4. Increase k and re-iterate (1).
If the light is off at the starting position - it means that we made a full circle. Now, turn on the light at starting position (again), go left and count until you reach a turned-on cart. This is the number of carts.
void find_set_bits(unsigned int num)
{
int i;
for (i = 0; i < 32; i++) // Assuming unsigned int is 32 bit!
{
if (num & (1<<i) != 0)
{
printf("Bit %d is set (0 = LSB).\n", i);
}
}
}
If there are no restrictions, this could be done in O(n).
Assuming the following structure:
struct _node
{
struct _node* next;
int data;
};
And assuming the interface of the function... This is my solution:
void merge(struct _node* h1, struct _node* h2)
{
while (h1->next != NULL)
h1 = h1->next;
h1->next = h2;
}
A nice optimization would be to have another structure for the list head, saving the last element as such:
struct _head
{
struct _node* first;
struct _node* last;
}
Then, an O(1) solution is possible:
void merge(struct _head* h1, struct _head* h2)
{
h1->last->next = h2;
h1->last = h2->last
}
Count the number of differences when taking the mirror image. C solution:
int toPali(char* s)
{
int result = 0;
char* last = s;
if (NULL == s)
return -1;
while (*last)
last++;
last--;
while (last > s)
{
result += (*last == *s ? 1 : 0);
s++;
last--;
}
return result;
}
Could you explain the desired behavior? Does the bit map act as a memory pool for bits?
- JonathanBarOr November 01, 2015One bubble sort iteration:
void swap(int* x, int* y)
{
int t = *x;
*x = *y;
*y = t;
}
void rearrange(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
if (i % 2 == 0)
{
if (arr[i] > arr[i+1])
swap(arr + i, arr + i + 1);
}
else
{
if (arr[i+1] > arr[i])
swap(arr + i, arr + i + 1);
}
}
}
int getm(Node* n, int m)
{
Node* ahead = n;
Node* res = n;
if ((NULL == n) || (m < 0))
return NULL;
for (int i = 0; i < m; i++)
{
ahead = ahead->next;
if (NULL == ahead)
return NULL;
}
while (NULL != ahead)
{
res = res->next;
ahead = ahead->next;
}
return res;
}
void mover(int* arr, int n)
{
int end = n - 1;
// Checking inputs
if ((NULL == arr) || (n <= 0))
return;
// Iterate the array
while (i <= end)
{
// Check for zeros
if (arr[i] == 0)
{
// Swap the elements at positions "i" and "end"
arr[i] = arr[end];
arr[end] = 0;
// The next position for a zero decreases
end--;
}
else
{
// Not a zero, move on
i++;
}
}
}
Two approaches:
1. Sorting the array (costs O(n log n)), iterating elements and for each element look for its negative value with binary search (again, O(n log n)). Overall time is n log n.
2. Iterate elements. For each element, add to a hash table, and search for its negative value in the hash table.
Keep L in a trie, and iterate searches in a parallel way, as such:
- JonathanBarOr November 05, 20151. For each search position in our search list:
1.1. If the next character is still in the trie - advance the search position to the corresponding position in the trie. If it hit a complete word - call the external API.
1.2. Otherwise, remove the search from the list.
2. Add a new position to the list. That position is the node following from the root, given the current character.