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]
Tag Archive for 'C++'
Programming exercise: interweaved strings
[Permalink]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
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:
Nostalgia: Old Computer Programming Software and Books
[Permalink]I had actually posted this to my Facebook about two weeks ago. At the time, I wrote:
I recently threw out several boxes of old computer programming software and books, because they were obsolete, and I didn’t know anyone who wanted them. For nostalgia’s sake, I took photos of the stuff I threw out. It’s such a pity that commercial software and the associated books become outdated so quickly.
I’m reposting the photos here… » [Expand post] [Permalink]
If you like this post, you might also like:
Mock-up of a Yudit-like mobile application
[Permalink]One application that I always look for in a mobile device is a multilingual dictionary. If one is not available, I can make do with support for multiple input methods (such as through SCIM), access to the internet, and a decent web browser (one that handles non-Latin fonts and right-to-left scripts).
I often end up using a program called Yudit, a Unicode editor written by Gáspár Sinai, even on a system that has native integrated support for multiple input methods, because it’s available on a wide range of systems and I’m familiar with the input methods bundled with it. For example, even though the same input method is supposedly available on both Microsoft Windows and through SCIM, there may be slight differences in the keyboard layouts that can result in typos if one is not careful.
It seems that the majority of wireless handheld devices ship with only one input method. Yudit does not appear to run on any of the major mobile operating systems… » [Expand post] [Permalink]