How to Improve Your Programming Question Skills?

[jd12345]

Currently I am solving some programming questions. All questions seem very general.

In mathematics or science I know what kind of questions we encounter. But in programming, the questions don't seem to fall into any category. So how do I train or practice questions to get better at it?

 

[trollcast]

Currently I am solving some programming questions. All questions seem very general.

In mathematics or science I know what kind of questions we encounter. But in programming, the questions don't seem to fall into any category. So how do I train or practice questions to get better at it?

Is this for a programming competition or are you learning to program as the answers could be quite different depending on the context?

 

[jd12345]

Well for a programming contest.
But I would also like to know what type of problems are there outside competitions

 

[trollcast]

Well for a programming contest.
But I would also like to know what type of problems are there outside competitions

Start off with this quote from the USACO site:

Hal Burch conducted an analysis over spring break of 1999 and made an amazing discovery: there are only 16 types of programming contest problems! Furthermore, the top several comprise almost 80% of the problems seen at the IOI. Here they are:
Dynamic Programming
Greedy
Complete Search
Flood Fill
Shortest Path
Recursive Search Techniques
Minimum Spanning Tree
Knapsack
Computational Geometry
Network Flow
Eulerian Path
Two-Dimensional Convex Hull
BigNums
Heuristic Search
Approximate Search
Ad Hoc Problems

The most challenging problems are Combination Problems which involve a loop (combinations, subsets, etc.) around one of the above algorithms - or even a loop of one algorithm with another inside it. These seem extraordinarily tricky to get right, even though conceptually they are ``obvious''.

If you can master solving just 40% of these problem types, you can almost guarantee a silver medal at the IOI. Mastering 80% moves you into the gold range almost for sure. Of course, `mastery' is a tough nut to crack! We'll be supplying a plethora of problems so that you can hone your skills in the quest for international fame.

That should give you an idea of what types problems are being asked at some of the highest programming competitions.

However since programming questions can take on elements from different types of problems there are lots of problems which don't fit neatly into one category or another.

The best way to practice for a competition is to find loads of old problems and look over them as well as learn about algorithms like sorting algorithms, prime factorisation algorithms etc as these can often be used as part of a solution to some problems.

Also learn how to optimise your code as quite a few problems are specifically designed to challenge a programmers skill at writing a efficient solution to the problem.

 

[jd12345]

Thanks for the list.
However what is the relevance of these problems to my future job.
In mathematics we prove equations, in science and engineering we try to give mathematical models etc.
But in computer science we are solving such questions. Although I find these interesting and enjoyable I fail to see the point of these type of questions

 

[trollcast]

Thanks for the list.
However what is the relevance of these problems to my future job.
In mathematics we prove equations, in science and engineering we try to give mathematical models etc.
But in computer science we are solving such questions. Although I find these interesting and enjoyable I fail to see the point of these type of questions

Well for example from some of the problems in the list:

Knapsack problems relate to real life issues such as cutting patterns for materials to reduce wastage or selecting shares or stocks to balance risk against projected returns.

Greedy algorithms can be related to routing packets across internet/computer network nodes to reach their destination.

Shortest path problems are very very very similar to the computations your sat nav makes to plot your route from location A to location B.

Then search algorithms are used every second by websites like google and others to trawl their databases for information efficiently.

 

[Bill Simpson]

Thanks for the list.
However what is the relevance of these problems to my future job.
...
Although I find these interesting and enjoyable I fail to see the point of these type of questions

If I remember the title correctly then the book "Programming interviews exposed: secrets to landing your next job" by Mongan, Giguère and Kindler tries to answer that particular question. The book has an assortment of such problems for you to work on, but much more important for you, the book tries to explain the point of these kinds of questions.

I can't speak for them, but I think the authors claim that when such programming problems are used well that they can quickly and efficiently tell a great deal about skill, thinking and methods of a potential new hire and more likely whether the person will be good at the job.

 

[AlephZero]

But in computer science we are solving such questions. Although I find these interesting and enjoyable I fail to see the point of these type of questions

That's one of the big problems with computer science courses IMO. You learn a lot of stuff about computing, but not much about applications (i.e. what computers are actually used for).

Part of the reason is that you can't learn about applications in any depth except by doing another degree course in the application area, and college life is too short for that.

For example if a mech engineer was working on optimizing a design, a process, or a system, it would only take a few minutes to explain why half the items on that list were useful, and the engineer might be using something close to those algorithms already without even knowing they had names. (And there's nothing very special about choosing a mech eng in that example)

 

[jd12345]

Well I understand motive of some type of questions like - number theory questions are useful as computer security depends on it, graph theory is important as computer networks utilize it, searching and sorting questions which use data structures are obviously important and relevant, geometry might be useful in graphics(although not sure)

But I don't understand dynamic programming and greedy problems. They seem like general methods to solve puzzles. Are they any relevant to computer science?

 

[trollcast]

... geometry might be useful in graphics(although not sure)

But I don't understand dynamic programming and greedy problems. They seem like general methods to solve puzzles. Are they any relevant to computer science?

Just a couple of quick real life examples for those 3 areas you've mentioned:

http://edocs.ub.unimaas.nl/loader/file.asp?id=475

That is a paper on the use of dynamic programming to solve problems related to ATM networks (These allow several different data streams to be transferred over the one physical network, eg. voice, data and video over a single connection)

Computational geometry is used by a wide area of fields, probably the most common example is CAD software or image processing software like Photoshop (a lot of the filters and tools are based on computational geometry methods)

For a fuller look at applications of geometry to real life problems click here.

I wasn't so sure about uses for greedy algorithms but a quick google showed several areas where they are being used. DNA sequences can be aligned (it lines up areas of similar DNA code so they can be compared) using a greedy algorithm (http://online.liebertpub.com/doi/pdf/10.1089/10665270050081478) , this is also an area where dynamic programming can be used as well (http://www.ibm.com/developerworks/library/j-seqalign/)

Greedy algorithms can also be used to find solutions to scheduling problems such as train timetables or flight schedules, however I can't find a good paper or website for these uses at the minute.

 

[jd12345]

Thank you - knowing relevance of programming questions motivates me.
Again thank you all who helped

 

[harborsparrow]

You might find answers to your question about relevance in Gayle Laakmann McDowell's book about interviewing for computer science jobs. It's very good.

https://www.amazon.com/dp/098478280X/?tag=pfamazon01-20

 

[jd12345]

I have one more doubt - in other fields if you are good with concepts then you can solve the questions.
For eg:- I will take physics. The problems in physics want you to co-relate different concepts and get an idea how things will behave. You should know the rules(or laws) and understand them to correctly answer the questions.

What do you need to solve programming questions?

Thank you!

 

[Solkar]

What do you need to solve programming questions?

A talent for abstraction and some degree of creativity.

 

[harborsparrow]

A talent for abstraction and some degree of creativity.

I would say also, a good deal of experience wouldn't hurt.

 

[Solkar]

I would say also, a good deal of experience wouldn't hurt.

Agreed.

Any neural net needs training stimuli, so does the human brain.