Interview Q&A

Coding

Easy

Balanced Delimiters

Problem Description: Determine if a string contains balanced delimiters.

Example:

(((foo))) => True

((foo)(bar)) => True

(((foo)(bar)) => False

Solution Approach:

1. Create a stack.
2. Iterate through the string.
   • If the current iteration is an opening delimiter, push it onto the stack.
   • If the current iteration is a closing delimiter, pop a value from the stack. Verify that the popped value is the corresponding opening delimiter. Continue iterating through the string if it is, otherwise the delimiters are not balanced
3. After iterating though the string, if the stack is empty, the delimiters are balanced, otherwise the delimiters are not balanced.

First Repeating Character

Problem Description: Find the first repeating character in a string.

Example:

foobarbaz => o

Solution Approach:

1. Create a dictionary
2. Iterate through the string.
   • If the current character is not in the dictionary, add it as a key to the dictionary and initialize its corresponding value to 1.
   • If the current character is in the dictionary, increment its corresponding value.
3. Iterate through the string again.
   • Use the character as a key in the dictionary to find the number of occurrences of that character.
   • If its value in the dictionary is greater than 1, return that character.

Add Reversed Linked Lists

Problem Description: Given two reversed linked lists, each representing one integer, add those two linked lists as if they were actual correct ordered integers and return the result as a reversed linked list.

Medium

Hard

---

Brain Teasers

Easy

Sudoku Sub-Grid

Explain how you would fill in one 3x3 sub-grid in Sudoku algorithmically with each horizontal, vertical, and diagonal adding up to 15.

Example:

a	b	c
d	e	f
g	h	i

Horizontally:

1. a + b + c = 15
2. d + e + f = 15
3. g + h + i = 15

Vertically:

1. a + d + g = 15
2. b + e + h = 15
3. c + f + i = 15

Diagonally:

1. a + e + i = 15
2. g + e + c = 15

Solution:

1. Find all of the possible combinations adding up to 15

1 + 9 + 5, 2 + 8 + 5, 3 + 7 + 5, 4 + 6 + 5

2. Keep track of how many unique combinations each number can be apart of

In the above example, 5 is used 4 times

3. Note how many combinations each square requires

3	2	3
2	4	2
3	2	3

4. Fill in each square according to how many times each number can be used

Since 5 can be used 4 times, it would be placed in the center cell

10x10x10 Rubik's Cube

You have a 10x10x10 Rubik's Cube (composed of 1x1x1 cubes). The outside is painted red. How many cubes are painted red?

Solution:

Do NOT try to count the cubes on the outside. That will be extremely difficult. Instead, count the cubes that are not painted red, the inside cubes. Each direction (x, y, and z) of the inside has 8 cubes (10 total - 2 outside). Therefore, the dimension of all the inner cubes without paint is 8x8x8 = 512. Subtract 512 inner cubes from the total number of cubes (1000 - 512), and your result is 412.

Medium

Three Wise Men Riddle

Three men are placed in a line, facing the same direction. Each of them is randomly given one hat to wear from a collection of 2 black hats and 3 white hats. The first man cannot see anyone's hat. The second man can only see the first man's hat. The third man can see both the first and the second man's hat. None of the men can see their own hat, and they are not allowed to speak to each other. As soon as a man knows his hat color, he will immediately announce it. After some time has passed, the first man declares that he has a white hat. He is correct. How did he know this?

Solution:

1. List out all possible combinations

W	W	W
W	W	B
W	B	W
B	W	W
W	B	B
B	W	B
B	B	W

2. Looking from the perspective of the third man, the last solution can be eliminated because if the first two men were wearing black hats, he would have known his hat was white.

W	W	W
W	W	B
W	B	W
B	W	W
W	B	B
B	W	B

3. If we take the perspective of the second man, we know that between us and the first man, one of us must have a black hat and one of us must have a white; otherwise the third man would have known his hat color. If the first man was wearing a black hat, than our hat must be white, so we would have known our hat color. Therefore, we can eliminate any solution with the first man having a black hat.

W	W	W
W	W	B
W	B	W
W	B	B

4. The only solutions left all have the first man wearing the white hat; therefore, the first man can conclude hat he has the white hat.

Hard

---

Theory/Technology