# Thread: Arrays: General Operations and Algorithms.

1. ## Arrays: General Operations and Algorithms.

I had a test this Tuesday; I failed. Three problems, all array related. A 45 minute time limit.

The first one asked in some fancy wording to basically return the range of consecutive indexes of the highest streak of integers. e.g [90, -100, 45, 3, -56, 529, -190, 200, -10] should return [5, 7] (five to seven, inclusive). This thing took me like 20 minutes to solve. Which I find ridiculous, it looks so easy now. Later I found out I didn't get full credits because my solution didn't pass all of the test cases.

The second problem asked to combine and sort two arrays of integers, without copying or modifying the original arrays and without using tools from any libraries. e.g given arrays [5,1,3] and [4,2,6] I should return [1,2,3,4,5,6]. This is the only one that I got right.

The last problem I thought very simple at first sight but for the life of me I couldn't solve it before running out of time. It required to return the elements of an array in a certain order: given the array ['a', 'b', 'c'] my function should return: [ ['a'], ['a', 'b'], ['a','b','c'], ['a', 'c'], ['b'], ['b', 'c'], ['c'] ]

I decided never to let that happen again. Array problems have always been my weakness. In general, any kind of timed problem solving exercise makes me uneasy. I hate to admit it but I am a slow thinker. I marvel at the way others can come up with solutions so fast when I'm barely starting to dissect the problem into pieces.

IMO, there can only be three possibilities to this: either they're geniuses, they have been exposed to similar problems before so they have a general idea on how to approach it, or I have a turd for a brain and I should sever my testicles so I don't perpetuate my diluted genes onto my offspring.

Whatever the case is, there's nothing I can really do about it except to prepare. So that next time I don't have to reinvent the wheel but merely load the potato sacks into the cart and giddy-up Matilda.

After giving it some thought, I believe array problems can be categorized into two types: Sort and Lookup. Sorting problems require the array to be sorted in a specific way: ascending, descending or by some arbitrary parameter. Lookup problems require you to select specific values from the array., according to some rule.

I would like to know if you guys are aware of any good site with programming exercises related to this topic, or know of good books on the subject, no matter the language.

Thank you.

2. Actually, I think this forum is pretty good for generating problems all on it's own. People generally come here with an idea of what they want to do, and a semi-complete example of code that they think can get the job done (I just typed in "array problem" into the search bar, and got a whole host of problems ).

My advice is to not worry about memorizing the information needed to solve every conceivable problem however. It's much better to try and come up with a system you can view the problem by, then come up with an answer. The system I use sort of looks like this:

1. Identify the problem. (What does my program need to do?).

2. Identify the information needed. (What does my program need to do it?)

3. Identify where the information will come from. (Where will I get what I need? Is the information part of the system already, or will I need to add it?)

