Interview Questions

$8\mathrm{.}1$ Triple Step: A child is running up a staircase with n steps and can hop either $1$ step, $2$ steps, or $3$ steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Hints:#$152,$#$178,$ #$217,$#$237,$#$262,$ #$359$

$134$

Cracking the Coding Interview, $6$th Edition

Chapter $8|$ Recursion and Dynamic Programming

$8\mathrm{.}2$ Robot in a Grid: Imagine a robot sitting on the upper left comer of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are "off limits$"$ such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

Hints: #$331,$ #$360,$#$388$

$8\mathrm{.}3$ Magic Index: A magic index in an array $A[0$dotsn$-1]$ is defined to be an index such that $A[i]=$ i$.$ Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A$.$

FOLLOW UP

What if the values are not distinct?

Hints:#$170,$ #$204,$ #$240,$#$286,$ #$340$

$8\mathrm{.}4$ Power Set: Write a method to return all subsets of a set.

Hints: #$273,$ #$290,$ #$338,$ #$354,$ #$373$

pg $396$

$q,$ pg $348$

$8\mathrm{.}5$ Recursive Multiply: Write a recursive function to multiply two positive integers without using the $*$ operator. You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.

Hints:#$166,$ #$203,$ #$227,$ #$234,$ #$246,$ #$280$

pq $350$

$8\mathrm{.}6$ Towers of Hanoi: In the classic problem of the Towers of Hanoi, you have $3$ towers and $N$ disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom $($i$.$e$.,$ each disk sits on top of an even larger one$).$ You have the following constraints:

$(1)$ Only one disk can be moved at a time.

$(2)$ A disk is slid off the top of one tower onto another tower.

$(3)$ A disk cannot be placed on top of a smaller disk.

Write a program to move the disks from the first tower to the last using stacks.

Hints: #$144,$ #$224,$ #$250,$#$272,$ #$318$

$q,$ pg $353$

$8\mathrm{.}7$ Permutations without Dups: Write a method to compute all permutations of a string of unique characters.

Hints: #$150,$ #$185,$ #$200,$ #$267,$ #$278,$ #$309,$ #$335,$ #$356$

$q,$ pg $355$

$8\mathrm{.}8$ Permutations with Dups: Write a method to compute all permutations of a string whose characters are not necessarily unique. The list of permutations should not have duplicates.

Hints: #$161,$ #$190,$ #$222,$ #$255$

pg $357$

Chapter $8$ Recursion and Dynamic Programming

$8\mathrm{.}9$ Parens: Implement an algorithm to print all valid $($e$.$g$.,$ properly opened and closed$)$ combinations of $n$ pairs of parentheses.

EXAMPLE

Input: $3$

Output: $((())),(()()),(())(),()(()),()()$

Hints: #$138,$ #$174,$ #$187,$ #$209,$ #$243,$ #$265,$ #$295$

CrackingTheCodingInterview.com $|6|$ th Edition

$135$