I don’t quite remember where I saw this problem, but I’m sure it’s appeared in a number of places. Given two strings \(s\) and \(t\), determine whether a string \(u\) is formed by interweaving \(s\) and \(t\). That is, determine whether \(u\) can be formed by taking the first few characters of (say) \(s\), followed by the first few characters of \(t\), then the next few characters of \(s\), and so on. For example, the string “abccdcxey” can be formed by interweaving “abcde” with “ccxy”… » [Expand post] [Permalink]
Archive for the 'programming and technical issues' Category
Programming exercise: interweaved strings
[Permalink]If you like this post, you might also like:
2 Comments
Programming exercise: red-white-blue sorting
[Permalink]I’ve been practising coding on the whiteboard for job interviews. This is very different than coding in front of a computer which has a keyboard, a monitor, and a nice editing program that allows you to correct your mistakes and type repetitive text very quickly. I’m trying to keep my programs simple and short, and writing in a C-like pseudocode.
This exercise comes from Skiena’s The Algorithm Design Manual
Persian Soft Keyboard and Applications for Android
[Permalink]Update (July 25, 2010): Please read this before posting a comment, sending me an e-mail, or giving the software a rating on the Android Market. Also, note that the remarks below pertain to Android 2.2 and below, and may become obsolete in the future.
About the keyboard:
- The app is a keyboard. Please do not say that “it doesn’t work” because “I see only squares”. A keyboard does not help you to render fonts or shape glyphs. This software is meant only for people who can already display Persian on their phones, but have no means of input. With that being said, I understand that many people who are looking for an input method for Persian are also looking for a way to display it. Just don’t confuse the two functionalities. (For information on how to display Persian, read on to the next section below.)
- There is nothing sinister about the warning that the software may see sensitive information such as passwords and credit card numbers. It can see anything you type when it is the active keyboard — and so can every other soft keyboard. It does not do anything with this information except to use it to guess what you’re typing. If you don’t want your password or credit card number to be read by the app, just switch to the default Android keyboard when you need to type something secret. (Unless, of course, your password is actually in Persian.)
- On most devices, you have to enable an input method after it’s installed by going into Settings, and to switch input methods you hold the trackball or long-tap with your finger in a text input field. These depend on the operating system, and are not things that I can change.
On installing a font and rooting your phone:
- To display Persian on Android, it is not sufficient just to install a font. You also need to get the system to join the glyphs and to display them in right-to-left order.
- To install a font, you will need to root your phone. Instructions can be found by using a search engine.
- If you are unable to follow the instructions yourself, or cannot find someone who is physically present to take you through the steps, it is unlikely that anyone can help you online. It’s not a trivial task in most cases, and nobody wants to be responsible for accidentally bricking your phone. I will try to help, but please understand that your request is non-trivial. Furthermore, please see the remark above about it not being sufficient just to install a font. Even after a font is installed, there is still a lot of work to do to display Persian on Android. If you do not understand how to root a phone yourself, you will very likely not understand how to go through the rest of the process either.
About displaying Persian on your phone:
- FarsiTel has just announced a Persianised version of Android. If you have a newer Android (2.1 and up) and want a completely Persian ROM, start your investigations there. Note that this solution includes a keyboard also (and it is a different one from mine).
- You can also try Arabic Android for displaying Persian. Yes, it’s designed for Arabic, but it works for Persian also. You may have to pay to obtain right-to-left functionality. Look for the “Arabic Android” app in the market once you have the appropriate image from the site installed.
- There is an app on the Android Market called “Persian Browser” that will enable font-shaping in the web browser only. If your browser displays Perso-Arabic glyphs but don’t join them or display them right-to-left, you can download this app to fix the problem.
- To use these ROMs/apps, you may need to root your phone and/or install fonts. See the section above.
- Disclaimer: I am not involved with these projects, and (to my knowledge) neither is my employer.
And, finally, I cannot make any comments about the state of official support for Persian on Android due to the terms of my employment. This is my personal web site, and is unaffiliated with my employer. Anything I write here about Persian support on Android reflects my personal opinion only.
The original post (from Nov. 16, 2009) follows.
I recently got a new smart phone — an Android-powered HTC Dream. As I wrote in a previous post, one of the first applications that I always look for is a multilingual dictionary, or at the very least a way to enter input in languages other than English… » [Expand post] [Permalink]
If you like this post, you might also like:
Lists of programming exercises
[Permalink]I’ve collected a number of web sites with lists of programming exercises, which I’m going through for practice.
In no particular order, these are… » [Expand post] [Permalink]
Programming exercise: permutations of a string
[Permalink]The problem is to implement a function that outputs all possible permutations of the characters in a string. Unlike combinations, two permutations are considered distinct if they contain the same characters, but in a different order. Also, for the purposes of this exercise, each occurrence of a repeated character is considered to be a distinct character. That is, if the input is “aaa”, the output should be six repetitions of “aaa”. The permutations may be output in any order.
This exercise, like the previous one on combinations of a string, is from the book Programming Interviews Exposed
Programming exercise: combinations of a string
[Permalink]The problem is to implement a function that outputs all possible combinations of the characters in a string (with length ranging from one to the length of the string). Unlike permutations, two combinations are considered to be the same if they contain the same characters, but in a different order. Another way to define the problem is to find the power set of the characters of the string (excluding the empty set).
Like the previous exercise, this one is also from the book Programming Interviews Exposed
Programming exercise: maximum value in integer array, part 1
[Permalink]This exercise is just a little bit more substantial than the last one — but not by very much. Given an array of \(n\) non-negative integers, find the maximum value in the array, or return \(-1\) if the array is empty. Obviously, the use of any built-in maximum-finding function is forbidden. While the problem is almost trivial, it does illustrate how each language works with array or vector data types, as well as how it handles iteration.
This exercise, like some of the other ones that I will also be going through, is from the book Programming Interviews Exposed
Programming exercise: Hello, world!
[Permalink]As a preliminary exercise to jog my memory, here is the obligatory “Hello, world!” program in a variety of languages. On the one hand, the programs do nothing except output a string, and so don’t illustrate very much about the respective languages. On the other hand, the simplicity of the task does illustrate the difference between languages that allow you to begin coding right away versus those that require a considerable amount of setting up (importing libraries, declaring classes, etc.) before you even have a functioning program… » [Expand post] [Permalink]
If you like this post, you might also like:
Programming exercises and comparison of programming languages
[Permalink]I started programming when I was eight years old. The first programming language I learned was Basic, followed very shortly by C and 8086 assembly language. During elementary school, I was also exposed to Pascal and Logo. I ignored Pascal because it seemed to me that anything I could do in it I could already do with C, and although I had some fun with Logo’s turtle graphics, I didn’t take it very seriously. At the time, I didn’t appreciate its connection with Lisp and other “serious” programming languages… » [Expand post] [Permalink]
Fixing the site’s appearance in Internet Explorer
[Permalink]I just spent the day in the library, where I used Internet Explorer on a public terminal. I knew that IE did not render CSS properly, but until I tried to use this web site for several hours in IE, I had no idea how bad things were. I’ve hacked the CSS so that it displays reasonably well in IE now. I hope this didn’t mess things up for other browsers. Grr… » [Expand post] [Permalink]
No related posts.