American Express Interview Prep Questions

DSA 4

DSAMedium

A queue is built from two stacks. Enqueue pushes onto stack A. Dequeue pops from stack B, first moving everything from A to B if B is empty. What is the amortised cost per operation?
1. O(n)
2. O(log n)
3. O(1)
4. O(n^2)
Show the answer

C. O(1)

One dequeue can move n elements, but each element is pushed and popped at most twice in its life (once on A, once on B), so n operations cost O(n) in total.

This topic is named in a candidate’s interview report: Tech intern on-campus interview, 2020, on GeeksforGeeks.
DSAHard

Delete as few characters as possible from "aaaabbbb" so that no two letters occur the same number of times. How many deletions are needed?
1. 0
2. 2
3. 1
4. 4
Show the answer

C. 1

a and b both occur 4 times. Deleting one b leaves counts 4 and 3, which are different. The general method sorts the counts and lowers each to the largest unused value below the one before it.

This topic is named in a candidate’s interview report: Tech intern on-campus interview, 2020, on GeeksforGeeks.
DSAMedium

You are given a pointer to a node in a singly linked list, not the last node, but not the head. How do you delete that node?
1. Walk back to the previous node and relink it
2. Set the node pointer to null
3. Copy the next node's data into this node, then unlink and free the next node
4. It cannot be done without the head
Show the answer

C. Copy the next node's data into this node, then unlink and free the next node

You cannot reach the previous node, so you make this node a copy of its successor and remove the successor instead. It does not work for the tail, which has no successor.

This topic is named in a candidate’s interview report: Technology intern on-campus interview, 2023, on GeeksforGeeks.
DSAMedium

To find the k-th largest of n numbers, you scan them while keeping a min-heap of at most k elements. What does this cost, and where is the answer at the end?
1. O(n log n); it is the largest element in the heap
2. O(n log k); it is the smallest element in the heap, at its top
3. O(k log n); it is the last element pushed
4. O(n); it is in the middle of the heap
Show the answer

B. O(n log k); it is the smallest element in the heap, at its top

Each number costs O(log k): push it, and pop the minimum when the heap exceeds k. The heap then holds the k largest numbers, and the smallest of those, at the top, is the k-th largest.

This topic is named in a candidate’s interview report: Technology intern on-campus interview, 2023, on GeeksforGeeks.

Python 1

PythonEasy

What does this print?
```
a, b = 5, 9
a = a + b
b = a - b
a = a - b
print(a, b)
```
1. 5 9
2. 14 5
3. 9 5
4. 9 14
Show the answer

C. 9 5

After a = a + b, a is 14. b = 14 - 9 = 5, the old a. a = 14 - 5 = 9, the old b. The values are swapped without a third variable (in fixed-size integer languages the sum can overflow, which is why XOR swaps are also taught).

This topic is named in a candidate’s interview report: Software engineer on-campus interview, 2021, on GeeksforGeeks.

C and C++ 2

C and C++Medium

Which is true of a C++ reference compared with a pointer?
1. A reference can be null, a pointer cannot
2. A reference must be initialised, cannot later be made to refer to another object and cannot be null; a pointer can do all three
3. Assigning to a reference makes it refer to a different object
4. Members are reached through a reference with ->
Show the answer

B. A reference must be initialised, cannot later be made to refer to another object and cannot be null; a pointer can do all three

A reference is an alias fixed at initialisation; assigning to it assigns to the object it names. A pointer is a separate variable holding an address, which can change or be nullptr, and needs * or -> to use.

This topic is named in a candidate’s interview report: Tech intern on-campus interview, 2020, on GeeksforGeeks.
C and C++Medium

Can a C++ class have several destructors, overloaded on their parameters?
1. Yes, one for each constructor
2. No; a destructor takes no parameters and returns nothing, so a class has exactly one
3. Yes, if they differ in return type
4. Only in classes with virtual functions
Show the answer

B. No; a destructor takes no parameters and returns nothing, so a class has exactly one

Constructors can be overloaded because objects can be created in different ways, but there is only one way to destroy one, so ~ClassName() has no parameters and cannot be overloaded. It can be virtual.

This topic is named in a candidate’s interview report: Software engineer on-campus interview, 2021, on GeeksforGeeks.

DBMS and SQL 1

DBMS and SQLMedium

Students take many courses and each course has many students. How is this stored in a normalised schema?
1. A comma-separated list of course ids in the student table
2. One column per course in the student table
3. A course_id column in student and a student_id column in course
4. A third table enrollment(student_id, course_id), each a foreign key, together forming its primary key
Show the answer

D. A third table enrollment(student_id, course_id), each a foreign key, together forming its primary key

A many-to-many relationship becomes a junction table. Each row records one enrolment, and the composite key stops the same student being enrolled in the same course twice.

This topic is named in a candidate’s interview report: Tech intern on-campus interview, 2020, on GeeksforGeeks.

Aptitude 2

AptitudeMedium

A monkey climbs a 20 ft pole. Each hour it climbs 3 ft and then slips back 2 ft. How many hours does it take to reach the top?
1. 20
2. 17
3. 10
4. 18
Show the answer

D. 18

After 17 hours it is at 17 ft (1 ft net per hour). In the 18th hour it climbs 3 ft to 20 ft and is at the top before it can slip.

This topic is named in a candidate’s interview report: Technology intern interview, 2021, on GeeksforGeeks.
AptitudeMedium

Three switches outside a closed room control three bulbs inside, one each. You may flip switches as you like but enter the room only once. How do you tell which switch controls which bulb?
1. Turn all three on, then enter
2. Turn switch 1 on for a few minutes, turn it off, turn switch 2 on, then enter: the lit bulb is 2, the warm unlit bulb is 1, the cold unlit bulb is 3
3. It cannot be done with one visit
4. Turn switches 1 and 2 on, then enter: the brighter bulb is 1
Show the answer

B. Turn switch 1 on for a few minutes, turn it off, turn switch 2 on, then enter: the lit bulb is 2, the warm unlit bulb is 1, the cold unlit bulb is 3

A bulb has two observable properties, on or off and warm or cold, giving enough states to tell three switches apart in one visit.

This topic is named in a candidate’s interview report: Technology intern interview, 2021, on GeeksforGeeks.

Prep for other employers

All employers

DSA 4

A queue is built from two stacks. Enqueue pushes onto stack A. Dequeue pops from stack B, first moving everything from A to B if B is empty. What is the amortised cost per operation?

Delete as few characters as possible from "aaaabbbb" so that no two letters occur the same number of times. How many deletions are needed?

You are given a pointer to a node in a singly linked list, not the last node, but not the head. How do you delete that node?

To find the k-th largest of n numbers, you scan them while keeping a min-heap of at most k elements. What does this cost, and where is the answer at the end?

Python 1

What does this print?

C and C++ 2

Which is true of a C++ reference compared with a pointer?

Can a C++ class have several destructors, overloaded on their parameters?

DBMS and SQL 1

Students take many courses and each course has many students. How is this stored in a normalised schema?

Aptitude 2

A monkey climbs a 20 ft pole. Each hour it climbs 3 ft and then slips back 2 ft. How many hours does it take to reach the top?

Three switches outside a closed room control three bulbs inside, one each. You may flip switches as you like but enter the room only once. How do you tell which switch controls which bulb?

Prep for other employers