4. Identify how to use the information to meet the needs of my program (At this stage we have the puzzle pieces, all that's left is setting them in place.)

This sounds pretty easy, but in real life I've noticed that things rarely go so smoothly. It's important to try and solve one problem at a time, don't try an do to much with a single step.

Anyway, my point is that by trying to memorize solutions to specific problems, you become like a military commander who is always ready for his opponents last operation. All I've done in trying to create my problem solving steps is to identify the points at which pieces of the solution become more apparent, there could be a better more comprehensive way.

3. Practice makes perfect.
Sphere Online Judge (SPOJ)
UVa Online Judge - Home

Problems are a lot easier to solve if you recognise part of the problem in something you've done previously.

4. Originally Posted by skyliner
I had a test this Tuesday; I failed. Three problems, all array related. A 45 minute time limit.
I don't know if this matters, but the test sounds suspect to me, unless the course covered these types of problems explicitly.

Just out of curiosity, I wrote the three programs in C (assuming by 'streak' you meant a consecutive sequence of numbers that sums to zero). I consider myself pretty proficient in C, and good at problem solving, but it still took me half an hour, at zero pressure, to implement these. (One reason I did this is that I don't remember solving these particular problems before. For the first, I used a simple nested loop. For the second, I found the minimum (and counted duplicates), then used a loop to find new minimums larger than the previous minimum (and count duplicates), until the sum total count matches the sum length of the two input arrays; this approach is roughly O(N^2) but robust, and works even in case of duplicates and one array being empty. For the last, I used a simple triple loop.)

In a test situation, I might have failed, too. Their loss.

I do understand that in current IT culture, output is all-important, and quality is an afterthought, perpetually pushed to future versions. In that kind of culture, this test does make sense: it teaches you to go for the fast, easy solutions using memorized patterns. The intent is to produce productive drones, not thinkers.

You might be like me, someone who does need time to think, and is not suited for high-volume code output. On the other hand, given a day or two to think, I can solve problems others take weeks to hack at and declare unsolvable in frustration. My rate of production is low, but the quality thus far seems to compensate for it. (Considering my posts are excessively long and verbose, I don't want to consider what it means for the quality. Reader beware, I guess. Also, I'm often wrong.)

Originally Posted by skyliner
I decided never to let that happen again. Array problems have always been my weakness.
Don't go that way. That way lies clinical depression, burnout, and lots of wasted time. Instead, accept it, and only decide to work on it, without promising anything or demanding any specific results from yourself.

I made a similar decision after picking a business path instead of research as I wished I had. I did quite well business-wise, but my mind crashed and burned. Twice. I have been trying to recover for the last five years or so. It's slow going.

Originally Posted by skyliner
In general, any kind of timed problem solving exercise makes me uneasy.
Me too, because they're designed to measure your productivity and ability to memorize solution patterns, and not your ability to find new solutions.

I even avoid timed puzzle and adventure games (I'm not kidding).

Originally Posted by skyliner
I marvel at the way others can come up with solutions so fast when I'm barely starting to dissect the problem into pieces.
For years, I had a similar problem with higher mathematics (solutions to differential equations and so on). I've never been good at memorizing stuff (other than the first 20 digits of Pi); I easily remember the overview and interesting features (applicable domain, problem spots), but the actual equation or full name of some long-dead scientists the equation is named after, often escapes me.

I had painstakingly pored over my Arfken-Weber (Mathematical Methods for Physicists), with very poor results, almost failing my classes. Suddenly, I realized there was a gaping hole: instead of being shown ways of deconstructing and classifying mathematical problems, my lecturers had concentrated on showing how to prove a solution is a correct solution after you have found a solution. I scanned through the books I had at hand, and created a four-page synopsis for solving differential equations (pretty similar to this WikiHow page). Armed with that one, mostly skipping the lectures as useless, I got a 4 (equivalent to a B) on my next exam.

There is a very similar issue to problem solving. There is a definite craft to it, mostly related to how one should construct their perception of a problem, and how to be willing to discard or revise parts of that mental model, at will. I find it similar to constructing several competing structures in parallel, comparing their merits and failures, and sometimes getting a kick out of the childlike wonder and energy you get by just stomping all over them, and finding a completely different approach to the thing. All of this takes time, but it seems to work.

I have not talked about this with more than two or three different people, so I believe I'm quite likely reinventing the proverbial wheel. I do like to call this area -- the craft of systematic problem solving -- meta-problem-solving, because at the core, it is about solving the problem of problem solving. (Corny name, maybe, but I like the pun. If it wasn't fun, I wouldn't be doing it for fun.) If you or anyone else find good references or books or articles about this, please let me know. The ones I've encountered tend towards philosophy, and have not had any practical relevance to the craft. At this point, I'm just about resigned to trying to compare the few known structured approaches to problem solving in their own respective domains, and trying to find the similarities and differences, to try and uncover the craft beneath.

The thing I do have found, is that the human brain is really, really good at finding that craft all by itself, without specifically knowing what the craft really boils down to, as it is exercised in different problem domains. This is very good news. It means that if you just get experience in solving different types of problems, using different methodologies, your brain tends to become better and better at it.

A good example of this happening is something many programmers have noticed: When you learn new programming languages, learning new programming languages becomes easier. You might think it is just because the programming languages necessarily have similarities, sharing a common mathematical basis, but I disagree: I've found and seen in others that also the capability to understand new paradigms -- like object-oriented programming, or say functional programming -- grows easier. I think it has something to do with "thinking outside the box"; that once your mind realizes its own current limitations, it can overcome them, and that after a few times of realizing the limitations, the mind becomes more able to both perceive and overcome its own limitations in general.

In practice, it seems to me that a wider background experience will produce better problem solvers than current, pipelined limited-to-one-small-domain study programs produce. Feel free to disagree, though; I'm often wrong.
Originally Posted by skyliner
I would like to know if you guys are aware of any good site with programming exercises related to this topic
Um, picking up a specific tool and going looking for problems to solve using that tool, is a pretty poor approach.

Instead, try to branch into areas you're interested in -- even areas you might think you don't have the necessary background knowledge --, and see what kind of problems the enthusiasts there discuss, and how they solve them.

Fortran code -- still very commonly used for scientific computation -- relies heavily on arrays, so you might wish to see if there are scientific computation fields that interest you. On the other hand, Fortran code is often quite poor, more accrued or congealed than designed, written by people with little formal education in abstract data structures or algorithm analysis, resulting in code where brilliant ideas and groan-worthy implementation are happily mixed. However, looking at the problems the code solves, and trying to find better ways to solve the same problems, might help you develop the skills you need.

5. Originally Posted by Nominal Animal
A good example of this happening is something many programmers have noticed: When you learn new programming languages, learning new programming languages becomes easier. You might think it is just because the programming languages necessarily have similarities, sharing a common mathematical basis, but I disagree: I've found and seen in others that also the capability to understand new paradigms -- like object-oriented programming, or say functional programming -- grows easier. I think it has something to do with "thinking outside the box"; that once your mind realizes its own current limitations, it can overcome them, and that after a few times of realizing the limitations, the mind becomes more able to both perceive and overcome its own limitations in general.
Paradigms overlap like anything else, so yes, it becomes easier to grok new ones because you've already come to already understand some shared aspects.

If the mind learned to "think outside the box" to "overcome its own limitations in general", then learning new programming languages would make you be able to learn new musical instruments faster, and vice versa, but this is not the case.

6. Originally Posted by Yarin
If the mind learned to "think outside the box" to "overcome its own limitations in general", then learning new programming languages would make you be able to learn new musical instruments faster, and vice versa, but this is not the case.
I disagree.

First, learning new musical instruments is a matter of training your motor cortex, rather than anything to do with your mind.

Second, learning logic, structures and algorithms, I do believe does help you understand music: that there is structure, and the structures define how we perceive the "moods" in it, how specific structures evoke specific reactions in humans (consider harmonies et cetera), and so on. (In this respect, the current mass-produced four-chord music is utter crap compared to some classical music.)

I'm definitely not claiming it's magic or magick-like: by learning to program, you do not suddenly understand music (or anything else) better. I claim that learning new things open up your mind into new ways of thinking. (Or something like that; it does not work if you only memorize or learn the same kind of things. It's more about being able to perceive in new ways, really.)

Perhaps a funny test might show you how weird this stuff works. If you can think (subvocalize) in more than one language, pick two different but similar puzzles or programming problems. Work on each while thinking completely in one language -- not by translating, but keeping even your subvocalized thoughts in that language --, and compare the results and how long it took you. Then, do the same four or five times, and notice how your performance changes. Perhaps this has more to do with how language itself affects our thinking, but my point is that the relationship between learning new concepts and new ways of thinking, and how you solve problems, is much more complicated than you might believe.

7. Originally Posted by Yarin
If the mind learned to "think outside the box" to "overcome its own limitations in general", then learning new programming languages would make you be able to learn new musical instruments faster, and vice versa, but this is not the case.
Is that "but this is not the case" based on only your gut feeling, or do you have something to back it up?

It seems that learning a musical instrument seems to help your mind grow in other ways, too.

So, at least the inverse seems to happen in real life.

(The Slashdot link was just too funny a coincidence to ignore, sorry!
I don't have any scientific proof myself either way.)

8. O_o

@Nominal Animal: You should give "How to Solve It" by George Pólya a read. I consider it to be the best book ever written on "meta-problem" solving.

Soma

9. Originally Posted by Nominal Animal
Is that "but this is not the case" based on only your gut feeling, or do you have something to back it up?

It seems that learning a musical instrument seems to help your mind grow in other ways, too.

So, at least the inverse seems to happen in real life.

(The Slashdot link was just too funny a coincidence to ignore, sorry!
I don't have any scientific proof myself either way.)

Eh, learning code just makes you more confident of your intellectual abilities, and the more confident you are the less likely you are to fail. I do agree that learning one language helps you learn a second, ect, I just think it's like Yarin says, that you begin to recognize patterns (that is the brains job after all).

It would be nice if it was more than that, but I would need to know the mechanism before I could believe it (if a psychological mechanism even means anything).

10. Originally Posted by Nominal Animal
Is that "but this is not the case" based on only your gut feeling, or do you have something to back it up?
Admittedly, I do not. Just anecdotes.

Originally Posted by Nominal Animal
It seems that learning a musical instrument seems to help your mind grow in other ways, too.

So, at least the inverse seems to happen in real life.
They show that the violinist has finer motor control of her left fingers. That knowing music makes one more apt to discerning tones, and picking out speech from among noise, etc.

This isn't an all-in-one improvement, because playing is diverse in what it demands from the brain, it's benefits are diverse, and so can benefit a more diverse range of activities.
There just isn't any evidence that learning new instruments helps you to learn new programming paradigms, simply because they don't overlap (at least that I know of). Whereas learning music helps with speech, because speech overlaps with music, at tones, noise compensation, etc..

11. Originally Posted by phantomotap
"How to Solve It" by George Pólya
Thanks; that and TRIZ look very promising. (Although now I'm pretty miffed nobody pointed these out when I started my university studies; they just might have saved me countless hours of frustration.)

Originally Posted by Alpo
makes you more confident of your intellectual abilities, and the more confident you are the less likely you are to fail
I guess so too. Or, perhaps, it is more about fear restricting your intellectual abilities, rather than confidence making you less likely to fail. (Confidence just makes it easier to learn from your failures and move on, without dwelling and getting stuck in the failures.)

Certainly, looking at business analysts, high-powered executives, and politicians, intellectual ability seems to not be required at all to be successful. As long as you portray the correct image, failures just do not matter.

Originally Posted by Yarin
playing is diverse in what it demands from the brain, it's benefits are diverse, and so can benefit a more diverse range of activities.
Yes; I cannot rule out that everything I've observed could be simply boiled down to "problem solving in general is a skill that benefits from a wide, diverse background of activities and concepts".

Originally Posted by Yarin
There just isn't any evidence that learning new instruments helps you to learn new programming paradigms, simply because they don't overlap (at least that I know of).
I don't know of any such evidence, either. However, the human brain is excellent at drawing analogies and parallels between completely different scenarios, so I'm not at all sure they do not overlap.

For example, if someone is learning how to play guitar, you could use that to teach how something like an I2C bus works: your hand on the neck controls the pitch/data (SDA line), and plucking the string corresponds to the clock (SCL line). If you move your hand on the neck too early or too late, it'll change the tone. And so on.

You could say that I claim that having a diverse background makes it easier for the human mind to find analogies (even incorrect ones) that yield ideas on how to attack a specific problem; and to compare multiple such attacks, to select the best one. This is what I think is "thinking outside the box". In my experience, this process is mostly subconscious, and somehow a good sleep (a good nap or a full nights sleep) seems to help the process; and only the "best ones" percolate up to the conscious part of my mind.

Most call this process intuition, and it's as good a name as any. I do not think there is anything "magical" or unknowable about it, it's just a natural process related to problem solving and situation awareness, that our brains have evolved.

Segueing back to the original thread, and the post by the OP:

1. Timed problem-solving tests are not designed to evaluate thinkers. They are designed to yield productive drones who can memorize and apply existing solutions without wasting time.
2. Concentrating on a single problem type -- say array operations and algorithms -- is not the best approach to develop your problem solving skills.
Instead, go for a diverse background. Learn new things, even if they don't seem really relevant. Compare, analyse, consider analogies. Have fun. Use your intuition as another tool you have.
3. Understand that social image and actual being/skills are two completely different things.
Some people are good at projecting an image of being a genius (often simply by being well prepared; not being asked questions they haven't prepared to answer). That does not mean they really are.
Ignore the person, and look at what they do instead.
4. Have fun. Life is too short to dwell on our perceived deficiencies. If you have to, learn to work around your weak spots. But most of all, pick something you find fun, and get good at it: the positive experiences and discoveries are what makes life worth living, in my opinion.

12. Originally Posted by Nominal Animal

1. Timed problem-solving tests are not designed to evaluate thinkers. They are designed to yield productive drones who can memorize and apply existing solutions without wasting time.

I remember a line from the movie "Jobs" (Not a good movie, but I liked this line ), it went something like "A system can only produce itself". This was where Steve Jobs was explaining why college wouldn't be any help in making him a person who could innovate. The more I think about my own experience, the more true this rings. A school is a place of disseminating knowledge, but it also disseminates a particular system of thought that once ingrained becomes hard to think outside of.

13. Originally Posted by Nominal Animal
...
Thank you for your kind words, Indeed, I seem to have found a kindred spirit
I don't know about my code quality, but I do like taking my time to ponder over a complicated problem. It is a source of great pleasure for me. The harder, the more compelled I feel. During that day or two it becomes almost an obsession; I think about it even when I'm not (If that makes any sense). Once solved, I like to go back an improve it, by either finding a better algorithm, eliminating redundancy or using clearer, more expressive identifiers (Sometimes I spend minutes on this alone). I find it sad I only get this satisfaction from hobby projects. School work almost always leaves a sour taste in my mouth.

I believe I didn't express myself clearly before. I never meant to set out to memorize every array problem in the universe, hoping I stumble upon it in the future. I agree with you that limiting myself to a small subset of problems can't be very beneficial in the broadscope of things. What I want is to master and internalize a couple of broad concepts applicable to all problems of this kind.

For instance, while looking up sorting algorithms I discovered the “Bubble Sort”. I hadn't heard of this before, and yet I implemented from scratch a very similar algorithm to sort the arrays in problem #2. This isn't the only sorting algorithm or the fastest. But it's simple and easy to implement. It is a nice tool to have. Knowing how it works certainly would have saved me a lot of time on the test.

Similarly, understanding a few searching algorithms can help me devise a custom one that fits a particular problem, much faster.

While not specifically about “solving the problem of problem solving” these volumes are written gold. I just started reading the first volume, titled Algorithms, and it indirectly touches quite a few key points on the subject.
The Art of Computer Programming

Fortran code -- still very commonly used for scientific computation -- relies heavily on arrays, so you might wish to see if there are scientific computation fields that interest you
It is not the first time I've heard that. I will certainly heed your advice.

I have found evidence supporting this. Not only that, any sort of exercise regimen that improves hand dexterity seems to develop the cerebral cortex. Improving your non dominant hand in this way also strengthens the Corpus Callosum and promotes Neurogenesis. I will post my source when find the link.

Originally Posted by Salem
Practice makes perfect.
Sphere Online Judge (SPOJ)
UVa Online Judge - Home
Problems are a lot easier to solve if you recognise part of the problem in something you've done previously.
I agree. Those links seem like an excellent source of practice problems, thanks.

Originally Posted by Nominal Animal

Segueing back to the original thread, and the post by the OP:

1. Timed problem-solving tests are not designed to evaluate thinkers. They are designed to yield productive drones who can memorize and apply existing solutions without wasting time.
2. Concentrating on a single problem type -- say array operations and algorithms -- is not the best approach to develop your problem solving skills.
Instead, go for a diverse background. Learn new things, even if they don't seem really relevant. Compare, analyse, consider analogies. Have fun. Use your intuition as another tool you have.
3. Understand that social image and actual being/skills are two completely different things.
Some people are good at projecting an image of being a genius (often simply by being well prepared; not being asked questions they haven't prepared to answer). That does not mean they really are.
Ignore the person, and look at what they do instead.
4. Have fun. Life is too short to dwell on our perceived deficiencies. If you have to, learn to work around your weak spots. But most of all, pick something you find fun, and get good at it: the positive experiences and discoveries are what makes life worth living, in my opinion.
I appreciate the life lessons you so kindly impart. Your posts exuberate with wisdom, the kind only age and experience provide.
Thank you.