Landing a job at Amazon as a software developer is a dream for many. The interview process is rigorous, often including challenging coding tests. Platforms like Career Cup are known for compiling interview questions from top tech companies, including Amazon. While the actual interview experience is designed to assess your problem-solving approach, understanding common question types can significantly boost your preparation.
My recent experience, although not directly leading to a formal offer, involved a coding challenge that sparked my interest in these types of interview questions. It made me reflect on the coding problems often found on platforms like Career Cup, and how they relate to real-world software development interviews, especially at companies like Amazon.
While my personal interviews haven’t mirrored the exact format of question banks, I recognize the value in practicing these problems to sharpen critical thinking, data structure knowledge, and coding fluency – skills highly valued in companies like Amazon. Therefore, I’ve decided to tackle some classic examples from Career Cup, questions purportedly asked in real interviews, including those from Amazon, and share my approach.
It’s important to note that the aim of these questions isn’t always about finding the “right answer” memorized from a study guide. Companies like Amazon are looking for candidates who can think on their feet, adapt to unexpected problems, and demonstrate a strong foundation in computer science principles. In fact, mimicking pre-prepared answers might be counterproductive. Amazon, like other tech leaders, likely prefers candidates who can demonstrate original thought and problem-solving agility.
However, familiarity with common question formats is undeniably helpful. So, let’s dive into some of the initial questions from Career Cup – skipping a few less directly relevant ones – and explore potential solutions. These questions, while not requiring advanced computer science PhD-level knowledge, do demand logical reasoning, understanding of basic data structures, and proficiency in a programming language.
Here are a few questions as presented on Career Cup, followed by my interpretation and solutions, drawing upon experience across languages like Go, Perl, Lisp, Java, PHP, JavaScript, and years in the IT industry.
1. From Amazon.com: Find if all the leaf nodes are at the same level in a binary tree. Recursive and non-recursive approach?
Let’s break down this classic binary tree problem. We need to determine if all leaf nodes in a given binary tree reside at the same depth. Think of a family tree analogy to visualize a binary tree.
Beatles
/
/
Alive Not Alive
/ /
/ /
Paul Ringo John GeorgeIn computer science terms, a tree is a structure of nodes, each potentially linking to other nodes. A binary tree specifically has each node linking to at most two child nodes. A “leaf” node is one with no children.
In our Beatles example, Paul, Ringo, John, and George are leaf nodes if we consider “Beatles” as the root. The question asks if all these “leaves” are at the same “level” or depth in the tree.
While libraries exist for tree manipulation in most languages, for interview scenarios, demonstrating fundamental understanding by building from basic structures is often preferred. Let’s use Go to illustrate. We can define a node (Person in this case) as a structure:
type Person struct {
name string
mom *Person
dad *Person
}Adding to the tree is straightforward:
func (p *Person) addParent(name string, mom bool) {
parent := Person{name: name}
if mom {
p.mom = &parent
} else {
p.dad = &parent
}
}Now, let’s consider the example tree:
func main() {
root := Person{name: "Self"}
root.addParent("Mom", true)
root.addParent("Dad", false)
root.mom.addParent("Maternal Grandma", true)
root.mom.addParent("Maternal Grandpa", false)
// Tree structure:
// Self
// /
// Mom Dad
// /
// Grams Gramps
}In this tree, “Dad,” “Grams,” and “Gramps” are leaves, but they are at different depths relative to “Self” as the root. The question requires us to programmatically verify if all leaves are at the same depth. We can approach this recursively and non-recursively.
Recursive Approach
The recursive approach involves traversing the tree. We’ll use a global variable depth to store the depth of the first encountered leaf. As we traverse, if we find a leaf at a different depth, we return false.
package main
import (
"fmt"
)
type Person struct {
name string
mom *Person
dad *Person
}
var depth int
func main() {
root := Person{name: "Self"}
root.addParent("Mom", true)
root.addParent("Dad", false)
root.mom.addParent("Maternal Grandma", true)
root.mom.addParent("Maternal Grandpa", false)
fmt.Println(checkDepths(&root, 0)) // Check from 'Self'
fmt.Println(checkDepths(root.mom, 0)) // Check from 'Mom'
}
func (p *Person) addParent(name string, mom bool) {
parent := Person{name: name}
if mom {
p.mom = &parent
} else {
p.dad = &parent
}
}
func checkDepths(p *Person, d int) bool {
if p == nil {
return true // Base case: null node is considered balanced
}
if d == 0 {
depth = -1 // Initialize depth for the first leaf
}
if p.mom == nil && p.dad == nil { // Leaf node
if depth == -1 {
depth = d // Set depth on first leaf
}
return d == depth // Check if current depth matches the first leaf's depth
}
d++ // Increment depth for non-leaf nodes
return checkDepths(p.mom, d) && checkDepths(p.dad, d) // Recurse on children
}
Non-Recursive Approach
Alternatively, we can represent a binary tree using an array. The index in the array implies the node’s position in the tree.
0
/
/
1 2
/ /
3 4 5 6
/
7 8We can iterate through the array and use mathematical relationships between indices to check for leaf nodes. A node at index n is a leaf if it’s not empty but its children at indices 2n+1 and 2n+2 are empty (or out of bounds).
Here’s the Go code for the non-recursive approach using an array representation:
package main
import (
"fmt"
"math"
)
var people []string
func main() {
people = make([]string, 1, 126) // Initialize slice
self := 0
people[self] = "Self"
mom := addParent("Mom", self, true)
dad := addParent("Dad", self, false)
addParent("Maternal Grandma", mom, true)
addParent("Maternal Grandpa", mom, false)
fmt.Println(checkDepths()) // Before adding paternal grandparents (false)
addParent("Paternal Grandma", dad, true)
addParent("Paternal Grandpa", dad, false)
fmt.Println(checkDepths()) // After adding paternal grandparents (true)
}
func addParent(name string, parentOf int, mom bool) int {
index := parentOf*2 + 1
if !mom {
index++
}
if index >= len(people) { // Expand slice if needed
people = append(people, make([]string, index-len(people)+1)...)
}
people[index] = name
return index
}
func checkDepths() bool {
lastIdx := float64(len(people) - 1)
lastRow := int(math.Log2(lastIdx))
l := int(math.Pow(2, float64(lastRow))) - 1 // Index of first element in last row
for n := 0; n < l; n++ {
if !isEmpty(n) && (isEmpty(2*n+1) && isEmpty(2*n+2)) {
return false // Found a leaf node before the last row
}
}
return true // No leaves found before the last row
}
func isEmpty(index int) bool {
if index >= len(people) {
return true
}
return people[index] == ""
}
2. From Cadence Inc: Given a positive integer “N” and an array of numbers ranging from 0-9 (say array name is arr). Print all numbers from 0 to N which include any number from “arr”. Example: i/p: N=20 arr={2,3} o/p: 2,3,12,13,20
This question asks us to filter numbers from 0 to N based on whether they contain any digits from a given array. For example, with digits [2, 3] and N=20, we need to output numbers like 2, 3, 12, 13, and 20 because they contain either ‘2’ or ‘3’.
Regular expressions are an elegant and efficient way to solve this. We can construct a regex pattern from the digit array and then test each number from 0 to N against this pattern.
Here’s a JavaScript solution using regular expressions:
function matches(N, arr) {
var m = [];
var re = new RegExp('[' + arr.join('') + ']'); // Create regex like /[23]/
for (var n = 0; n <= N; n++) {
if (re.test(String(n))) { // Test if number (converted to string) matches regex
m.push(n);
}
}
return m;
}
console.log(matches(20, [2, 3])); // Output: [2, 3, 12, 13, 20]And the concise Perl equivalent:
perl -le '$N=shift; $re=join("", @ARGV); print for grep {/[$re]/} 0..$N' 20 2 33. From Facebook: We are given a set of integers with repeated occurrences of elements. For Example, S={1,2,2}. We need to print the power set of S ensuring that the repeated elements of the power set are printed only once. For the above S, the power set will be {NULL, {1}, {2}, {2}, {1,2}, {1,2}, {2,2}, {1,2,2}}. So, as per the question requirements, we need to print {NULL, {1}, {2}, {1,2}, {2,2}, {1,2,2}}
The power set of a set S is the set of all possible subsets of S, including the empty set and S itself. For S = {1, 2, 2}, the initial power set includes duplicates because of the repeated ‘2’. We need to generate the power set and then remove duplicate subsets.
Lisp, particularly Emacs Lisp, is well-suited for power set generation due to its list manipulation capabilities.
(require 'cl)
(defun powerset (s)
(sort (delete-dups (reduce #'(lambda (one two)
(append (mapcar #'(lambda (i) (cons two i)) one) one))
(sort s #'>)
:initial-value '(nil)))
#'(lambda (a b) (< (length a) (length b)))))
(print (powerset '(1 2 2))) ;; Output: (nil (1) (2) (1 2) (2 2) (1 2 2))This Lisp code leverages functional programming concepts. The core logic uses reduce, append, mapcar, and cons to build the power set iteratively. It starts with an initial set containing only nil (empty set). For each element in the input set s, it generates new subsets by adding the element to each existing subset and then combines these with the original subsets. Finally, delete-dups removes duplicate subsets, and sort arranges them by length.
For a more conventional approach, consider JavaScript using binary counting. Each subset can be represented by a binary number. If the j-th bit of the binary number is 1, include the j-th element of the original set in the subset.
function powerSet(arr) {
var ps = {}; // Power set hash to avoid duplicates
for (var n = 0; n < (1 << arr.length); n++) { // Iterate through all possible subsets (2^length)
var tmp = [];
for (var f = 0; f < arr.length; f++) {
if ((n >> f) % 2 == 1) { // Check if f-th bit is set
tmp.push(arr[f]);
}
}
ps[tmp.sort().join(',')] = 1; // Use sorted subset as key to handle duplicates
}
var res = Object.keys(ps).sort(cmp); // Get unique subsets and sort
return res;
function cmp(a, b) { // Custom sort function for subset length
return a.length - b.length;
}
}
console.log(powerSet([1, 2, 2])); // Output: ["", "1", "2", "1,2", "2,2", "1,2,2"]4. Also from Facebook: Write a function which returns the square root of a given number up to a precision of 0.0001. Only arithmetic operations like addition, subtraction, division, and multiplication are allowed.
This question restricts us to basic arithmetic operations to calculate a square root, ruling out built-in square root functions. One method is the Babylonian method or Newton-Raphson method, an iterative approach. However, the question hints at a more fundamental, digit-by-digit calculation similar to long division.
The Wikipedia article on square root algorithms describes a “Decimal (base 10)” method akin to long division. This method involves iteratively determining digits of the square root. Let’s implement this in PHP:
<?php
function sqrt_manual($number, $precision = 4) {
$integer_part = floor($number);
$decimal_part = $number - $integer_part;
$result = "";
// Integer part
$a = 0;
$b = 0;
$integer_part *= 100;
while ($integer_part > 0) {
$x = 0;
while (($a + $x + 1) * ($x + 1) <= $integer_part) {
$x++;
}
$result .= $x;
$integer_part -= ($a + $x) * $x;
$a = ($a + $x + $x) * 10;
}
// Decimal part
if ($precision > 0) {
$result .= ".";
for ($i = 0; $i < $precision; $i++) {
$decimal_part *= 100;
$integer_part = floor($decimal_part);
$decimal_part -= $integer_part;
$x = 0;
while (($a + $x + 1) * ($x + 1) <= $integer_part) {
$x++;
}
$result .= $x;
$integer_part -= ($a + $x) * $x;
$a = ($a + $x + $x) * 10;
}
}
return floatval($result);
}
echo sqrt_manual(1800, 4) . "n"; // Output: 42.4264
echo sqrt_manual(43046721, 4) . "n"; // Output: 6561
echo sqrt_manual(2, 4) . "n"; // Output: 1.4142
?>This PHP code implements the digit-by-digit square root algorithm. It processes the integer and decimal parts separately. The core logic involves finding the largest digit x at each step such that (a + x + 1) * (x + 1) is less than or equal to the remaining part of the number, where a is a value built up from previous digits.
5. From Goldman Sachs: A standard chess knight is sitting at position a1 on an N x N chessboard. What is the minimum number of moves it will take to reach the diagonally opposite corner? P.S. – If it were an 8 x 8 chessboard, the final destination for the knight would be h8.
This is a critical thinking puzzle related to graph traversal and optimal paths. We need to find the minimum knight moves from one corner to the opposite corner of an N x N chessboard.
For smaller boards, we can deduce the optimal moves manually. For example, on a 4×4 board, it takes 2 moves. On a 3×3 board, it becomes more complex due to board size constraints; it actually requires 4 moves.
The optimal move count tends to follow a pattern, often staying constant for a few board sizes and then incrementing. Here’s a pattern observed for board sizes 3 to 19:
Board Edge length: 3, Optimal move count: 4
Board Edge length: 4, Optimal move count: 2
Board Edge length: 5, Optimal move count: 4
Board Edge length: 6, Optimal move count: 4
Board Edge length: 7, Optimal move count: 4
Board Edge length: 8, Optimal move count: 6
Board Edge length: 9, Optimal move count: 6
Board Edge length: 10, Optimal move count: 6
Board Edge length: 11, Optimal move count: 8
Board Edge length: 12, Optimal move count: 8
Board Edge length: 13, Optimal move count: 8
Board Edge length: 14, Optimal move count: 10
Board Edge length: 15, Optimal move count: 10
Board Edge length: 16, Optimal move count: 10
Board Edge length: 17, Optimal move count: 12
Board Edge length: 18, Optimal move count: 12
Board Edge length: 19, Optimal move count: 12Based on this pattern, we can implement a Java function to calculate the optimal move count:
package cea.demos;
public class KnightMoves {
private KnightMoves() {
}
public static int getOptimalMoveNum(int size) throws Exception {
if (size < 1) {
throw new Exception("Invalid board size");
}
if (size == 3) {
return 4;
}
int baseMoves = (size + 1) / 3;
int moveCount = baseMoves * 2;
return moveCount;
}
public static void main(String[] args) {
for (int size = 3; size <= 19; size++) {
try {
System.out.println("Board Edge length: " + size + ", Optimal move count: " + getOptimalMoveNum(size));
} catch (Exception e) {
System.out.println("Error for size " + size + ": " + e.getMessage());
}
}
}
}This Java code encapsulates the logic for calculating the optimal knight moves. It handles the special case of a 3×3 board and then uses a formula derived from the observed pattern for larger boards.
These examples illustrate the type of coding and problem-solving questions you might encounter in interviews, particularly those related to companies like Amazon and often discussed on platforms like Career Cup. Practicing these, understanding the underlying concepts, and being able to articulate your thought process are key to interview success.
Enjoy!
