Elastic Tabs

I was just reading Joel Spolsky's column and today he gave this link. It's a nice idea for IDE's. Instead of tabs or spaces just use elastic tabs. Go check it out.

Mihai

Problem: Detecting duplicated items in an array

And another problem :-).

Someone asked me to give him problems so that he can train for an interview. I gave him the problems from google posted here and in turn he gave me another one: You have an array of length n. It is filled with n random numbers between 0 and n-1. The task it to find out if any of them are repeated.

The trivial solution would be to sort the array and detect any repeated number in the sorted array. This one has O(n * log(n)) time complexity. We should be able to do better. Here is what i came out with after a little thinking.

• start with the first element of the array which has a value different from the index at which it is located. For int[] arr = {0, 1, 2, 3, 5, 4} i would start with the position 4 because the value of 5 is different than its index.
• take the value and go in the array at the position represented by that index. Look at the value from there. If the value is the same as that index we just found our duplicate. If not then remember the new value, put the old value in there and do the same.
• if the next value is the original starting position you have just arranged a subset of the original array in the proper place. select the next number matching the condition at step 1 if possible. If not then you are done, you have the array sorted and you also know that there are no repeted numbers in it.

The worst case complexity is lower than O(2 * n). In the best case and medium case probably you will find in less than n/2 operations but this is just a guess. You would have to apply some statistics :-) to find out exactly what is this in the medium case.

Mihai.

Goooogle interview questions II

This is the follow-up I promised some posts ago for the search problem.

Last time I was hinting at a totally different algorithm which might solve the problem. It's quite interesting and fun but .. it doesn't work :-). It will not find the shortest fragment but a short fragment. I'll give the code later. For now here is a variation of the alg I posted which has the same complexity but it's different :-).

Remember that with the algorithm posted you would merge the index arrays while keeping score of the term each index belonged (coloring them as I said). After that you would start with the minimal valid sequence from either end and walk toward the middle of the complete array (by breaking the longest sequence and then rebuilding again with new data) until you would have the same sequence in either end. This will require you to have the original index sets in memory before starting the work. This might be ok in some cases but if the index arrays are big you might get them from a database or web service or something else as a stream. In this case you would start only from one end and do the same (find a valid seq, break it, find another valid seq .. etc) while keeping score of the shortest one so far. This can enable you to actually apply the alg while reading the index sets (if they are too big).

The other interesting solution is this:

• sort the shortest index array.
  
• for each index in this index array you would find the nearest index in the second array.
• with those two numbers you would compute the mean find in the third array the closest number to the mean. - now you will have a couple of candidates (the same amount as the number of items in the shortest index array). You need choose the shortest one.
  

It's a nice algorithm but it doesn't work completely. The counter example is real nice :-). However it is faster because the complexity is something like O(card(S1)) * (1 + O(log(card(S2)) + log(card(S3))) compared with O(card(S1) + card(S2) + card(S3))
as in the first algorithm. In some cases you might be content with the size of the solution it would find. I think is not that far off the real solution. In the case of 3 search terms they are even related :-).

Mihai.

Goooogle interview questions

The other day I got hooked by a friend of mine with a couple of interview questions given by google. Some of them are challenging and quite interesting. Here is one (taken from here): Question #8) Given an array A[string], an array of strings where each string represents a word in a text document. Also given 3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm for an arbitrary number of search terms. This one in effect is asking you to solve the excerpting problem: Given a text, a couple of search terms with the matching positions in the original text you are asked to return an "interesting" fragment of the original text containing all the search term. In this case the interesting criteria is the length of the fragment: the fragment is most interesting when the length is shorter.

