-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
654 lines (593 loc) · 24.4 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
<!DOCTYPE html>
<html lang="en">
<head>
<meta name="generator" content="HTML Tidy for Linux (vers 25 March 2009), see www.w3.org">
<title>C++ Practice Programs</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link type="text/css" href="css/ui-lightness/jquery-ui-1.8.21.custom.css" rel="stylesheet">
<link type="text/css" href="./css/style.css" rel="stylesheet">
<link type="text/css" href="css/syntaxhighlighter/shCoreDefault.css" rel="stylesheet" />
<script type="text/javascript" src="js/jquery-1.7.2.min.js"></script>
<script type="text/javascript" src="js/jquery-ui-1.8.21.custom.min.js"></script>
<script type="text/javascript" src="js/syntaxhighlighter/shCore.js"></script>
<script type="text/javascript" src="js/syntaxhighlighter/shBrushCpp.js"></script>
<script type="text/javascript" src="js/script.js"></script>
</head>
<body id="index">
<h2>Basic Programming Challenges</h2>
<div id="accordion1">
<h3><a href="#section1">Count the number of lines in a file</a></h3>
<div>
<p>Here's a simple help free challenge to get you started: write a program that takes a file as an argument and counts the total number of lines. Lines are defined as ending with a newline character. Program usage should be</p>
<pre class="inPara">
count filename.txt
</pre>
<p>and the output should be the line count.</p>
<a href="#" class="codeButton1">Show / Hide Solution code</a><div class="code1 code">
<pre class="brush: cpp;">
#include <fstream>
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
if(argc!=2)
{
cout<<"Input should be of the form 'count filename.txt'";
return 1;
}
else
{
ifstream input_file(argv[1]);
if(!input_file)
{
cout << "File " << argv[1] << " does not exist";
return 0;
}
char c;
int count = 0;
while(input_file.get(c))
{
if(c == '\n')
{
count++;
}
}
cout << "Total lines in file: " << count;
}
return 0;
}
</pre><!-- End of code1 pre --></div>
</div>
<h3><a href="#section2">Determine the size of a file</a></h3>
<div>
<p>In this challenge, given the name of a file, print out the size of the file, in bytes. If no file is given, provide a help string to the user that indicates how to use the program. You might need help with <a href="http://www.cprogramming.com/tutorial/lesson14.html">taking parameters via the command line</a> or <a href="http://www.cprogramming.com/tutorial/lesson10.html">file I/O in C++</a> (if you want to solve this problem in C, you might be interested in this article on <a href="http://www.cprogramming.com/tutorial/cfileio.html">C file I/O</a>).</p>
<a href="#" class="codeButton2">Show / Hide Solution code</a><div class="code2 code">
<pre class="brush: cpp">
/*
* This solution uses some sophisticated features of ifstream, but it can be done by simple counting bytes as well.
* This program was created by Denis Meyer (http://www.calltopower.de/blog/)
*/
#include <iostream>
#include <fstream>
using namespace std;
int main (int argc, char* const argv[]) {
if ( argc < 1 )
{
cout << endl << "Usage programname filename" << endl << endl;
return 1;
}
else if ( argc != 2 )
{
cout << endl << "Usage: " << argv[0] << " filename" << endl << endl;
return 1;
}
ifstream file(argv[1]);
if(!file.is_open()) {
cout << endl << "Couldn't open File " << argv[1] << endl << endl;
return 1;
}
long begin, end;
begin = file.tellg();
file.seekg (0, ios::end);
end = file.tellg();
file.close();
cout << endl << "The Size of the File '" << argv[1] << "' is: " << (end-begin) << " Byte." << endl << endl;
return 0;
}
</pre><!-- End of code2 pre --></div>
</div>
<h3><a href="#section3">Find all permutations of a given input</a></h3>
<div>
<h3>String Permutation Challenge</h3>
<p>Here is another mathematical problem, where the trick is as much to discover the algorithm as it is to write the code: write a program to display all possible permutations of a given input string--if the string contains duplicate characters, you may have multiple repeated results. Input should be of the form</p>
<pre class="inPara">
permute string
</pre>
<p>and output should be a word per line.</p>
<p>Here is a sample for the input cat</p>
<pre class="inPara">
cat
cta
act
atc
tac
tca
</pre>
<a href="#" class="codeButton3">Show / Hide Solution code</a><div class="code3 code">
<pre class="brush: cpp">
/*
* The trick to string permutations is to find all permutations that begin with one letter,
* then all permutations that begin with a second letter, and so forth.
* This might suggest a recursive solution: in order to find all permutations that begin with a given letter,
* call permute on the remainder of the string,
* thereby finding all permutations of the substring using the same algorithm.
*
* This is one of the solutions
*/
#include <iostream>
#include <string>
using namespace std;
string swtch(string topermute, int x, int y)
{
string newstring = topermute;
newstring[x] = newstring[y];
newstring[y] = topermute[x]; //avoids temp variable
return newstring;
}
void permute(string topermute, int place)
{
if(place == topermute.length() - 1)
{
cout << topermute << endl;
}
for(int nextchar = place; nextchar <
topermute.length(); nextchar++)
{
permute(swtch(topermute, place, nextchar),
place+1);
}
}
int main(int argc, char* argv[])
{
if(argc!=2)
{
cout << "Proper input is 'permute string'";
return 1;
}
permute(argv[1], 0);
}
</pre><!-- End of code3 pre --></div>
</div>
</div>
<h2>Intermediate Programming Challenges</h2>
<div id="accordion2">
<h3><a href="#section4">Integer to English Conversion</a></h3>
<div>
<p>Write a program that takes an integer and displays the English name of that value. You should support both positive and negative numbers, in the range supported by a 32-bit integer (approximately -2 billion to 2 billion).</p>
<p><em>Examples:</em></p>
<pre class="inPara">
10 -> ten
121 -> one hundred twenty one
1032 -> one thousand thirty two
11043 -> eleven thousand forty three
1200000 -> one million two hundred thousand
</pre>
<a href="#" class="codeButton4">Show / Hide Solution code</a><div class="code4 code">
<pre class="brush: cpp">
#include <string>
#include <iostream>
using namespace std;
string num_to_text[] = { "", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
"eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
string tens_to_text[] = { "", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" };
string power_to_text[] = { "", "thousand", "million", "billion" };
string padIfNeeded (string ans)
{
if ( ans == "" )
{
return "";
}
return " " + ans;
}
string translateHundred (int hundred_chunk)
{
// handle special cases in the teens
if ( hundred_chunk < 20 ) {
return num_to_text[ hundred_chunk ];
}
int tens = hundred_chunk / 10;
int ones = hundred_chunk % 10;
return tens_to_text[ tens ] + padIfNeeded( num_to_text[ ones ] );
}
string translateThousand (int thousand_chunk)
{
if ( thousand_chunk < 100 )
{
return translateHundred( thousand_chunk );
}
else
{
int hundreds = thousand_chunk / 100;
int hundred_chunk = thousand_chunk % 100;
return num_to_text[ hundreds ] + " hundred" + padIfNeeded( translateHundred( hundred_chunk ) );
}
}
int main()
{
int n;
cin >> n;
string number;
bool is_negative = false;
if ( n < 0 )
{
is_negative = true;
n *= -1;
}
int chunk_count = 0;
while ( n > 0 )
{
if ( n % 1000 != 0 ) {
number = translateThousand( n % 1000 ) + padIfNeeded( power_to_text[ chunk_count ] + padIfNeeded( number ) );
}
n /= 1000;
chunk_count++;
}
if ( number == "" )
{
number = "zero";
}
if ( is_negative )
{
number = "negative " + number;
}
cout << number << endl;
}
</pre></div><!-- 1 of 7 -->
</div>
<h3><a href="#section5">Factorial Challenge (Not finding X factorial!)</a></h3>
<div>
<p>Here's a challenge that's a bit more mathematical in nature. Write a program that determines the number of trailing zeros at the end of X! (X factorial), where X is an arbitrary number. For instance, 5! is 120, so it has one trailing zero. (How can you handle extremely values, such as 100!?) The input format should be that the program asks the user to enter a number, minus the !.</p>
<a href="#" class="codeButton5">Show / Hide Solution code</a><div class="code5 code">
<pre class="brush: cpp">
/*
* The trick here is to realize that the limiting case is the number of times five will be a factor of X!, as 5*2 = 10,
* and any time the number is multiplied by 10, there will be an additional trailing zero.
* Due to the abundance of even numbers, there are plenty of spare twos that are factors of any number.
* The trick is that the number of trailing zeros in X! is the number of times five divides into the number, plus the number of times 25 divides into the number,
* plus the number of times 125 divides into the number, and so forth.
* (25 is 5*5, so when five is divided into the number, that still leaves a single 5 remaining as a factor.)
*/
#include <iostream>
using namespace std;
int main()
{
int factorialnumber = 0;
cout << "Please enter a number: ";
cin >> factorialnumber;
int zero_count = 0;
for(int five_factor=5;
five_factor <= factorialnumber;
five_factor*=5)
{
zero_count += factorialnumber/five_factor;
}
cout << "Trailing zeros of " << factorialnumber;
cout << "! is " << zero_count << endl;
}
</pre></div><!-- 2 of 7 -->
</div>
<h3><a href="#section6">String Searching with wildcards</a></h3>
<div>
<p>Write a program that takes two arguments at the command line, both strings. The program checks to see whether or not the second string is a substring of the first (without using the substr -- or any other library -- function). One caveat: any * in the second string can match zero or more characters in the first string, so if the input were abcd and the substring were a*c, then it would count as a substring. Also, include functionality to allow an asterisk to be taken literally if preceded by a \, and a \ is taken literally except when preceding an asterisk.</p>
<a href="#" class="codeButton6">Show / Hide Solution code</a><div class="code6 code">
<pre class="brush: cpp">
#include <iostream>
using namespace std;
int count_asterisks(char *str)
{
int asterisk_count = 0;
for(int x=0; x < strlen(str); x++)
{
if(x=='*' && (x == 0 || str[x-1] != '\\'))
{
asterisk_count++;
}
}
return asterisk_count;
}
bool match_within(char *, char *);
bool match_at_front(char * search_in, char * search_for)
{
if(search_for[0] == '\0') //everything matches
{
return true;
}
else if(search_in[0] == '\0') //end of first string
{
return false;
}
else if(search_for[0] == '*')
{ //any number of initial characters are chewed up by the *
return match_within(search_in, (search_for+1));
}
else if(search_for[0] == '\\' && search_for[1] == '*')
{
if(search_in[0] == '*')
{
return match_at_front(search_in + 1, search_for + 2);
}
else
{
return false;
}
}
else if(search_for[0] == search_in[0])
{
return match_at_front(search_in+1, search_for+1);
}
else
{
return false;
}
}
bool match_within(char * search_in, char * search_for)
{
for(int x=0;
x <= strlen(search_in)-strlen(search_for)-count_asterisks(search_for); x++)
{
if(match_at_front(search_in+x, search_for))
{
return true;
}
}
return false;
}
int main(int argc, char* argv[])
{
if(argc != 3)
{
cout<<"Input should be of the form substring str1 str2";
return 0;
}
if(match_within(argv[1], argv[2]))
{
cout << "String " << argv[2];
cout << " is contained within " << argv[1] << ".";
}
else
{
cout << "String " << argv[2] << " is not contained within ";
cout << argv[1] << ".";
}
}
/*
* The logic behind this solution is that search_within searches to find if at any place in the first string, the second string matches the next part of the first string.
* The find_at_front function is used to check if at any given starting spot in the first string, the second string matches.
* The trick to handle is asterisk matching any number of characters is that an asterisk matches any number of characters, so when an asterisk appears at the beginning of a string,
* that means that whatever remains of the string after the asterisk should match as a substring of the first string.
* And because of the way find_at_front recursively moves down each string, whenever an asterisk occurs in the second_string, it will be at the front, so we test to see if the remainder of the second string is a substring of the first string.
*
* Notice the use of pointer arithmetic to simplify the manipulation of the strings.
*/
</pre></div><!-- 3 of 7 -->
</div>
<h3><a href="#section7">Converting Decimal to Binary</a></h3>
<div>
<p>Write a program that accepts a base ten (non-fractional) number at the command line and outputs the binary representation of that number. Sample input is</p>
<pre class="inPara">
dectobin 120
</pre>
<a href="#" class="codeButton7">Show / Hide Solution code</a><div class="code7 code">
<pre class="brush: cpp">
#include <iostream>
#include <math.h>
#include <ctype.h>
using namespace std;
int dectobin(int dec, int power_of_two)
{
if(dec == 0)
{
cout << "0";
}
else if(dec/(int)pow(2, power_of_two))
{
int remainder = dectobin(dec, power_of_two+1);
if(remainder/(int)pow(2, power_of_two))
{
cout << "1";
return remainder - (int)pow(2, power_of_two);
}
else
{
cout << "0";
return remainder;
}
}
else
{
return dec;
}
}
int main(int argc, char *argv[])
{
if(argc != 2)
{
cout << "Input is of format 'dectobin num'";
return 1;
}
dectobin(atoi(argv[1]), 0);
}
/*
* The logic behind the program is to find the largest power of two that fits in the decimal number; this is the first one output in the decimal number.
* The remainder is returned down the recursive chain, and if the current power of two at each function call fits within the remainder,
* then the function outputs a 1 and returns the remainder minus the amount accounted for by that place in the binary number.
* Otherwise a 0 is output as a placeholder and the remainder is returned to allow it to be checked against the next smallest power of two.
*/
</pre></div><!-- 4 of 7 -->
</div>
<h3><a href="#section8">Computing Pascal's Triangle</a></h3>
<div>
<p>Write a program to compute the value of a given position in Pascal's Triangle (See image).</p>
<img src="./images/pascal.jpg" alt="Pascal's Triangle">
<p>The way to compute any given position's value is to add up the numbers to the position's right and left in the preceding row. For instance, to compute the middle number in the third row, you add 1 and 1; the sides of the triangle are always 1 because you only add the number to the upper left or the upper right (there being no second number on the other side).</p>
<p>The program should prompt the user to input a row and a position in the row. The program should ensure that the input is valid before computing a value for the position.</p>
<a href="#" class="codeButton8">Show / Hide Solution code</a><div class="code8 code">
<pre class="brush: cpp">
#include <iostream>
using namespace std;
int compute_pascal(int row, int position)
{
if(position == 1)
{
return 1;
}
else if(position == row)
{
return 1;
}
else
{
return compute_pascal(row-1, position) + compute_pascal(row-1, position-1);
}
}
int main()
{
int row, position;
cout << "Please input a row and a position along the row: ";
cin >> row >> position;
if(row < position)
{
cout << "Invalid entry. Position must be less than or equal to row.";
return 0;
}
cout << "Value at row " << row << " and position " << position << " is " << compute_pascal(row, position);
}
/*
* A nice recursive solution works because each number is computed from only two other numbers, each of which are computed by two other numbers,
* and the base case is always reached because the algorithm essentially climbs to the apex of the triangle (or to the sides),
* which will always be reached by the nature of the problem.
*/
</pre></div><!-- 5 of 7 -->
</div>
<h3><a href="#section9">Print a linked-list in reverse order</a></h3>
<div>
<p>Using whatever programming techniques you know, write the cleanest possible function you can think of to print a singly linked list in reverse. The format for the node should be a struct containing an integer value, val, and a next pointer to the following node.</p>
<a href="#" class="codeButton9">Show / Hide Solution code</a><div class="code9 code">
<pre class="brush: cpp">
/*
* This code is in C; the only major difference between it and C++ are in the way that structs are declared; in C++, "node* next" is sufficient.
* It would, of course, be possible to replace the printf with cout if so desired.
*/
#include <stdio.h>
struct node
{
int val;
struct node* next;
};
void print_reverse( struct node* list )
{
if ( list != 0 )
{
print_reverse( list->next );
printf( "%d\n", list->val );
}
}
/*
* This solution uses recursion to reverse the linked list by, in effect, placing every element on the list on the call stack.
* Since the first element put on a stack is the last one removed, by putting the list on the stack in order,
* we can remove the elements in exactly the reverse order.
*/
</pre></div><!-- 6 of 7 -->
</div>
<h3><a href="#section10">Implement an in-place linked list reversal</a></h3>
<div>
<p>This challenge, similar to the last linked list challenge, involves reversing a singly linked list--but this time, you must not out the list but actually reverse the entire list in place. By in-place, I mean that no memory can be allocated. The resulting code should be function that takes the head of a list and returns a the new head of the reversed list.</p>
<a href="#" class="codeButton10">Show / Hide Solution code</a><div class="code10 code">
<pre class="brush: cpp">
struct node
{
int val;
struct node* next;
};
struct node* reverse (struct node* list)
{
/* initialization */
struct node *reversed_list_head = 0;
struct node *rest_orig_list = list;
/* build up the reversed_list like a stack while the original list
remains */
while ( rest_orig_list != 0 )
{
struct node *orig_list_tail = rest_orig_list->next;
/* the head of the remainder of the original list will be the
new head of the new list */
rest_orig_list->next = reversed_list_head;
reversed_list_head = rest_orig_list;
rest_orig_list = orig_list_tail;
}
return reversed_list_head;
}
/*
* Note that copying the input into a new pointer, rest_orig_list, wasn't strictly necessary,
* but doing so allows us to avoid confusing two separate tasks: taking an input into the function and iterating over the list.
*/
</pre></div><!-- 7 of 7 -->
</div>
</div>
<h2>Advanced Programming Challenges</h2>
<div id="accordion3">
<h3><a href="#section11">Efficiently find the Maximum Subarray Sum</a></h3>
<div>
<p>In this challenge, given an array of integers, the goal is to efficiently find the subarray that has the greatest value when all of its elements are summed together. Note that because some elements of the array may be negative, the problem is not solved by simply picking the start and end elements of the array to be the subarrray, and summing the entire array.</p>
<p>For example, given the array</p>
<pre class="inPara">
{1, 2, -5, 4, -3, 2}
</pre>
<p>The maximum sum of a subarray is 4. It is possible for the subarray to be zero elements in length (if every element of the array were negative).</p>
<p>Before you write the code, take some time to think of the most efficient solution possible; it may surprise you. The major goal of this challenge is to test your algorithmic skills rather than merely your ability to write code quickly.</p>
<a href="#" class="codeButton11">Show / Hide Solution code</a><div class="code11 code">
<pre class="brush: cpp">
/*
* This can be solved in O(n) time using the following code that makes only a single pass over the array
*/
int max_sum(int *vector, int len)
{
int best = 0, current = 0;
int i = 0;
for(i = 0; i < len; ++i)
{
current += *(vector + i);
if(current < 0)
{
current = 0;
}
best = best > current ? best : current;
}
return best;
}
</pre></div>
</div>
<h3><a href="#section12">Write a self-printing program without file IO</a></h3>
<div>
<p>Write a program that, when run, will print out its source code. This source code, in turn, should compile and print out itself. (Fun fact: a program that prints itself is called a quine.)</p>
<a href="#" class="codeButton12">Show / Hide Solution code</a><div class="code12 code">
<pre class="brush: cpp">
#include <stdio.h>
char *program = "#include <stdio.h>%cchar *program = %c%s%c;%cint main()%c{%c
printf(program, 10, 34, program, 34, 10, 10, 10, 10, 10, 10);%c return 0;%c}%c";
int main()
{
printf(program, 10, 34, program, 34, 10, 10, 10, 10, 10, 10);
return 0;
}
/*
* The two key tricks here are using a string with an embedded %s specifier to allow the string to contain itself when printed,
* and to use the %c format specifier to allow printing out special characters like newlines,
* which could not otherwise be embedded in the output string.
*/
</pre></div>
</div>
</div>
<p>Reference: <a href="http://www.cprogramming.com/challenge.html">Cprogramming.com</a></p>
</body>
</html>