When preparing for a job interview, one of the tasks I encountered was a problem that emphasized proficiency in the C programming language and data structures. The task, which you can find [here]({{ site.github.owner_url }}/concordance#concordance), revolved around efficient search and insertion operations for key-value pairs. The keys, unique words extracted from an input document, needed to map to an array of line numbers in the document where the word appeared. Given the frequent need for search and insert operations, it was evident that hash tables would be the ideal data structure for this task, boasting an average and amortized case complexity of O(1).
For my implementation of the hash table, I drew inspiration from the one presented in James Aspnes's PineWiki. While this implementation is straightforward and serves well for educational purposes, it falls short when it comes to production-level performance. If you seek a robust, high-performance hash table solution for C, consider exploring alternatives like jwHash.
In addition to my C implementation, I also tackled this task in C++ and Python, utilizing the built-in containers available in both languages. In C++, I leveraged the power of the Standard Template Library (STL) with data structures like unordered_map, map, and vector. In Python, I relied on the simplicity of dict and list.
Unsurprisingly, the C++ implementation outperformed the others. However, I must admit that I did not fully exploit the capabilities of C in my C implementation. Furthermore, it's worth noting that my C hash table implementation employed chaining, which, while a valid approach, falls short of the performance potential offered by open addressing techniques.
This task offered a compelling opportunity to compare the performance of C/C++ and Python when dealing with a real-world problem. While C/C++ demonstrated their prowess in terms of performance, Python showcased its ease of use and rapid development capabilities. It's a testament to Python's versatility that it remains a popular choice, even for tasks where performance is a critical factor.
In summary, this interview task not only challenged my C programming skills but also highlighted the trade-offs between performance and ease of use in different programming languages. The choice between C/C++ and Python ultimately depends on the specific requirements of the project at hand and the balance you aim to strike between performance and development speed.