My first solution was to the [max(min(S1), min(S2), min(S3)), min(max(S1), max(S2), max(S3))] which is not good. The reason is that you can have cases in which the interval you choose can have a one or more search terms left out: S1 = {1, 3}, S2 = {5, 7}, S3 = {4, 8}. The interval you would get in this case would have been 1, 3 which will only contain the first term. You can also choose the min(min()..) .. max(max()..) solution which is good as an interval containing all the terms but is too broad (in effect is the longest possible). You can merge the S1, S2, S3 sequences and sort them (having "colored" the indexes first). This will be a proper sequences (it has all the colors in it) but it is too long. We need to shorten it. For this we will look at the sequence ends for the shortest subsequences beginning and ending at each end of the current sequence. For example given this sequence: [R1, B3, Y4, R5, .... R11, B10, B15, Y16] we will look at those 2 subsequences: [R1, B3, Y4], [R11, B10, B15, Y16]. Right now we have 3 sequences: the original, the first one of length 3 and the second one of length 4. Because we are looking for the sequence of minimal length we can break the one with length 4. We will ignore then the Y16 term and go ahead and rebuild the second sequence looking deeper into the original sequence. Once we find a proper one we apply the same rule (break the longest one). This will guarantee that we will always have the shorter one. The algorithm will stop when both the found sequences are in fact the same.

There is a problem somewhere in this algorithm but I'll let a little fun in problem for the readers :-). You can easily extend this to more than 3 terms maintaining the exact complexity. The actual complexity of this is O(n) where n is the sum of the term positions in the original text. Also there is another solution totally different than this one and quite interesting which for multiple terms might be faster.
Maybe I'll post it at some point.

Mihai

You want recording ? ( X11 Event recording)

I had the task of creating/updating an X11 application with the ability to "always" have control (or at least knowledge) of the keyboard and mouse no matter what. There were a couple of options. Either grab the mouse and keyboard but with this you have the disadvantage of needing to send events to the target applications by hand. Or you can release the keys and do a grab on a specific key. This might work but you loose the ability to process some keys, or you can watch the events from the outside (using the XRecord extension for example). So I/we choose to go with the third option.

Another part of the equation was that we needed to watch the events only in the cases in which we were forced to release the keyboard and mouse. So the ability to programmatically turn on/off the recording was needed.

I looked on the net for a XRecord API documentation and the only useful one was XRecord library description document. This document is a PDF describing how the API is structured, what the functions and the structures are and how to use them. Everything is fine once you read it but if you read it like me then you are somewhat in trouble because you might miss a proposition that is key in how this API works.
(The document in available here: http://www.x.org/X11R6.8.1/docs/Xext/recordlib.pdf)

How it works:
- first you make a X connection ( using xlib's XOpenDisplay for example ).
- query for the extension with XRecordQueryVersion API function call.
- after that you create a recording context.
- once you have that you need to enable it in order to get events.
- once enabled you start receiving events and when you are tired of them you can disable it.
- free the context
- close the display and that's it.

Now the catch is that you need to use 2 connections: one for data and one to control it but this is not the complete story. This is mentioned in the document but in only 2 lines somewhere at the 1.3 part of the document. And if you read it quick (like me for example) you might miss it and then you start wondering why all the Xlib calls that you try to execute on the connection used to enable the context seem to block mysteriously ? This is somewhat a mistake from my part because I should have read the damn document more closely but this is life....

There are other quirks that you need to remember if you plan to use this: you need to call the XRecordCreateContext on the connection that you will use to enable it (the data connectoin) because it will fail at runtime if not with an Xlib error BadParameter or the like (this is not in the document). Also if you enable the context on one connection (the data connectio usually) you will need to disable it on the other connection (the control) because your calls into Xlib on the data connection will fail. And in the end you need to keep in mind that recorded events are actually xEvents and they seem kind of raw. For example the ButtonPress and ButtonRelease have the correct state for the button which was Pressed/Released but no position information which means you have to keep that state yourself but using the MotionNotify event types and reading the mouse position from them. This is not very good because it places a lot of overhead. If I for example don't need the mouse move events and only need the mouse clicks and clicked position i should be able to get that info from the actual ButtonDown event and not from tracking the mouse.

Mihai