ftonello
BAN USERI got confused, your I/O is fine if called with the right block size, altough you are not specifing the optiomal size. Also you are always dividing it by half of the file size, which is not optimal if the file size is smaller then the block size or if it is not divisible by the block size.
Some observations:
* The OOP API can be worked out more. You should use STL like implementation, itarators and operators.
* Using a vector<> for that is not optimal since you don't need it. Use array instead. Altough some compilers generate std::vector assembly as arrays when possible, still I wouldn't recommend for best portabilty and performance.
* For C++ implementation fopen family fucntions (C lib std) is not recommented. Use fstreams instead.
* You fstat(), or any OS system call, instead of ftell() for file size.
* The implementation is not robust.
* &v[0] == v
But for an interview for a Jr position should be fine.
Good luck.
O(n) space and time
But the big O notation here doens't really matter, the I/O and memory allocation is what matters. In this case, it uses optimal block size to reverse any type of file.
The code is a bit complicated, but it is safe and robust. But to be honest, I doubt that the engineer would require that much...
Also, it only runs on Unix, of course. Why would you even consider having something else? :)
#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>
inline void swap(unsigned char *a, unsigned char *b)
{
unsigned char tmp = *b;
*b = *a;
*a = tmp;
}
void reverse_file(int fd, size_t file_size, size_t buffer_size)
{
if (file_size <= buffer_size) {
buffer_size = file_size;
unsigned char buffer[buffer_size];
size_t i, io_size = 0;
lseek(fd, 0, SEEK_SET);
do {
io_size += read(fd, buffer + io_size, buffer_size - io_size);
} while (io_size < buffer_size);
for (i = 0; i < buffer_size / 2; ++i)
swap(&buffer[i], &buffer[buffer_size - 1 - i]);
lseek(fd, 0, SEEK_SET);
do {
io_size += write(fd, buffer + io_size, buffer_size - io_size);
} while (io_size < buffer_size);
} else {
size_t total_io_size = 0;
/* make sure buffer_size is at maximum half of the file */
buffer_size = buffer_size > (file_size / 2) ? file_size / 2 : buffer_size;
unsigned char buffer1[buffer_size], buffer2[buffer_size];
do {
size_t i, io_size = 0;
lseek(fd, total_io_size, SEEK_SET);
io_size = 0;
do {
io_size += read(fd, buffer1 + io_size, buffer_size - io_size);
} while (io_size < buffer_size);
lseek(fd, file_size - buffer_size - total_io_size, SEEK_SET);
io_size = 0;
do {
io_size += read(fd, buffer2 + io_size, buffer_size - io_size);
} while (io_size < buffer_size);
for (i = 0; i < buffer_size / 2; ++i) {
swap(&buffer1[i], &buffer1[buffer_size - 1 - i]);
swap(&buffer2[i], &buffer2[buffer_size - 1 - i]);
}
lseek(fd, total_io_size, SEEK_SET);
io_size = 0;
do {
io_size += write(fd, buffer2 + io_size, buffer_size - io_size);
} while (io_size < buffer_size);
lseek(fd, file_size - buffer_size - total_io_size, SEEK_SET);
io_size = 0;
do {
io_size += write(fd, buffer1 + io_size, buffer_size - io_size);
} while (io_size < buffer_size);
total_io_size += buffer_size;
} while (total_io_size < file_size / 2);
}
}
int main(int argc, char *argv[])
{
char *file = argv[1];
struct stat st;
size_t file_size, buffer_size;
int fd;
fd = open(file, O_RDWR);
fstat(fd, &st);
reverse_file(fd, st.st_size, st.st_blksize);
close(fd);
return 0;
}
You can change the BALL_MAX define for any divisible by 3. Try 81*81*81 for example.
time: O(log3(n)) best case, worst case is O(n)
space: O(n)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define BALL_MAX (81)
#define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b))
#define BALL_OFFSET(_ball, _len, _off) (_ball + ((_len / 3) * (_off)))
static long iterations;
inline size_t min3(size_t a, size_t b, size_t c)
{
return MIN(MIN(a, b), c);
}
size_t weight(size_t *ball, size_t len)
{
size_t i;
size_t ret = 0;
for (i = 0; i < len; ++i)
ret += *(ball + i);
return ret;
}
bool find_lightest_ball(size_t *ball, size_t len, size_t *min_val /* OUT */)
{
iterations++;
if (len == 3) {
*min_val = min3(*ball, *(ball + 1), *(ball + 2));
return true;
} else if (len == 9) {
size_t w1, w2, w3;
w1 = weight(BALL_OFFSET(ball, len, 0), len / 3);
w2 = weight(BALL_OFFSET(ball, len, 1), len / 3);
w3 = weight(BALL_OFFSET(ball, len, 2), len / 3);
if (w1 == w2 && w2 == w3)
return false;
else if (w1 < w2)
return find_lightest_ball(BALL_OFFSET(ball, len, 0), len / 3, min_val);
else if (w2 < w1)
return find_lightest_ball(BALL_OFFSET(ball, len, 1), len / 3, min_val);
else
return find_lightest_ball(BALL_OFFSET(ball, len, 2), len / 3, min_val);
} else {
return find_lightest_ball(BALL_OFFSET(ball, len, 0), len / 3, min_val) ||
find_lightest_ball(BALL_OFFSET(ball, len, 1), len / 3, min_val) ||
find_lightest_ball(BALL_OFFSET(ball, len, 2), len / 3, min_val);
}
}
int main(int argc, char *argv[])
{
size_t i, ball[BALL_MAX];
size_t w, w2, l_i;
size_t min_ball_val;
srand(time(NULL));
w = rand() % 100 + 1;
for (i = 0; i < BALL_MAX; i++)
ball[i] = w;
l_i = rand() % BALL_MAX;
while ((w2 = rand() % 100) >= w);
ball[l_i] = w2;
for (i = 0; i < BALL_MAX; i++)
printf("ball #%u: %u\n", i+1, ball[i]);
find_lightest_ball(ball, sizeof(ball) / sizeof(*ball), &min_ball_val);
printf("lightes ball: %u\n", min_ball_val);
printf("number of iterations: %ld\n", iterations);
return 0;
}
O(n) time and O(1) space.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int val;
struct node *next;
} node_t;
typedef struct linked_list {
node_t *head;
size_t size;
} ll_t;
ll_t * linked_list_new()
{
ll_t *ll = (ll_t *)(malloc(sizeof(ll_t)));
ll->head = NULL;
ll->size = 0;
return ll;
}
node_t * linked_list_insert(ll_t *ll, int val)
{
node_t *node;
if (!ll)
return NULL;
if (ll->head) {
node_t *end = ll->head;
while (end->next)
end = end->next;
node = (node_t *)(malloc(sizeof(node_t)));
node->val = val;
node->next = NULL;
end->next = node;
} else {
node = (node_t *)(malloc(sizeof(node_t)));
node->val = val;
node->next = NULL;
ll->head = node;
}
ll->size++;
return node;
}
#define _LINKED_LIST_MERGE_NODE(_ll, _prev, _n) \
do { \
if (_prev) \
_prev->next = _n; \
else \
_ll->head = _n; \
\
_ll->size++; \
_prev = _n; \
_n = _n->next; \
} while(0);
/* merge into first list */
void linked_list_merge(ll_t *ll1, ll_t *ll2)
{
node_t *prev = NULL;
node_t *n1, *n2;
n1 = ll1->head;
n2 = ll2->head;
while (n1 && n2) {
if (n1->val >= n2->val) {
_LINKED_LIST_MERGE_NODE(ll1, prev, n2);
} else {
if (prev)
prev->next = n1;
prev = n1;
n1 = n1->next;
}
};
while (n2) {
_LINKED_LIST_MERGE_NODE(ll1, prev, n2);
}
}
int main(int argc, char *argv[])
{
ll_t *l1, *l2;
l1 = linked_list_new();
l2 = linked_list_new();
linked_list_insert(l1, 0);
linked_list_insert(l1, 1);
linked_list_insert(l1, 3);
linked_list_insert(l1, 5);
linked_list_insert(l1, 7);
linked_list_insert(l1, 7);
linked_list_insert(l1, 9);
linked_list_insert(l1, 11);
linked_list_insert(l1, 13);
linked_list_insert(l1, 15);
linked_list_insert(l1, 17);
linked_list_insert(l2, 0);
linked_list_insert(l2, 2);
linked_list_insert(l2, 4);
linked_list_insert(l2, 6);
linked_list_insert(l2, 7);
linked_list_insert(l2, 8);
linked_list_insert(l2, 10);
linked_list_insert(l2, 12);
linked_list_insert(l2, 14);
linked_list_insert(l2, 16);
linked_list_merge(l1, l2);
node_t *node = l1->head;
printf("size: %u\n", l1->size);
while (node) {
printf("%d ", node->val);
node = node->next;
}
printf("\n");
return 0;
}
O(n) implementation with no recursion or string length check.
#include <stdio.h>
#include <stdbool.h>
bool is_str_equal(char *str1, char *str2)
{
while (*str1 && *str2 && *str1 == *str2)
str1++,str2++;
return !(*str1 || *str2);
}
bool is_one_count(char *str1, char *str2)
{
while (*str1 && *str2 && *str1 == *str2)
str1++,str2++;
/* same string */
if (!(*str1 || *str2))
return false;
return is_str_equal(str1 + 1, str2) ||
is_str_equal(str1, str2 + 1) ||
is_str_equal(str1 + 1, str2 + 1) ||
is_str_equal(str1 - 1, str2) ||
is_str_equal(str1, str2 - 1);
}
int main(int argc, char *argv[])
{
printf("%s\n", (is_one_count("abbc","abcc")) ? "True" : "False");
return 0;
}
The fastest check if it is palindrome from stdin in the west:
- ftonello January 31, 2016