Recursive Algorithm Interview Questions

“How do you find the max depth of a binary tree?”

View Answers (1)

“Implement a Linked List class (for ints only) that supports an append function, which simply appends to the end of the list.

After that, they asked me to implement an appendAt function that takes two ints as arguments, and appends the second argument to the node containing the first argument in the list.

e.g for a list 1 -> 2 -> 3 -> 4 -> 5 , appendAt(3,6) would result in a list: 1 -> 2 -> 3 -> 6 -> 4 -> 5

e.g for a list 1 -> 2 -> 2 -> 3 -> 4 -> 5, appendAt(2,8) would result in: 1 - > 2 -> 8 -> 2 -> 3 -> 4 -> 5 (i.e if the first argument appears more than once in the list, then append the second argument to the first instance of the node containing the first argument)

I gave an iterative solution to the problem. The interviewer then asked me to write it recursively.

This one is really easy, I faltered on it for some reason.”

View Answers (1)

“You are given a Binary Search Tree of ints with duplicate entries. You are guaranteed that if an element has a duplicate entry, it is in the right subtree of that element. Write a function to count the total number of duplicates.

(note, if a tree contains the same element two times, the count of duplicates is 1, not 2)”

View Answers (2)

“Write a function for mutliply(a,b), where a and b are both positive integers, but you can only use the + or - operators.”

View Answers (1)

“Write the function nqueens(num_rows, num_cols, num_queens) -- where num_rows and num_cols is the size of an arbitrary chess board. Function returns "true" if there exists a way to place "num_queens" queens without any queen threatening any other queen, false if it isn't possible.

Efficiency is not a concern.”

View Answers (1)

“Describe a case where you would need to use a cursor to return records from a table.”

Answer Question

“Write a function that raises a number to an exponent in C or Java...”

View Answers (1)

“Implement a power function to raise a double to an int power, including negative powers.”

View Answers (5)

“Write a function Brackets(int n) that prints all combinations of well-formed brackets. For Brackets(3) the output would be

((())) (()()) (())() ()(()) ()()()”

View Answers (10)