Querying the Document

Sort by

recency

|

157 Discussions

|

  • + 0 comments

    This test measures nothing other than the candidate's tolerance for torture.

    There would only be two realistic approaches to this problem in real life.

    1) Rewrite the entire thing, and if not allowed to do that: 2) Quit the job.

  • + 0 comments
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include<assert.h>
    #define MAX_CHARACTERS 1005
    #define MAX_PARAGRAPHS 5
    
    char* kth_word_in_mth_sentence_of_nth_paragraph(char**** document, int k, int m, int n) {
        return document[n-1][m-1][k-1];
    }
    
    char** kth_sentence_in_mth_paragraph(char**** document, int k, int m) { 
        return document[m-1][k-1];
    }
    
    char*** kth_paragraph(char**** document, int k) {
        return document[k-1];
    }
    
    void resetTempWord(char * tmpWord, int * tmpWordIndex) {
        tmpWord[0] = '\0';
        *tmpWordIndex = 0;
    }
    
    char**** get_document(char* text) {
        char **** document;
    
        int wordIndex = -1;
        int sentenceIndex = -1;
        int paragraphIndex = -1;
        
        int wordOpen = 0;
        int sentenceOpen = 0;
        int paragraphOpen = 0;
        
         //when to make a new slot
         // - upon observation of new requirement for a slot (letter)
         //when to reset the tempword
         // - when the last word was wrapped up
         //when to wrap up the current word, sentend and paragraph
         // - when their delimiters are observed
                
        char tempWord[1000000];
        int tempWordIndex = 0;
        tempWord[0] = '\0';
        int length = strlen(text);
        for (int i = 0; i < length; i++) {
            char chr = text[i];
            if (chr == '\0') { 
                //i think we just need to wrap up the paragraph
                paragraphOpen = 0;
                break;
            } else if (chr == ' ') {
                tempWord[tempWordIndex] = '\0';
                char * newWord = malloc(tempWordIndex);
                strcpy(newWord, tempWord);
                document[paragraphIndex][sentenceIndex][wordIndex] = newWord;
                resetTempWord(tempWord, &tempWordIndex);
                wordOpen = 0;
            } else if (chr == '.') {
                tempWord[tempWordIndex] = '\0';
                char * newWord = malloc(tempWordIndex);
                strcpy(newWord, tempWord);
                document[paragraphIndex][sentenceIndex][wordIndex] = newWord;
                resetTempWord(tempWord, &tempWordIndex);
                wordOpen = 0;
                
                sentenceOpen = 0;
            } else if (chr == '\n') {
                paragraphOpen = 0;
            } else {
                if (!paragraphOpen) {
                    paragraphIndex++;
                    sentenceIndex = wordIndex = -1;
                    if (!document) {
                        document = calloc(1, sizeof(char ***));
                    } else {
                        document = realloc(document, (paragraphIndex + 1) * sizeof(char ***));
                    }
                    paragraphOpen = 1;
                }
                //if we need a sentence mem, make it now
                if (!sentenceOpen) {
                    sentenceIndex++;
                    wordIndex = -1;
                    if (!document[paragraphIndex]) {
                        document[paragraphIndex] = calloc(1, sizeof(char **));
                    } else {
                        document[paragraphIndex] = realloc(document[paragraphIndex], (sentenceIndex + 1) * sizeof(char **));
                    }
                    sentenceOpen = 1;
                }
                //if we need a word mem, make it now
                if (!wordOpen) {
                    wordIndex++;
                    if (!document[paragraphIndex][sentenceIndex]) {
                        document[paragraphIndex][sentenceIndex] = calloc(1, sizeof(char *));
                    } else {
                        document[paragraphIndex][sentenceIndex] = realloc(document[paragraphIndex][sentenceIndex], (wordIndex + 1) * sizeof(char *));
                    }
                    wordOpen = 1;
                }
                
                //add letter to word
                tempWord[tempWordIndex++] = chr;
            }
        }
        
        return document;
    }
    
    
    char* get_input_text() {	
        int paragraph_count;
        scanf("%d", &paragraph_count);
    
        char p[MAX_PARAGRAPHS][MAX_CHARACTERS], doc[MAX_CHARACTERS];
        memset(doc, 0, sizeof(doc));
        getchar();
        for (int i = 0; i < paragraph_count; i++) {
            scanf("%[^\n]%*c", p[i]);
            strcat(doc, p[i]);
            if (i != paragraph_count - 1)
                strcat(doc, "\n");
        }
    
        char* returnDoc = (char*)malloc((strlen (doc)+1) * (sizeof(char)));
        strcpy(returnDoc, doc);
        return returnDoc;
    }
    
    void print_word(char* word) {
        printf("%s", word);
    }
    
    void print_sentence(char** sentence) {
        int word_count;
        scanf("%d", &word_count);
        for(int i = 0; i < word_count; i++){
            printf("%s", sentence[i]);
            if( i != word_count - 1)
                printf(" ");
        }
    } 
    
    void print_paragraph(char*** paragraph) {
        int sentence_count;
        scanf("%d", &sentence_count);
        for (int i = 0; i < sentence_count; i++) {
            print_sentence(*(paragraph + i));
            printf(".");
        }
    }
    
    int main() 
    {
        char* text = get_input_text();
        char**** document = get_document(text);
    
        int q;
        scanf("%d", &q);
    
        while (q--) {
            int type;
            scanf("%d", &type);
    
            if (type == 3){
                int k, m, n;
                scanf("%d %d %d", &k, &m, &n);
                char* word = kth_word_in_mth_sentence_of_nth_paragraph(document, k, m, n);
                print_word(word);
            }
    
            else if (type == 2){
                int k, m;
                scanf("%d %d", &k, &m);
                char** sentence = kth_sentence_in_mth_paragraph(document, k, m);
                print_sentence(sentence);
            }
    
            else{
                int k;
                scanf("%d", &k);
                char*** paragraph = kth_paragraph(document, k);
                print_paragraph(paragraph);
            }
            printf("\n");
        }     
    }
    
  • + 0 comments

    We can use strtok_r and save its internal states using save pointers since we use nested looping.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include<assert.h>
    #define MAX_CHARACTERS 1005
    #define MAX_PARAGRAPHS 5
    
    int char_count(char *s, char c) {
        int count = 0;
        for (int i = 0; i < strlen(s); i++)
            count += (int) (s[i] == c);
        return count;
    }
    
    char* kth_word_in_mth_sentence_of_nth_paragraph(char**** document, int k, int m, int n) {
        return document[n - 1][m - 1][k - 1];
    }
    
    char** kth_sentence_in_mth_paragraph(char**** document, int k, int m) {
        return document[m - 1][k - 1];
    }
    
    char*** kth_paragraph(char**** document, int k) {
        return document[k - 1];
    }
    
    char**** get_document(char* text) {
        char ****doc;
        int pcnt = char_count(text, '\n') + 1, cp = 0;
        doc = (char ****)malloc((sizeof(char ***)) * pcnt);
        char *ptoken, *psaveptr;
        ptoken = strtok_r(text, "\n", &psaveptr);
        while (ptoken != NULL) {
            char *p = (char *)malloc((sizeof(char)) * (strlen(ptoken) + 1));
            strcpy(p, ptoken);
            int scnt = char_count(p, '.') + 1, cs = 0;
            doc[cp] = (char ***)malloc((sizeof(char **)) * scnt);
            char *stoken, *ssaveptr;
            stoken = strtok_r(p, ".", &ssaveptr);
            while (stoken != NULL) {
                char *s = (char *)malloc((sizeof(char)) * (strlen(stoken) + 1));
                strcpy(s, stoken);
                int wcnt = char_count(s, ' ') + 1, cw = 0;
                doc[cp][cs] = (char **)malloc((sizeof(char *)) * wcnt);
                char *wtoken, *wsaveptr;
                wtoken = strtok_r(s, " ", &wsaveptr);
                while (wtoken != NULL) {
                    char *w = malloc((sizeof(char)) * (strlen(wtoken) + 1));
                    strcpy(w, wtoken);
                    int ccnt = strlen(w);
                    doc[cp][cs][cw] = (char *)malloc((sizeof(char)) * (ccnt + 1));
                    strcpy(doc[cp][cs][cw], w);
                    wtoken = strtok_r(NULL, " ", &wsaveptr);
                    cw++;
                }
                stoken = strtok_r(NULL, ".", &ssaveptr);
                cs++;
            }
            ptoken = strtok_r(NULL, "\n", &psaveptr);
            cp++;
        }
        return doc;
    }
    
    
    
    char* get_input_text() {	
        int paragraph_count;
        scanf("%d", &paragraph_count);
    
        char p[MAX_PARAGRAPHS][MAX_CHARACTERS], doc[MAX_CHARACTERS];
        memset(doc, 0, sizeof(doc));
        getchar();
        for (int i = 0; i < paragraph_count; i++) {
            scanf("%[^\n]%*c", p[i]);
            strcat(doc, p[i]);
            if (i != paragraph_count - 1)
                strcat(doc, "\n");
        }
    
        char* returnDoc = (char*)malloc((strlen (doc)+1) * (sizeof(char)));
        strcpy(returnDoc, doc);
        return returnDoc;
    }
    
    void print_word(char* word) {
        printf("%s", word);
    }
    
    void print_sentence(char** sentence) {
        int word_count;
        scanf("%d", &word_count);
        for(int i = 0; i < word_count; i++){
            printf("%s", sentence[i]);
            if( i != word_count - 1)
                printf(" ");
        }
    } 
    
    void print_paragraph(char*** paragraph) {
        int sentence_count;
        scanf("%d", &sentence_count);
        for (int i = 0; i < sentence_count; i++) {
            print_sentence(*(paragraph + i));
            printf(".");
        }
    }
    
    int main() 
    {
        char* text = get_input_text();
        char**** document = get_document(text);
    
        int q;
        scanf("%d", &q);
    
        while (q--) {
            int type;
            scanf("%d", &type);
    
            if (type == 3){
                int k, m, n;
                scanf("%d %d %d", &k, &m, &n);
                char* word = kth_word_in_mth_sentence_of_nth_paragraph(document, k, m, n);
                print_word(word);
            }
    
            else if (type == 2){
                int k, m;
                scanf("%d %d", &k, &m);
                char** sentence = kth_sentence_in_mth_paragraph(document, k, m);
                print_sentence(sentence);
            }
    
            else{
                int k;
                scanf("%d", &k);
                char*** paragraph = kth_paragraph(document, k);
                print_paragraph(paragraph);
            }
            printf("\n");
        }     
    }
    
  • + 0 comments
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include<assert.h>
    #define MAX_CHARACTERS 1005
    #define MAX_PARAGRAPHS 5
    
    char* kth_word_in_mth_sentence_of_nth_paragraph(char**** document, int k, int m, int n) {
        return document[n - 1][m - 1][k - 1]; 
    }
    
    char** kth_sentence_in_mth_paragraph(char**** document, int k, int m) { 
        return document[m - 1][k - 1]; 
    }
    
    char*** kth_paragraph(char**** document, int k) {
        return document[k - 1]; 
    }
    
    char* get_word(const char* word) 
    {
        char* ans = NULL; 
        ans = (char*) strdup(word); 
        return ans; 
    }
    
    char** get_sentence(const char* sentence) 
    {
        char** ans = NULL; 
        int count_word = 0;
        char *temp_sentence = (char*) strdup(sentence); 
        char *start = temp_sentence; 
        char *end = strchr(start, ' '); 
        while (end != NULL) {
            *end = '\0'; 
            char* temp_word = (char*) strdup(start); 
            ans = (char**) realloc(ans, sizeof(char**) * (count_word + 1)); 
            ans[count_word] = get_word(temp_word);       
            start = end + 1; 
            end = strchr(start, ' '); 
            count_word++; 
        }
        if (*start != '\0') {
            ans = (char**) realloc(ans, sizeof(char*) * (count_word + 1));
            char* temp_word = (char*) strdup(start);  
            ans[count_word] = get_word(temp_word);       
            count_word++;    
        }
        return ans; 
    }
    
    char*** get_paragraph(const char* paragraph) 
    {
        char*** ans = NULL; 
        int count_sentence = 0; 
        char* temp_paragraph = (char*) strdup(paragraph); 
        char *start = temp_paragraph; 
        char *end = strchr(start, '.'); 
        while (end != NULL) {
            *end = '\0'; 
            char *temp_sentence = (char*) strdup(start); 
            ans = (char***) realloc(ans, sizeof(char**) * (count_sentence + 1)); 
            ans[count_sentence] = get_sentence(temp_sentence); 
            start = end + 1; 
            end = strchr(start, '.'); 
            count_sentence++; 
        }
        if (*start != '\0') {
            ans = (char***) realloc(ans, sizeof(char**) * (count_sentence + 1)); 
            char *temp_sentence = (char*) strdup(start); 
            ans[count_sentence] = get_sentence(temp_paragraph); 
            count_sentence++; 
        }
        return ans; 
    }
    
    char**** get_document(char* document) {
        char ****ans = NULL; 
        int count_paragraph = 0; 
        char *temp_document = (char*) strdup(document); 
        char *start = temp_document; 
        char *end = strchr(start, '\n'); 
        while (end != NULL) {
            *end = '\0'; 
            char *temp_paragraph = (char*) strdup(start); 
            ans = (char****) realloc(ans, sizeof(char***) * (count_paragraph + 1));
            ans[count_paragraph] = get_paragraph(temp_paragraph); 
            start = end + 1; 
            end = strchr(start, '\n'); 
            count_paragraph++; 
        }
        if (*start != '\0') {
            ans = (char****) realloc(ans, sizeof(char***) * (count_paragraph + 1));
            char *temp_paragraph = (char*) strdup(start); 
            ans[count_paragraph] = get_paragraph(temp_paragraph); 
            count_paragraph++; 
        }
        return ans; 
    }   
    
    
    char* get_input_text() {	
        int paragraph_count;
        scanf("%d", &paragraph_count);
    
        char p[MAX_PARAGRAPHS][MAX_CHARACTERS], doc[MAX_CHARACTERS];
        memset(doc, 0, sizeof(doc));
        getchar();
        for (int i = 0; i < paragraph_count; i++) {
            scanf("%[^\n]%*c", p[i]);
            strcat(doc, p[i]);
            if (i != paragraph_count - 1)
                strcat(doc, "\n");
        }
    
        char* returnDoc = (char*)malloc((strlen (doc)+1) * (sizeof(char)));
        strcpy(returnDoc, doc);
        return returnDoc;
    }
    
    void print_word(char* word) {
        printf("%s", word);
    }
    
    void print_sentence(char** sentence) {
        int word_count;
        scanf("%d", &word_count);
        for(int i = 0; i < word_count; i++){
            printf("%s", sentence[i]);
            if( i != word_count - 1)
                printf(" ");
        }
    } 
    
    void print_paragraph(char*** paragraph) {
        int sentence_count;
        scanf("%d", &sentence_count);
        for (int i = 0; i < sentence_count; i++) {
            print_sentence(*(paragraph + i));
            printf(".");
        }
    }
    
    int main() 
    {
        char* text = get_input_text();
        char**** document = get_document(text);
    
        int q;
        scanf("%d", &q);
    
        while (q--) {
            int type;
            scanf("%d", &type);
    
            if (type == 3){
                int k, m, n;
                scanf("%d %d %d", &k, &m, &n);
                char* word = kth_word_in_mth_sentence_of_nth_paragraph(document, k, m, n);
                print_word(word);
            }
    
            else if (type == 2){
                int k, m;
                scanf("%d %d", &k, &m);
                char** sentence = kth_sentence_in_mth_paragraph(document, k, m);
                print_sentence(sentence);
            }
    
            else{
                int k;
                scanf("%d", &k);
                char*** paragraph = kth_paragraph(document, k);
                print_paragraph(paragraph);
            }
            printf("\n");
        }     
    }
    
  • + 0 comments
    char* kth_word_in_mth_sentence_of_nth_paragraph(char**** document, int k, int m, int n) {
        return document[n-1][m-1][k-1];
    }
    
    char** kth_sentence_in_mth_paragraph(char**** document, int k, int m) { 
        return document[m-1][k-1];
    }
    
    char*** kth_paragraph(char**** document, int k) {
        return document[k-1];
    }
    
    char**** get_document(char* text) {
        int count_word = 0;
        int count_sentence = 0;
        int count_paragraph = 1;
        int len = strlen(text);
        for(int i = 0; i < len; i++)
        {
            if(text[i] == ' ')
                count_word++;
            else if(text[i] == '.')
            {
                count_word++;
                count_sentence++;
            }
            else if(text[i] == '\n')
                count_paragraph++;
        }
        char** words = (char**) malloc(count_word * sizeof(char*));
        words[0] = text;
        char*** sentences = (char***) malloc(count_sentence * sizeof(char**));
        sentences[0] = words;
        char**** paragraphs = (char****) malloc(count_paragraph * sizeof(char***));
        paragraphs[0] = sentences;
        
        for(int i = 1, i_word = 1, i_sentence = 1, i_paragraph = 1; i < len; i++)
        {
            if(text[i] == ' ')
            {
                text[i] = '\0';
                words[i_word++] = text+i+1;
            }
            else if(text[i] == '.')
            {
                text[i] = '\0';
                if(i_sentence < count_sentence && text[i+1] != '\n')
                {
                    words[i_word++] = text+i+1;
                    sentences[i_sentence++] = words + i_word - 1;
                }
            }
            else if(text[i] == '\n')
            {
                words[i_word++] = text+i+1;
                sentences[i_sentence++] = words + i_word - 1;
                paragraphs[i_paragraph++] = sentences + i_sentence -1;
            }
        }
        return paragraphs;
    }