phoxis Coding Discussions, Computer Science

A wide character trie implementation

It’s been a long time since I posted here. Therefore I decided to dig out some quick and straightforward stuffs from my disk which I previously decided should’t be in this blog.

I have posted multiple trie and dictionary search based programs in C, C++ and Perl before Jumble Work Solver and Jumble Work Solver Again. This time (again!) it’s about a trie. Although this time there was a specific requirement from a group who needed to implement a trie based word distance counting for bangla language, therefore Unicode support. This was supposed to be modified more and plugged into a spelling correction for scanned OCR text in the Bengali language.

Initially I suggested that a ternary tree would be more appropriate as the memory cost for standard trie (not compressed) would be huge. Although, finally the decision was to go with plain and simple trie. I know it is mad, but this is what it is :D.

Also, before going into the implementation, I should note that there is an efficient implementation of Radix Tree present in libcprops library. Though which we won’t be using for this one. I would recommend you people to have a look into this library if you already haven’t seen it yet.

Let’s say, we have a word “hello” and a node with an array of pointers of length 26 representing each character of the English language, each of which indicates that if the ith character follows the character represented by this node. Therefore for this example “hello”, the head node’s array of pointers will have the location 7 pointing to another node, which will have the 4th location of the pointer pointing to another node, whose pointer array’s 11 th location will point to another node and so on. Note here the indexing starts from zero. When the word ends, then the next pointer can be pointed to a special terminal marker node, which can be common to all, and the node is marked as a terminal node. This is essential as a valid word can be a substring of another valid word, in which case the shorter would need to be decided. When another new word like “help” comes in, we will follow the same path upto “hel” created by the word “hello”, and as we find there are no pointer for “p” pointing to any node, a new node will be created as explained before. Continue reading “A wide character trie implementation” →

phoxis C Language, Computer Science

C Q&A #6: An interesting difference between the C and C++ conditional operator

int main (void)
{
  int a = 5, b = 10, c;

  c = a > 3 ? b = 5 : a = 3;
  printf ("%d %d %d\n", a, b, c);
  //cout << a << " " << b << " " << c << endl;
  
  return 0;
}

Have a look at the above code, what will be the outcome if the code was in C language and if in C++ Language (replace with printf with cout)?

Directly going to the solution. Compilation error for C, and works perfect (no warnings) with C++. I saw this problem is a C question and answer book which didn’t bother to explain, so here is the explanation. Continue reading “C Q&A #6: An interesting difference between the C and C++ conditional operator” →

phoxis Coding Discussions, Computer Science

Find pairs of numbers in an array with difference ‘k’

The problem statement is, an long array is given with n elements, we need to find all the pairs of numbers in this long array which have a constant difference k. I will post three methods. The first method is the brute force method and has a runtime complexity O (n2), the next method has runtime complexity O (n*log (n)), and the last one will have the runtime complexity O (n).

Continue reading “Find pairs of numbers in an array with difference ‘k’” →

phoxis Coding Discussions, Computer Science

Jumble word solver again

I have already posted a jumbled word solver written in C language, although what I posted is actually become old, as I have changed some of the things in the code. I will update the post with this (hope to update!) with the new changes, but before it I would like to post the the same stuff in other languages and with different datastructure. Recently I am learning Perl and brushing up C++, therefore I will post jumble word solver written in C++ and Perl in this post.
Continue reading “Jumble word solver again” →

phoxis Coding Discussions, Computer Science

Implement queue using stack

The puzzle is to implement basic queue operations with using only basic stack operations. That is, a stack object is given, we need construct a wrapper for the queue functions, insert, remove, which will only use the stack object as its storage, and naturally will have to use the stack operations. I have already posted the opposite task in the post Implement stack using a queue

This can be done using two stack objects. We call these the first stack and the second stack. Although either the insert or the remove complexity will no more be O(1).

I have discussed the process gradually. I added the last solution when it clicked in my mind while reviewing this post.

Continue reading “Implement queue using stack” →

phoxis C Language, Computer Science, Humor

C LANGUAGE UERS! Y U NO SEE STANDARDS!

C LANGUAGE USERS! Y U NO SEE STANDARDS!
C LANGUAGE USERS!
Y U NO SEE STANDARDS!

I had to make this. There are people who give a damn to the standards and follow the stone age Turbo C 3.1 compiler, run programs compiled by it. In the cases for compiler dependent and undefined behaviours, they try to guess in some way why the output was like that and get into a conclusion. Continue reading “C LANGUAGE UERS! Y U NO SEE STANDARDS!” →

phoxis C Language, Coding Discussions, Computer Science

Journey of a simple recursive code

Some one asked the following question in StackOverflow

Implement a function with prototype char *repeat(char *s, int n) so that it creates and returns a string which consists of n repetitions of the input string s. For example: if the input is “Hello” and 3, the output is “HelloHelloHello”. Use only recursive constructs.

I immediately started compiling the answer as it was a pretty straight forward question. But it was not only me who was posting the answer. So after posting, very quickly other answers started appearing. It was a general everyday answer, until a person (who also answered the question) pointed out a bug in my code. Bugs disturb the mind. So I dug into the code and fixed it. The things started to get challenging when others started to get more compact code, which didn’t let me sit idle.
Continue reading “Journey of a simple recursive code” →

phoxis Coding Discussions, Computer Science

Implement stack using a queue

The puzzle is to implement basic stack operations with using only basic queue operations. That is, a queue object is given, we need construct a wrapper for the stack functions, push, pop, which will only use the queue object as its storage, and naturally will have to use the queue operations.

This can be done using only one queue object. Although either the push or the pop complexity will no more be O(1).
Continue reading “Implement stack using a queue” →