Index

  • A
  • A2Z Interviews: puzzles (website), 604
  • accepting states, 497, 711
  • acyclic networks, 439–440
  • adaptive quadrature, 50–53, 711
  • adaptive techniques, 599, 609
  • adding
    • items, 335–336, 339–341
    • nodes, 303–305
  • AddInterval method, 329
  • AddItemToChild method, 335–336
  • AddNote method, 320
  • Adelson-Velskii, G. M. (mathematician), 350
  • adjacent, 405, 711
  • Advanced Encryption Standard (AES), 520, 532–533, 711
  • advanced linked-list operations, 609
  • adversary, in cryptography, 520, 711
  • AES (Advanced Encryption Standard), 520, 532–533, 711
  • algorithmic goals, 607
  • algorithms
    • all-pairs shortest paths, 431–436, 617
    • backtracking
      • about, 252–253
      • eight queens problem, 254–257, 718
      • knight's tour problem, 257–260, 723
    • basic exercises, 20–22
    • basic network
      • about, 403
      • exercises, 447–450
      • finding paths, 425–436
      • network representations, 407–409
      • network terminology, 403–406
      • shortest path modifications, 441–446
      • strongly connected components, 420–425
      • transitivity, 436–441
      • traversals, 409–420
    • basic recursion, 228–238
    • basics of, 607–608
    • bees, 394, 712
    • binary search, 203–204, 611
    • Boyer-Moore, 493, 504–508, 618, 713
    • branch-and-bound, 616
    • Bron-Kerbosch, 475–480, 714
    • Bubblesort, 171–174, 197, 714
    • Bucketsort, 195–197
    • bully, 587–588, 714
    • characteristics of, 607
    • community detection
      • about, 483
      • clique percolation method (CPM), 485
      • Girvan-Newman, 483–485, 721
      • maximal cliques, 473, 483, 724
    • ContainsDuplicates, 10, 15
    • ContainsNodes, 313–314
    • ContainsNodes, 313–314
    • countingsort, 192–193, 197, 716
    • cryptographical, 619
    • data structures and, 2–3
    • defined, 1, 607, 711
    • distributed
      • about, 561–562, 573, 620
      • byzantine generals problem (BGP), 581–584, 620, 714
      • clock synchronization, 589–590, 620
      • consensus problem, 584–587, 620, 716
      • debugging, 573–574
      • dining philosophers problem, 577–580, 620, 717
      • embarassingly parallel, 574–576, 620
      • embarassingly parallel algorithm, 574–576
      • exercises, 591–593
      • leader election, 587–588, 620
      • mergesort, 576–577
      • mergesort, 189–191, 197, 576–577, 620, 725
      • mergesort algorithm, 576–577
      • snapshot, 588–589, 620, 732
      • two generals problem, 580–581, 620, 736
      • types of parallelism, 562–572
    • Double Metaphone, 514, 718
    • edit distance, 618
    • embarassingly parallel, 574–576, 620
    • Euclidean, 36–37, 608, 719
    • Euclid's, 36–37, 608, 719
    • features of, 6–17
    • FindCellBefore, 75
    • FindLargest, 8–9, 14
    • five-coloring, 459–462
    • Fleury's, 486–487, 720
    • Floyd-Warshall, 98–100, 431, 437, 735
    • Ford-Fulkerson, 466, 720
    • four-coloring, 459, 720
    • Gaussian elimination, 61–62
    • Girvan-Newman, 483–485, 721
    • graphical
    • Heapsort, 175–181, 721
    • Hierholzer's, 487–488, 722
    • InsertCell, 88
    • insertionsort
    • interpolation search, 611
    • Kosaraju's, 421–422, 723
    • Kosaraju-Sharir, 421–422, 732
    • label-correcting shortest path, 617
    • label-setting, 617
    • LeadsToSolution, 253
    • linked-list
      • about, 86
      • copying lists, 86–87
      • sorting with insertionsort, 87–88
      • sorting with selectionsort, 88–89
    • list retracing, 94–95
    • list reversal, 95–97
    • map coloring
      • about, 456, 462–463
      • five-coloring, 459–462
      • four-coloring, 459, 720
      • three-coloring, 458–459
      • two-coloring, 456–458
    • numerical
      • about, 23, 608–609
      • exercises, 68–70
      • finding greatest common divisor (GCD), 36–40
      • finding zeros, 55–57
      • Gaussian elimination, 57–62, 609, 721
      • least square fits, 62–67, 723
      • performing exponentiation, 40–41
      • performing numerical integration, 47–55
      • prime numbers, 42–47
      • randomizing data, 23–36
    • Shor's, 572
    • shortest path
      • about, 441
      • best-first search, 442–443
      • bidirectional search, 442
      • early stopping, 442
      • prohibitions, 443–446
      • shape points, 441–442
      • turn penalties, 443–446
    • Soundex, 511–513, 732
    • specialized tree
      • about, 322
      • animal game, 322–324
      • building trees, 328–329
      • expression evaluation, 324–326
      • intersecting with intervals, 330–332
      • intersecting with points, 329–330
      • interval trees, 326–328
      • quadtrees, 332–337
      • tries, 337–342
    • stable sorting, 191
    • stack
      • about, 141
      • reversing an array, 141
      • stack insertionsort, 145–146
      • stack selectionsort, 146–147
      • tower of Hanoi, 143–145, 235–238, 735
      • train sorting, 142–143
    • stack insertionsort, 145–146
    • stack selectionsort, 146–147
    • string
      • about, 493, 618
      • calculating edit distance, 508–511
      • exercises, 515–517
      • matching parentheses, 494–496
      • pattern matching, 497–504
      • phonetic, 511–514, 618, 728
      • string searching, 504–508
    • swarm intelligence, 616
    • three-coloring, 458–459
    • tortoise-and-hare, 98–100, 431, 437, 735
    • train sorting, 142–143
    • two-coloring, 456–458
  • alignment rule, 395
  • all-pairs shortest paths algorithm, 431–436, 617
  • amortized analysis, 163, 711
  • amortized operations, 615
  • analyzing Quicksort algorithm run time, 182–184
  • ancestors, 286, 288, 712
  • angle brackets, 4
  • animal game, 322–324
  • ant colony optimization, 393–394
  • Appel, Kenneth (mathematician), 459
  • append method (Python), 113, 136
  • approximate optimization, 619
  • approximate routing, 245–246
  • arithmetic expressions, evaluating, 494–496
  • Array class
  • array packing, 610
  • array queues, 148–151
  • array stacks, 138–139
  • ArrayEntry class, 121–122
  • ArrayRow class, 121–122
  • arrays
    • about, 103, 610
    • basic concepts, 103–106
    • in C#, 104
    • circular, 150, 715
    • defined, 3, 712
    • exercises, 132–134
    • Insertionsort algorithm in, 168–169
    • lower-triangular, 118, 724
    • matrices, 129–131
    • nonzero lower bounds, 114–118
    • one-dimensional, 105, 106–113, 723
    • in Python, 103
    • randomizing, 29–30
    • Selectionsort algorithm in, 170–171
    • sparse, 121–129, 610, 732
    • triangular, 118–121, 735
    • two-dimensional, 105
    • upper-triangular, 118, 736
  • Array.Sort method, 18–19
  • art gallery problem, 554
  • Assign method, 421, 422, 424, 425
  • associative arrays. See hash tables
  • asymptotic performance, 7–8, 712
  • attacker, in cryptography, 520, 712
  • augmenting path, 712
  • Augustus, 526
  • average, finding, 107–108
  • AVL trees
    • about, 350
    • adding values, 350–352
    • defined, 615, 712
    • deleting values, 353
  • B
  • back substitution, 60–61, 712
  • backtracking, 35, 613, 712
  • backtracking algorithms
    • about, 252–253
    • eight queens problem, 254–257, 718
    • knight's tour problem, 257–260, 723
  • base case, 228, 291, 712
  • basic array operation, 610
  • basic linked-list operations, 609
  • basic network algorithms
    • about, 403
    • exercises, 447–450
    • finding paths, 425–436
    • network representations, 407–409
    • network terminology, 403–406
    • shortest path modifications, 441–446
    • strongly connected components, 420–425
    • transitivity, 436–441
    • traversals, 409–420
  • bees algorithm, 394, 712
  • Beginning XML, 5th Edition (Fawcett), 295
  • behavior, of algorithms, 607
  • Bellaso, Giovan Battista (cryptologist), 527
  • Berkeley Open Infrastructure for Network Computing (BOINC), 566
  • best-first search, 442–443
  • Bézout, Étienne (mathematician), 38
  • Bézout's identity, 38–40, 712
  • BGP (byzantine generals problem), 581–584, 620, 714
  • biased, 712
  • biased PRNG, 26–29, 608
  • bidirectional search, 442
  • Big O notation, 7–11, 544, 607, 713
  • Big Omega notation, 544, 713
  • Big Theta notation, 544, 713
  • BigInteger data type, 41, 276
  • bin packing problem, 554
  • binary search, 203–204, 713
  • binary search algorithm, 203–204, 611
  • binary tree
  • BinaryNode class, 299, 300, 304
  • Binary-Search method, 201
  • binomial coefficient, 474, 713
  • binomial heaps
    • about, 152–163
    • defined, 713
    • merging, 156–161
  • binomial theorem, 713
  • binomial trees
    • about, 152–154
    • defined, 713
    • merging, 155–156
  • bin-packing problem, 388
  • bipartite detection, 713
  • bipartite graph, 550
  • bipartite matching, 713
  • bipartite matching problem, 550
  • bipartite network, 467, 713
  • block ciphers
    • about, 531
    • defined, 619, 713
    • Feistel cipher, 533–534, 719
    • substitution-permutation network cipher, 531–533
  • Blowfish, 520
  • Boids, 395–397
  • BOINC (Berkeley Open Infrastructure for Network Computing), 566
  • bottleneck traveling salesman problem, 554
  • bottom-up B-tree, 363, 713
  • bottom-up programming, 277, 613
  • Boyer-Moore algorithm, 493, 504–508, 618, 713
  • branch and bound technique, 379–381, 714
  • branch-and-bound algorithm, 616
  • branches, 285, 288, 403, 406, 481–482, 614, 714, 724
  • breadth-first search, 714
  • breadth-first traversals
    • about, 301–302
    • defined, 714
    • for networks, 412–413
  • B+trees, 363–364, 712
  • Bubblesort algorithm, 171–174, 197, 714
  • buckets, 211–213, 359, 714
  • Bucketsort algorithm, 195–197
  • building
    • complete self-avoiding walks, 34–36
    • complete trees, 295–296
    • DFAs for regular expressions, 500–502
    • mazes, 419–420
    • parse trees, 496
    • random walks, 31–36
    • self-avoiding walks, 33–34
    • specialized trees, 328–329
    • threaded trees, 318–320
    • trees in general, 292––295
  • “Building a 270* Teraflops Deep Learning Box for Under $10,000,” 566
  • bully algorithm, 587–588, 714
  • bye, 267–273
  • byzantine generals problem (BGP), 581–584, 620, 714
  • C
  • C#
    • about, 41
    • Array class, 114
    • arrays in, 104
    • automatic memory management and, 79
    • Dictionary class, 209–210
    • dictionary in, 111
    • generating selections in, 474
    • HashTable class, 209–210
    • IndexOf method, 493
    • IntegerCell class, 71–72
    • sorting tools in, 168
    • Stack class, 136
    • string class, 493
  • C programming language, 79
  • C++ programming language, 79, 129
  • Caesar, Julius, 526
  • Caesar substitution cipher, 526–527, 714
  • calculating
    • edit distance, 508–511
    • greatest common divisor (GCD), 36–38
  • call stack, 714
  • call tree, 190
  • capacitated network, 464, 714
  • capacity, 404, 714
  • CareerCup (website), 604
  • Carmichael numbers, 630–631
  • Case statement, 5
  • cells
    • adding at the beginning of linked lists, 75–76
    • adding at the end of linked lists, 76–77
    • defined, 71, 609, 715
    • deleting from linked lists, 78–79
    • finding in linked lists, 73–74
    • inserting after other cells in linked lists, 77–78
    • marking, 92–93
    • systolic arrays and, 562
  • chaining, 211–213, 612
  • Chandy/Misra, 579–580
  • checking local links, 481–482
  • child lists, 614
  • child node, 286, 288, 715
  • Chinese postman problem (CPP), 554, 715
  • chromatic number, 715
  • chromatic number problem, 555
  • cipher, 715., See also specific ciphers
  • ciphertext, 520, 715
  • circular array, 150, 715
  • circular linked lists
    • about, 91–92
    • defined, 715
    • hash tables, 93–94
    • list retracing algorithm, 94–95
    • list reversal algorithm, 95–97
    • marking cells, 92–93
    • tortoise-and-hare algorithm, 98–100
  • clique cover problem, 555
  • clique percolation method (CPM), 485
  • clique problem, 555
  • cliques
    • about, 473–474
    • Bron-Kerbosch algorithm, 475–480, 714
    • brute-force approach, 474–475
    • defined, 715
    • finding triangles, 480–482
  • clock synchronization, 589–590, 620
  • clone references, 472–473
  • closed tour, 723
  • cluster, 565
  • cluster computing, 715
  • clustering, 612
  • cocktail shaker sort, 173, 197, 715
  • cohesion rule, 395
  • collision, 211, 715
  • collision-resolution policy, 211, 715
  • colorability, 617
  • column transposition cipher, 523–525
  • column-major order, 105
  • column-ordered sparse matrices, 131
  • columns, finding, 122–123
  • combinations. See selections
  • common run time functions, 11–16
  • community, 483–485
  • community detection, 715
  • community detection algorithms
    • about, 483
    • clique percolation method (CPM), 485
    • Girvan-Newman, 483–485, 721
    • maximal cliques, 473, 483, 724
  • complete self-avoiding walks, 34–36
  • complete trees
  • condensation, 440, 715
  • connected, 405, 716
  • connected component, 404, 405, 716
  • connectivity, 616
  • connectivity matrix, 119, 716
  • connectivity testing, 413–415
  • consensus problem, 584–587, 620, 716
  • ContainsDuplicates algorithm, 10, 15
  • ContainsNodes algorithm, 313–314
  • contention, 575–576, 620
  • Cook-Levin theorem, 548
  • Cook's theorem, 548
  • CoolInterview puzzles (website), 604
  • coprime, 730
  • copying lists, 86–87
  • costs, 404, 405, 716
  • count method, 84
  • counting
    • combinations, 254–255
    • defined, 611
    • permutations with duplicates, 265
    • permutations without duplicates, 266–267
  • countingsort algorithm, 192–193, 197, 716
  • covering network, 445–446, 716
  • CPM (clique percolation method), 485
  • cryptanalysis, 520, 716
  • cryptographic hash function, 538, 716
  • cryptographical algorithms, 619
  • cryptographically secure pseudorandom number generator (CSPRNG), 26, 716
  • cryptography
    • about, 519–520, 618–619
    • block ciphers, 531–534, 619, 713, 719
    • defined, 716
    • exercises, 540–541
    • public-key encryption, 534–537, 619, 729
    • RSA algorithm, 534–537, 731
    • substitution ciphers, 526–531, 733
    • terminology for, 520–521
    • transposition ciphers, 521–526, 618, 735
    • uses for, 538–539
  • CSPRNG (cryptographically secure pseudorandom number generator), 26, 716
  • cutting stock problem, 389–390, 716
  • cycle, 404, 406, 716
  • cycle detection, 455, 716
  • D
  • dance floor, 394
  • data, randomizing, 23–36
  • Data Encryption Standard (DES), 534, 716
  • data parallelism, 562, 716
  • data processing units (DPUs), 562, 717
  • data structures
    • algorithms and, 2–3
    • defined, 607, 717
  • data structures technique, 599
  • deadlock, 571–572, 717
  • debugging
    • distributed algorithms, 573–574
    • parallel algorithms, 620
  • decipher, 520, 717
  • decision trees
    • about, 367–368, 615–616
    • defined, 717
    • exercises, 398–401
    • searching game trees, 368–375
    • searching general, 375–392
    • swarm intelligence (SI), 392–397
  • degree-constrained spanning tree problem, 555
  • DeleteEntry method, 126, 129
  • deleting
  • dendogram, 717
  • depth, of nodes, 287, 288, 311–312, 717
  • depth-first traversals
    • defined, 717
    • for networks, 410–412
    • for trees, 297
  • distributed computing, 565–567, 718
  • divide-and-conquer approach, 249–252, 599, 611, 613
  • dominating set, 718
  • dominating set problem, 555
  • DoSomething method, 5
  • double hashing, 219
  • double linked lists, 79–81
  • Double Metaphone algorithm, 514, 718
  • double stacks, 139–141, 610
  • DoubleIt method, 5
  • doubly linked lists
  • DPUs (data processing units), 562, 717
  • DrawRelative method, 242, 244–245
  • DSPACE(f(n)), 718
  • DTIME(f(n)), 619, 718
  • duplicates
    • permutations with, 265
    • permutations without, 266–267
    • selections with, 262–263
    • selections without, 264
  • edit distance algorithm, 618
  • edit graph, 509–511
  • eight queens problem, 254–257, 718
  • Einstein@Home, 566
  • Elements (Euclid), 36
  • embarassingly parallel, 718
  • embarassingly parallel algorithms, 574–576, 620
  • EMST (Euclidean minimum spanning tree), 418–419
  • encipher, 520, 719
  • encrypt, 520, 719
  • End While statement, 4
  • enqueue, 161–162
  • Enqueue method, 147–148
  • entanglement, 719
  • Euclid
    • Elements, 36
  • Euclidean algorithm, 36–37, 608, 719
  • Euclidean minimum spanning tree (EMST), 418–419
  • Euclidean spanning tree, 617
  • Euclid's algorithm, 36–37, 608, 719
  • Euler, Leonhard (mathematician), 485
  • Euler tours, 314–316, 485–488, 719
  • Eulerian cycles, 314–316, 485–488, 719
  • Eulerian network, 485, 719
  • Eulerian paths, 314–316, 485–488, 719
  • Euler's totient function, 535–536, 719
  • Evaluate method, 496
  • evaluating arithmetic expressions, 494–496
  • exact cover, 719
  • exact cover problem, 555
  • exercises
    • algorithm basics, 20–22
    • arrays, 132–134
    • balanced trees, 365–366
    • basic network algorithms, 447–450
    • complexity theory, 558–559
    • cryptography, 540–541
    • decision trees, 398–401
    • distributed algorithms, 591–593
    • hash tables, 222–225
    • interview puzzles, 604–605
    • linked lists, 101–102
    • network algorithms, 489–492
    • numerical algorithms, 68–70
    • recursion, 281–284
    • searching, 208
    • sorting, 198–200
    • string algorithms, 515–517
    • trees, 342–348
  • exhaustive search, 106–107, 202–203, 377–379, 611, 719
  • ExhaustiveSearch method, 378
  • expanded node networks, 444–445
  • exponential functions, 15–16
  • exponentiation, performing, 40–41
  • expression evaluation, 324–326
  • ExpressionNode class, 325–326
  • expressions, 614
  • EXPTIME, 619, 719
  • EXPSPACE, 719
  • extending greatest common divisor (GCD), 38–40
  • ExtendWalk method, 35–36
  • Extensible Markup Language (XML), 295
  • external node, 286, 289, 719
  • external sorting, 191, 611, 719
  • F
  • Facebook interview puzzles group (website), 603
  • factorial function, 16, 228–230, 232, 719
  • fair, 719
  • fair PRNG, 26–29, 608
  • fairness, ensuring, 26–28
  • Fawcett, Joe (author)
    • Beginning XML, 5th Edition, 295
  • feedback vertex set problem, 555
  • Feistel, Horst (cryptographer), 533
  • Feistel cipher, 533–534, 719
  • Fermat liar, 46, 720
  • Fermat primality test, 46
  • Fermat witness, 46, 609, 720
  • Fermat's little theorem, 608–609
  • Fibonacci function, 231–232, 276
  • Fibonacci numbers, 230–232, 720
  • FIFO (first-in-first-out). See queues
  • FIFO list, 720
  • file processing, 575
  • fill percentage, 211, 720
  • find method (Python), 493
  • FindCellBefore algorithm, 75
  • FindColumnBefore method, 123–125, 127, 128
  • finding
    • average, 107–108
    • cells in linked lists, 73–74
    • columns, 122–123
    • greatest common divisor (GCD), 36–40
    • items, 106–107, 336–337, 341–342
    • maximum, 107–108
    • median, 108–109
    • minimum, 107–108
    • mode, 109–112
    • nodes, 306
    • paths, 425–436
    • prime factors, 42–44
    • prime numbers, 44–45
    • rows, 122–123
    • triangles, 480–482
    • zeros, 55–57
  • G
  • game trees, 615–616
  • gaskets, 246–247, 720
  • Gauss, Johann Carl Friedrich (mathematician and physicist), 58
  • Gaussian elimination, 57–62, 609, 721
  • Gaussian elimination algorithm, 61–62
  • GCD. See greatest common divisor (GCD)
  • general and lieutenants problem, 582, 721
  • general networks, 440–441
  • general recursion removal, 277–280, 613
  • general trees, 312–314
  • generalized partition problem, 387–388, 721
  • generating
    • nonuniform distributions, 30–31
    • random values, 23–29
    • values, 24–26
  • generator, 239, 721
  • geometric calculations, 443–444
  • get method, 115
  • GIMPS (Great Internet Mersenne Prime Search), 566
  • Girvan, Michelle (physicist), 483
  • Girvan-Newman algorithm, 483–485, 721
  • GPUs (graphics processing units), 562
  • graph, 406, 721
  • graph isomorphism problem, 555, 721
  • graphical algorithms
  • graphics processing units (GPUs), 562
  • Great Internet Mersenne Prime Search (GIMPS), 566
  • greatest common divisor (GCD)
    • calculating, 36–38
    • defined, 721
    • extending, 38–40
    • finding, 36–40
  • grid computing, 565, 721
  • grids, joining, 566
  • Guthrie, Francis (mathematician), 459
  • H
  • Haidong Wang's interview puzzles (website), 603
  • Haken, Wolfgang (mathematician), 459
  • HAM (Hamiltonian path) problem, 440, 555, 721
  • HAMC (Hamiltonian circuit) problem, 555, 721
  • Hamiltonian, 721
  • Hamiltonian circuit (HAMC) problem, 555, 721
  • Hamiltonian completion problem, 555, 721
  • Hamiltonian cycle problem, 440, 555
  • Hamiltonian path (HAM) problem, 440, 555, 721
  • hardware random number generator (HRNG), 24
  • hash tables
  • HashTable class (C#), 209–210
  • heaps
  • heuristics
    • about, 82
    • decision tree, 381–387
    • defined, 616, 722
    • game tree, 374–375
  • Hierholzer's algorithm, 487–488, 722
  • higher dimensions, 115–118
  • Hilbert, David (mathematician), 241
  • Hilbert curve, 241–242, 722
  • hill climbing, 616, 722
  • hill-climbing heuristic, 385–386
  • How to Ace a Google Interview (website), 603
  • HRNG (hardware random number generator), 24
  • hybrid methods, 84–85
  • I
  • IBM Q System One, 572
  • If-Then-Else statement, 5
  • implementing
    • Heapsort algorithm, 180–181
    • Quicksort algorithm in place, 185–188
    • Quicksort algorithm with stacks, 185
    • round-robin scheduling, 271–273
  • improving paths, 382–384
  • in-degree, 404, 406, 722
  • independent set, 722
  • IndexOf method (C#), 493
  • indirect recursion, 722
  • inductive reasoning, 291, 614
  • initial state, 497, 722
  • initiator, 239, 722
  • inorder traversal, 299–300, 722
  • insert method (Python), 113
  • InsertCell algorithm, 88
  • inserting items, 112–113
  • insertionsort algorithm
  • IntegerCell class (C#), 71–72
  • interchange networks, 445445–, 716
  • internal node, 286, 289, 722
  • interpolation search, 204–205, 722
  • interpolation search algorithm, 611
  • intersecting
    • with intervals, 330–332
    • with points, 329–330
  • Interval class, 328–329
  • interval trees, 326–328, 722
  • IntervalNode class, 329
  • intervals, intersecting with, 330–332
  • interview puzzles
    • about, 595–596, 621
    • answering questions, 598–602
    • asking questions, 597–598
    • exercises, 604–605
    • websites, 603–604
  • Interview Puzzles Dissected: Solving and Understanding Interview Puzzles (Stephens), 604
  • interview websites, 603–604
  • isomorphic, 722
  • iterating, over singly linked lists, 73
  • itertools.combinations method (Python), 474
  • J
  • job shop scheduling, 723
  • job shop scheduling problem, 555
  • joining grids, 566
  • K
  • k-clique, 473, 723
  • Kerbosch, Joep (computer scientist), 475
  • key, 723
  • knapsack problem, 16, 390, 555, 723
  • knight's tour problem, 257–260, 723
  • knowledge trees, 614
  • Koch, Helge von (mathematician), 239
  • Koch curve, 239–241, 723
  • Koch snowflake, 241
  • Kosaraju, Sambasiva Rao (professor), 421
  • Kosaraju's algorithm, 421–422, 723
  • Kosaraju-Sharir algorithm, 421–422, 732
  • L
  • label-correcting shortest path algorithm, 617
  • label-correcting shortest paths, 430–431
  • label-setting algorithm, 617
  • label-setting shortest paths, 426–429
  • Landis, E. M. (researcher), 350
  • last-in-first-out (LIFO). See stack
  • LCM (least common multiple), 69
  • leader election, 587–588, 620
  • LeadsToSolution algorithm, 253
  • leaf node, 286, 289, 290, 723
  • least common ancestor. See lowest common ancestor (LCA)
  • least common multiple (LCM), 69
  • least squares fit, 62–67, 723
  • leaves, 614
  • left-left case, 350–351
  • level, of nodes, 287, 289, 723
  • level-order traversal. See breadth-first traversal
  • LIFO (last-in-first-out). See stacks
  • LIFO lists. See stacks
  • line network, 445–446, 716
  • linear arrays. See one-dimensional arrays
  • linear congruential generator, 24, 723
  • linear least squares fit, 62–64
  • linear probing, 215–217, 724
  • linear search, 106–107, 202–203, 611, 724
  • Link class, 407, 616
  • linked lists
    • about, 71, 609
    • basic concepts, 71–72
    • defined, 724
    • doubly linked list, 79–81
    • exercises, 101–102
    • linked lists with loops, 91–100
    • linked-list algorithms, 86–89
    • multithreaded linked list, 90
    • self-organizing linked list, 82–86
    • singly linked list, 72–79
    • sorted linked list, 81–82
  • linked-list algorithms
    • about, 86
    • copying lists, 86–87
    • sorting with insertionsort algorithm, 87–88
    • sorting with selectionsort algorithm, 88–89
  • linked-list queues, 148
  • linked-list stacks, 136–138
  • links. See branches
  • list retracing, 724
  • list retracing algorithm, 94–95
  • list reversal, 724
  • list reversal algorithm, 95–97
  • lists, 86–87, 248–249
  • livelock, 724
  • logarithmic growth, 614
  • logarithms, 12
  • longest path problem, 556, 724
  • loops
  • Lucas, Edouard (Mathematician), 144
  • M
  • majority voting problem, 205–207, 724
  • MakeSkyline method, 250–251
  • map coloring, 724
  • map coloring algorithms
    • about, 456, 462–463
    • five-coloring, 459–462
    • four-coloring, 459, 720
    • three-coloring, 458–459
    • two-coloring, 456–458
  • Map2DArray method, 106
  • mapping, 612
  • marking cells, 92–93
  • matching, 724
  • matching parentheses, 494–496
  • MatchUp class, 272
  • Math Is Fun (website), 129
  • Math Olympiads (website), 604
  • matrices, 129–131
  • "Matrix" (website), 129
  • maximal cliques, 473, 483, 724
  • maximal flow, 617
  • maximal flow problem, 464–466, 724
  • maximum, finding, 107–108
  • maximum independent set, 724., See also independent set
  • maximum independent set problem, 556
  • maximum leaf spanning tree, 724
  • maximum leaf spanning tree problem, 556
  • mazes, building, 419–420
  • median, finding, 108–109
  • memory requirements, for algorithms, 607
  • MergeRootsWithSameOrder algorithm, 160–161
  • MergeSkylines method, 251
  • mergesort algorithm, 189–191, 197, 576–577, 620, 725
  • mergesort method, 19
  • MergeTrees method, 159–160
  • merging
    • binomial heaps, 156–161
    • binomial trees, 155–156
  • Metaphone algorithm, 513–514, 725
  • method of gradient ascent, 385–386
  • method of gradient descent, 385–386
  • methods
    • AddInterval, 329
    • AddItemToChild, 335–336
    • AddNote, 320
    • append (Python), 113, 136
    • Array.Sort, 18–19
    • Assign, 421, 422, 424, 425
    • Binary-Search, 201
    • CompleteSelfAvoidingWalk, 35–36
    • count, 84
    • defined, 4
    • DeleteEntry, 126, 129
    • Dequeue, 147–148
    • DoSomething, 5
    • DoubleIt, 5
    • DrawRelative, 242, 244–245
    • Enqueue, 147–148
    • Evaluate, 496
    • ExhaustiveSearch, 378
    • ExtendWalk, 35–36
    • find (Python), 493
    • FindColumnBefore, 123–125, 127, 128
    • FindNode, 306
    • FindRowBefore, 124–125, 126–127, 128
    • get, 115
    • hybrid, 84–85
    • IndexOf (C#), 493
    • insert (Python), 113
    • itertools.combinations (Python), 474
    • MakeSkyline, 250–251
    • Map2DArray, 106
    • MergeSkylines, 251
    • mergesort, 19
    • MergeTrees, 159–160
    • ModPow (C#), 41
    • Newton-Raphson, 55, 609, 726
    • Newton's, 55, 609, 726
    • passing, 299
    • polygon, 728
    • pop, 136–137, 728
    • push, 136–137, 729
    • Rearrange, 85–86
    • ReverseList, 97
    • ScheduleRoundRobinOdd, 273
    • set, 115
    • shuffle, 29
    • SierpDown, 244–245
    • SierpLeft, 244–245
    • SierpRight, 244–245
    • SierpUp, 244–245
    • StartExhaustiveSearch, 378
    • swap, 83–84, 733, 735
    • transpose, 83–84, 733, 735
    • TraverseInorder, 300
    • TraversePostorder, 301
    • TraversePreorder, 299
    • Visit, 422
  • mi flow cut, 468–470
  • Microsoft's .NET Framework, 18–19
  • min flow cut, 725
  • min-cut, 468–470
  • minimal flow cut problem, 468–470
  • minimal spanning trees, 417–418, 725
  • minimax, 369–372, 725
  • minimum, finding, 107–108
  • minimum cut, 468–470
  • minimum degree spanning tree, 725
  • minimum degree spanning tree problem, 556
  • minimum equivalent digraph, 438
  • minimum heap property, 154, 725
  • minimum k-cut, 725
  • minimum k-cut problem, 556
  • minimum reductions, 438, 725
  • Mod operator, 4
  • mode, finding, 109–112
  • modeling accuracy, 609
  • ModPow method (C#), 41
  • Monte Carlo integration, 54–55, 725
  • Monte Carlo simulation, 609, 725
  • Moore, Gordon E. (founder of Intel Corporation), 561, 721
  • Moore's law, 561, 725
  • move to front method (MTF), 83, 725
  • MoveMemory function, 18
  • multi-CPU processing, 567
  • multiple recursion, 725
  • multiplicative inverses, 536, 725
  • multithreaded linked lists, 90
  • mutex, 569, 620, 725
  • N
  • N function, 14
  • N! function, 16
  • N log N function, 15, 543–544
  • N2 function, 15
  • natural number, 725
  • neighbors, 403, 406, 725
  • .NET Framework (Microsoft), 18–19, 201
  • network algorithms
  • network cloning, 470–473
  • network coloring, 556, 726
  • network coloring problem, 555
  • network representations, 407–409
  • networks
  • nondeterministic computer, 546
  • nondeterministic finite automaton (NFA), 502–504
  • nonindexed database searches, 575
  • non-self-intersecting walk, 33–34, 608
  • nonuniform distributions, 30–31
  • nonzero lower bounds
    • about, 114
    • higher dimensions, 115–118
    • two dimensions, 114–115
  • Norishige Chiba (computer scientist), 481
  • notation, complexity theory, 544–545
  • NP, 619, 726
  • NP-complete, 548, 619, 726
  • NP-complete problems, 554–556
  • NP-hard, 550–551, 726
  • NPSPACE, 726
  • NTIME(f(n)), 619, 726
  • null transition, 503, 726
  • numeric integration, 47–55, 726
  • numeric quadrature, 47–55, 726
  • numerical algorithms
    • about, 23, 608–609
    • exercises, 68–70
    • finding greatest common divisor (GCD), 36–40
    • finding zeros, 55–57
    • Gaussian elimination, 57–62, 609, 721
    • least square fits, 62–67, 723
    • performing exponentiation, 40–41
    • performing numerical integration, 47–55
    • prime numbers, 42–47
    • randomizing data, 23–36
  • NumPy library (Python), 114
  • O
  • object references, 614
  • observer, 589, 727
  • occtrees, 337, 727
  • odd-cycle problem, 558, 727
  • Odell, Margaret King (developer of Soundex), 511
  • O(N log N) algorithms
  • one-dimensional arrays
    • about, 105, 106
    • defined, 723
    • finding items, 106–107
    • finding median, 108–109
    • finding minimum, maximum, and average, 107–108
    • finding mode, 109–112
    • inserting items, 112–113
    • removing items, 113
  • one-time pad cipher, 530–531, 619, 727
  • open addressing
    • about, 213–214
    • defined, 612, 727
    • double hashing, 219
    • linear probing, 215–217, 724
    • ordered hashing, 219–222, 612
    • pseudorandom probing, 219, 729
    • quadratic probing, 217–218, 729
    • removing items, 214–215
  • P
  • P, 619, 727
  • pairs, 316
  • parallel algorithms, debugging, 620
  • parallelism
    • about, 562
    • deadlock, 571–572, 717
    • distributed computing, 565–567, 718
    • multi-CPU processing, 567
    • quantum computing, 572, 730
    • race conditions, 567–571, 730
    • systolic arrays, 562–565, 734
    • types of, 620
  • parent node
  • parent pointers, 310–311
  • parenthesis matching, 618
  • parse trees, building, 496
  • partial ordering, 453, 727
  • partition problem, 367, 556, 727
  • partitioning, 611
  • passing methods, 299
  • paths
    • about, 404
    • all-pairs shortest, 431–436
    • augmenting, 712
    • defined, 406, 727
    • Eulerian, 314–316, 485–488, 719
    • finding, 425–436
    • improving, 382–384
    • label-correcting shortest, 430–431
    • label-setting shortest, 426–429
  • pattern matching
    • about, 497
    • building DFAs for regular expressions, 500–502
    • deterministic finite automaton (DFA), 497–499
    • nondeterministic finite automaton (NFA), 502–504
  • P-boxes (permutation boxes), 531, 727
  • perfect tree, 287, 289, 727
  • performing
    • exponentiation, 40–41
    • numerical integration, 47–55
  • permutation boxes (P-boxes), 531, 727
  • permutations
    • about, 260
    • counting, 265, 266–267
    • defined, 613, 727
    • with duplicates, 265
    • without duplicates, 266–267
  • petaflop (pflop), 566, 728
  • PGP (Pretty Good Privacy), 537
  • phase king algorithm, 584–585, 728
  • phi function, 535–536, 719
  • Philips, Lawrence, 513
  • phonetic algorithms, 511–514, 618, 728
  • PigeonholeSort algorithm, 193–195, 197, 728
  • plaintext, 520, 728
  • planar, 728
  • points, intersecting with, 329–330
  • Polish notation, 302, 728
  • polygon method, 268, 728
  • polynomial least squares, 728
  • polynomial least squares fit, 64–67
  • polynomial run time, 15, 728
  • polynomials, degree of, 65
  • pop method, 136–137, 728
  • popping objects, 136
  • postorder traversal, 300–301, 728
  • pow function (Python), 41
  • practical considerations, 18–19
  • precalculated values, 608
  • prefix trees, 337–342, 614, 735
  • preorder traversal, 297–299, 728
  • Pretty Good Privacy (PGP), 537
  • primality, testing for, 45–47
  • primary clustering, 216, 728
  • prime factors, finding, 42–44
  • prime numbers
    • defined, 728
    • finding, 44–45
    • working with, 42–47
  • priority inversion, 571, 728
  • priority queues, 151–152, 178, 610, 728
  • private key, 534, 729
  • PRNG (pseudorandom number generator), 24, 25, 26–29, 608, 729
  • probabilistic algorithm, 47, 608, 729
  • probability technique, 599
  • probe sequence, 213, 729
  • problem structure technique, 599
  • procedures, 4
  • programming puzzles, 621
  • prohibitions, 443–446
  • pseudoclassical mechanics, 396–397
  • pseudocode
    • about, 3–6
    • Bron-Kerbosch algorithm, 476–477
    • defined, 607, 729
    • for self-organizing linked lists, 85–86
  • pseudorandom number generator (PRNG), 24, 25, 26–29, 608, 729
  • pseudorandom probing, 219, 729
  • PSPACE, 729
  • public key, 534, 729
  • public key exponent, 535, 729
  • public key modulus, 535, 729
  • public-key encryption, 534–537, 619, 729
  • push method, 136–137, 729
  • pushdown stack. See stack
  • pushing objects, 136
  • puzzle problems, 621
  • Python
    • append method, 113, 136
    • arrays in, 103
    • automatic memory management and, 79
    • dictionary in, 111
    • find method, 493
    • insert method, 113
    • integers on, 82
    • itertools.combinations method, 474
    • NumPy library, 114
    • pop method, 136, 728
    • pow function, 41
    • sorting tools in, 168
  • R
  • race conditions, 567–571, 730
  • random searches, 381–382, 575
  • random self-avoiding walk, 33–34, 608, 730
  • random solution search, 730
  • random values, generating, 23–29
  • random walks
  • randomization technique, 599
  • randomizing
  • Random.org (website), 24
  • random_trees program, 25
  • RandomTrees program, 25
  • range minimum query (RMQ), 730
  • range minimum query problem, 316
  • ray tracing, 574
  • reachable, 730
  • reachable node, 404, 406
  • Rearrange method, 85–86
  • receiver, 730
  • rectangle rule, 48–49, 730
  • recursion
    • about, 227–228, 612–613
    • backtracking algorithms, 252–260
    • basic algorithms, 228–238
    • defined, 730
    • exercises, 281–284
    • factorial function, 228–230
    • Fibonacci numbers, 230–232
    • graphical algorithms, 238–252
    • removal, 273–280
    • rod-cutting problem, 232–235
    • selections and permutations, 260–273
    • Tower of Hanoi, 235–238
  • recursive algorithm, 612
  • recursive calls, 476
  • recursive metrics, 612
  • reduce, 730
  • reductions, 548–550, 619
  • regular expressions
  • relatively prime, 730
  • remaining node key, 339–340
  • removing items, 113, 214–215
  • reporting problem, 551–554, 619, 730
  • residual capacity, 465, 730
  • residual capacity network, 730
  • resizing hash tables, 211
  • resource hierarchy, 578–579, 731
  • Return statement, 4, 10
  • reverse Polish notation, 302, 731
  • ReverseList method, 97
  • Reversi game, 375
  • reversing an array algorithm, 141
  • Reynolds, Craig, 395
  • right rotation, 351
  • right-right case, 351
  • rod-cutting problem, 232–235, 731
  • root node, 286, 289, 731
  • root split, 355, 731
  • roots, 55, 731
  • Rosetta@home, 566
  • round-robin scheduling
    • about, 267–268
    • defined, 731
    • even number of teams, 270
    • implementation, 271–273
    • odd number of teams, 268–270
  • round-robin tournament, 267
  • route ciphers, 525–526
  • route inspection problem. See Chinese postman problem (CPP)
  • routines, 4
  • row/column transposition cipher, 521–523, 731
  • row-major order, 105
  • rows, finding, 122–123
  • RSA algorithm, 534–537, 731
  • RtlMoveMemory function, 18
  • runtime, 163, 303
  • runtime functions, 11–16, 608
  • Russell, Robert C., 511
  • S
  • satisfiability problem (SAT), 391–392, 548, 556, 731
  • S-boxes (substitution boxes), 531, 733
  • ScheduleRoundRobinOdd method, 273
  • scytale, 731
  • searching
    • about, 201–202, 611
    • best-first, 442–443
    • bidirectional, 442
    • binary, 203–204, 713
    • breadth-first search, 714
    • brute-force, 575
    • exercises, 208
    • exhaustive, 106–107, 202–203, 377–379, 611, 719
    • game trees, 368–375
    • general decision trees, 375–392
    • interpolation, 204–205, 722
    • linear, 106–107, 202–203, 611, 724
    • majority voting, 205–207
    • random, 381–382, 575
    • random solution, 730
    • string, 504–508
    • traversals and, 296
  • secondary clustering, 218, 731
  • security through obscurity, 519, 731
  • seed, 24
  • seed clique, 485
  • Select Case statement, 278
  • selections
    • about, 260
    • counting, 254–255
    • defined, 613, 731
    • with duplicates, 262–263
    • with loops, 261–262
    • without duplicates, 264
  • selectionsort algorithm
    • about, 197, 610
    • in arrays, 170–171
    • sorting with, 88–89
  • self-avoiding walks, creating, 33–34
  • self-organizing linked lists, 82–86, 731
  • self-organizing list, 609
  • self-similar fractal, 239, 613, 732
  • sender, in cryptography, 520, 732
  • sentinels, 74–75, 609, 732
  • separation rule, 395
  • set intersection operator, 477
  • set method, 115
  • Set P, 475–476
  • Set R, 475–476
  • Set X, 475–476
  • SETI@home, 566
  • setting values, 125–127
  • “Seven Bridges of Königsberg” problem, 485
  • shape points, 441–442
  • Shor's algorithm, 572
  • shortest path algorithms
    • about, 441
    • best-first search, 442–443
    • bidirectional search, 442
    • early stopping, 442
    • prohibitions, 443–446
    • shape points, 441–442
    • turn penalties, 443–446
  • shortest path tree, 732
  • shuffle method, 29
  • SI (swarm intelligence)
    • about, 392–393
    • ant colony optimization, 393–394
    • bees algorithm, 394, 712
    • defined, 733–734
    • swarm simulation, 394–397, 734
  • sibling nodes, 732
  • siblings, 286, 289
  • SierpDown method, 244–245
  • Sierpiński, Wacław (mathematician), 243, 247
  • Sierpiński curve, 243–246, 732
  • SierpLeft method, 244–245
  • SierpRight method, 244–245
  • SierpUp method, 244–245
  • sieve of Eratosthenes, 44–45, 732
  • simple substitution cipher, 529–530
  • Simpson's rule, 50, 732
  • simulated annealing, 384–385, 732
  • single recursion, 732
  • singly linked list, 72–79
  • skyline problem
    • about, 247
    • defined, 732
    • divide-and-conquer approach, 249–252
    • lists, 248–249
  • snapshot, 588–589, 620, 732
  • snapshot token, 732
  • solutions to exercises
    • algorithm basics, 623–626
    • arrays, 638–648
    • balanced trees, 670–675
    • basic network algorithms, 678–681
    • complexity theory, 692–696
    • cryptography, 689–691
    • decision trees, 675–677
    • distributed algorithms, 697–701
    • hash tables, 655–657
    • interview puzzles, 701–709
    • linked lists, 633–638
    • network algorithms, 681–686
    • numerical algorithms, 626–633
    • queues, 648–650
    • recursion, 658–663
    • searching, 653–655
    • sorting, 650–653
    • stacks, 648–650
    • string algorithms, 686–689
    • trees, 663–669
  • sorted chaining, 612
  • sorted hill climbing, 386–387
  • sorted linked lists, 81–82
  • sorted trees
  • sorting
    • about, 167–168, 610–611
    • exercises, 198–200
    • with insertionsort algorithm, 87–88
    • O(N log N) algorithms, 174–191
    • O(N2) algorithms, 168–174
    • with selectionsort algorithm, 88–89
    • Sub O(N log N) algorithms, 192–197
  • Soundex algorithm, 511–513, 732
  • space-filling curves, 245–246, 732
  • spanning trees
  • sparse arrays
    • about, 121–123
    • defined, 610, 732
    • deleting values, 127–129
    • finding rows/columns, 122–123
    • getting values, 124–125
    • setting values, 125–127
  • spatial trees, 614
  • specialized queues, 151–152
  • specialized tree algorithms
    • about, 322
    • animal game, 322–324
    • building trees, 328–329
    • expression evaluation, 324–326
    • intersecting with intervals, 330–332
    • intersecting with points, 329–330
    • interval trees, 326–328
    • quadtrees, 332–337
    • tries, 337–342
  • speed, of algorithms, 607
  • Sqrt N function, 14
  • stable sort, 733
  • stable sorting algorithm, 191
  • stack algorithms
    • about, 141
    • reversing an array, 141
    • stack insertionsort, 145–146
    • stack selectionsort, 146–147
    • tower of Hanoi, 143–145, 235–238, 735
    • train sorting, 142–143
  • Stack class (C#), 136
  • stack insertionsort algorithm, 145–146
  • stack selectionsort algorithm, 146–147
  • stacks
    • about, 135–136, 230, 610
    • array, 138–139
    • defined, 610, 733
    • double, 139–141, 610
    • implementing Quicksort algorithm with, 185
    • linked-list, 136–138
  • StartExhaustiveSearch method, 378
  • starvation, 571, 733
  • state transition diagram, 498, 733
  • statements
    • End While, 4
    • If-Then-Else, 5
    • Return, 4, 10
    • Select Case, 278
    • Step, 4
  • steering behaviors, 395
  • Step statement, 4
  • Stephens, Rod (author)
    • contact information for, 5
    • Interview Puzzles Dissected: Solving and Understanding Interview Puzzles, 604
  • stride, 215, 733
  • string algorithms
    • about, 493, 618
    • calculating edit distance, 508–511
    • exercises, 515–517
    • matching parentheses, 494–496
    • pattern matching, 497–504
    • phonetic algorithms, 511–514, 618, 728
    • string searching, 504–508
  • string class (C#), 493
  • string searching, 504–508
  • strongly connected, 406, 420, 733
  • strongly connected components
  • Sub O(N log N) algorithms
  • subgraph isomorphism problem, 556, 733
  • subprocedures, 4
  • subroutines, 4
  • subset sum problem, 388, 556, 733
  • substitution boxes (S-boxes), 531, 733
  • substitution ciphers
    • about, 526
    • Caesar substitution cipher, 526–527, 714
    • defined, 733
    • one-time pad cipher, 530–531, 619, 727
    • simple substitution cipher, 529–530
    • Vigenère cipher, 527–529, 736
  • substitution-permutation network, 733
  • substitution-permutation network cipher, 531–533
  • substring matching, 618
  • subtree, 287, 289, 733
  • superposition, 572, 733
  • swap method, 83–84, 733, 735
  • swarm intelligence (SI)
    • about, 392–393
    • ant colony optimization, 393–394
    • bees algorithm, 394, 712
    • defined, 733–734
    • swarm simulation, 394–397, 734
  • swarm intelligence algorithms, 616
  • swarm simulation, 394–397, 734
  • symmetric traversal, 299–300, 722
  • symmetrically threaded tree, 317, 734
  • symmetric-key encryption, 534, 734
  • synchronization, 620
  • systolic arrays, 562–565, 734
  • T
  • tail recursion, 734
  • tail recursion removal, 274–275, 613
  • Takao Nishizeki (computer scientist), 481
  • task parallelism, 567, 734
  • techinterview (website), 603
  • techniques
    • adaptive, 599, 609
    • for algorithms, 607
    • branch and bound, 379–381, 714
    • data structures, 599
    • decision trees, 599
    • probability, 599
    • problem structure, 599
    • randomization, 599
  • 10 famous Microsoft interview puzzles (website), 603
  • 10 Google interview puzzles (website), 603
  • teraflop (tflop), 566, 734
  • testing
    • connectivity, 413–415
    • for primality, 45–47
  • tflop (teraflop), 566
  • thread, 90, 317, 614, 734
  • threaded linked list, 609
  • threaded trees
    • about, 317–318
    • building, 318–320
    • defined, 734
    • using, 320–322
  • 3CNF (Three-term conjunctive normal form), 549, 734
  • 3-node, 354, 711
  • 3-satisfiability problem (3SAT), 392, 549, 556
  • three-coloring algorithm, 458–459
  • three-cycle problem, 734
  • three-partition problem, 556, 734
  • three-satisfiability (3SAT) problem, 556, 734
  • Three-term conjunctive normal form (3CNF), 549, 734
  • Top 5 Microsoft interview questions (website), 603
  • top-down B-trees, 363, 615, 734
  • topological sorting, 451–455, 617, 734
  • tortoise-and-hare algorithm, 98–100, 431, 437, 735
  • totient function, 535–536, 719
  • tower of Hanoi, 143–145, 235–238, 735
  • train sorting algorithm, 142–143
  • transitive closure, 436, 617, 735
  • transitive closure problem, 437–438
  • transitive reduction, 436, 438–441, 617, 735
  • transitivity
    • about, 436
    • transitive closure problem, 437–438
    • transitive reduction, 436, 438–441, 617, 735
  • transpose links, 421, 735
  • transpose method, 83–84, 733, 735
  • transpose network, 421, 735
  • transposition ciphers
    • about, 521
    • column transposition, 523–525
    • defined, 618, 735
    • route ciphers, 525–526
    • row/column transposition, 521–523
  • treesort, 735
  • trial division, 44
  • triangles, finding, 480–482
  • triangular arrays, 118–121, 735
  • tries, 337–342, 614, 735
  • Triple DES (3DES/TDES), 534, 735
  • true random-number generators (TRNGs), 24, 608, 735
  • TSP (traveling salesman problem), 16, 391, 393–394, 556, 735
  • Turing, Alan (mathematician), 545
  • Turing machine, 545–546, 736
  • turn penalties, 443–446
  • two dimensions, 114–115
  • two generals problem, 580–581, 620, 736
  • 2-3 trees
    • about, 354
    • adding values, 355–356
    • defined, 615, 711
    • deleting values, 356–358
  • 2N function, 15–16
  • 2-node, 354, 711
  • two-coloring algorithm, 456–458
  • two-dimensional arrays, 105
  • V
  • value null, 13
  • values
    • deleting, 127–129
    • generating, 24–26
    • getting, 124–125
    • setting, 125–127
  • vehicle routing, 736
  • vehicle routing problem, 556
  • vertex. See nodes
  • vertex coloring, 556, 726
  • vertex coloring problem, 555
  • vertex cover, 736
  • vertex cover problem, 556, 726
  • Vigenère, Blaise de (diplomat), 527
  • Vigenère cipher, 527–529, 736
  • virtual backlink, 736
  • Visit method, 422
  • Visual Basic, automatic memory management and, 79
  • visualizing functions, 16–17
  • W
  • waiter, 579
  • Warnsdorff, H. C. von, 259
  • weakly connected, 406, 736
  • websites
    • A2Z Interviews: puzzles, 604
    • Advanced Encryption Standard (AES), 533
    • Berkeley Open Infrastructure for Network Computing (BOINC), 566
    • “Building a 270* Teraflops Deep Learning Box for Under $10,000,” 566
    • Byzantine Empire, 581
    • CareerCup, 604
    • Cook-Levin theorem, 548
    • CoolInterview puzzles, 604
    • Data Encryption Standard (DES), 534
    • Einstein@Home, 566
    • Euclidean minimum spanning tree (EMST), 419
    • Extensible Markup Language (XML), 295
    • external sorting on tape drives, 191
    • Facebook interview puzzles group, 603
    • Great Internet Mersenne Prime Search (GIMPS), 566
    • Haidong Wang's interview puzzles, 603
    • How to Ace a Google Interview, 603
    • IBM Q System One, 572
    • Math Is Fun, 129
    • Math Olympiads, 604
    • “Matrix,” 129
    • phonetic algorithms, 514
    • Polish notation, 302
    • Pretty Good Privacy (PGP), 537
    • prime factoring, 44
    • quantum computing, 572
    • Random.org, 24
    • reverse Polish notation, 302
    • Reversi game, 375
    • Rosetta@home, 566
    • SETI@home, 566
    • "Seven Bridges of Königsberg" problem, 485
    • tape drives, 191
    • techniterview, 603
    • 10 famous Microsoft interview puzzles, 603
    • 10 Google interview puzzles, 603
    • Top 5 Microsoft interview questions, 603
    • Turing machine, 546
    • URLs, 480
    • Why Brainteasers Don't Belong in Job Interview, 603
  • weights, 404, 406, 736., See also costs
  • wheel factorization, 44
  • While loop, 4, 38, 74, 179, 188, 221, 275, 278, 321
  • “Why Are Manhole Covers Round? A Laboratory Study of Reactions to Puzzle Interviews,” 596
  • Why Brainteasers Don't Belong in Job Interview (website), 603
  • work assignment problem, 467–468, 736
  • X
  • XML (Extensible Markup Language), 295
  • Z
  • zero sum subset problem, 551, 737
  • zeros, finding, 55–57
  • zero-time sort, 565, 737
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.129.20.125