HackerRank’s 30 Days of Code, Day 8, Part I

Like all previous tasks, this was marked as easy. Well, it may be easy if you’re solving it in Java or any other language which has Map methods, but with C, the task becomes more complicated: you have to implement a hashtable, and this is a challenge in itself. What’s more, it won’t be enough to pass all the test cases, but more on that later :)

Here’s the code I ended up with (for the time being):

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */    
// declaring variables
long long int n;
char str[1000];

// creating the structure
struct phoneBook {
char name[100];
long long int number;
} map[99999];

// getting number of entries and saving the data to the structure
scanf("%lld", &n);
for (long long int i = 0; i < n; i++) {
scanf("%s %lld\n", map[i].name, &map[i].number);
}

// reading the rest of entries, searching the phonebook, printing out search results
while (scanf("%s", str) != EOF) {
long long int counter = 0;
for (long long int j = 0; j < n; j++) {
if (!strcmp(str, map[j].name)) {
printf("%s=%lld\n", map[j].name, map[j].number);
counter = 1;
}
}
if (counter != 1) {
printf("Not found\n");
}
}
return 0;
}

An almost line-by-line explanation:

  • First, I created a struct (phoneBook) with two members, name and number;
  • Next, I used scanf() to get the number of lines I would need to read and extract data from and another scanf() inside a for loop to store the data in my phoneBook;
  • At this point in my code, I’ve read n lines of input and created a phoneBook. Next comes the tricky part: reading an unknown number of queries and returning either a stored entry or a Not found. Since the number of queries is unknown, a while loop executing until end of file is reached seems the best option.

At first, my while loop looked like this:

while (scanf(“%s”, str) != EOF) {
 for (long long int j = 0; j < n; j++) {
 if (!strcmp(str, map[j].name)) {
 printf(“%s=%lld\n”, map[j].name, map[j].number);
 } 
 }
 else {
 printf(“Not found\n”); 
 } 
 }

It didn’t work quite right — the output, while containing the right entries, largely consisted of Not founds. I suspected the issue might be not with the while loop, but with the for loop, so I employed testing against custom input and entered something like this:

4
alice 6758586
dina 754646
jane 3647587
kate 34967546
dina
alice
kate
jane

A test run confirmed that the for loop worked beautifully — all these entries were correctly stored and printed out. Things began going astray only when I added names which were not in the list. By the way, testing against custom input comes in especially handy in this task!

I turned to the Discussions section and noticed that a couple of (reportedly successful) C solutions contained some sort of a counter inside the loop. I tried this, too, and it worked:

while (scanf("%s", str) != EOF) {
int counter = 0;
for (long long int j = 0; j < n; j++) {
if (!strcmp(str, map[j].name)) {
printf("%s=%lld\n", map[j].name, map[j].number);
counter = 1;
}
}
if (counter != 1) {
printf("Not found\n");
}
}

This is how it works: at the beginning of the loop, the counter is set to 0; if the queried name was found in the phone book, the counter is set to 1, and the result of the query is printed out; if, however, the counter is left unchanged, Not found is printed out, and the loop executes again (until it reaches end of file).

Note that in this snippet of my code, something is slightly different from the final version: I use int, not long long int. This is because when I was running the code against the sample test case and my custom input, it more or less worked, but when I submitted my code after a successful run against the sample test case, it segfaulted on several subsequent test cases. When I downloaded the second test case, it became obvious that the number of entries and queries was simply too big, so I replaced ints with long long ints.

This helped to get rid of the segmentation fault, but now the same test cases showed timeout error. Indeed, if the number of entries/queries is too big, and the entries are in random order, search may take a very long time, so implementing a sorting function and maybe a more efficient searching function should help.

And all this for a supposedly easy task. Isn’t programming in C just fun?:)

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.