PayPal Interview Prep Questions with Answers

DSA 4

DSAMedium

To group words that are anagrams of each other, such as eat, tea and ate, what makes a good hash map key?
1. The word's length
2. The word itself
3. The first letter of the word
4. The word's letters sorted, such as "aet", or a count of each letter
Show the answer

D. The word's letters sorted, such as "aet", or a count of each letter

Anagrams share the same multiset of letters, so the sorted letters (O(k log k)) or a 26-letter count (O(k)) is identical for all of them. Words with the same key go in the same group.

This topic is named in a candidate’s interview report: SDE-1 and intern on-campus interview, 2021, on GeeksforGeeks.
DSAMedium

Seven people stand in a circle, numbered 1 to 7. Counting starts at person 1 and every second person is removed (2 goes first, then 4, and so on) until one is left. Who survives?
1. 1
2. 3
3. 7
4. 5
Show the answer

C. 7

People leave in the order 2, 4, 6, 1, 5, 3, so 7 is left. This is the Josephus problem: the recurrence J(n) = (J(n - 1) + k) mod n gives the survivor without simulating, and a circular linked list simulates it directly in O(nk).

This topic is named in a candidate’s interview report: SDE-1 on-campus interview, 2021, on GeeksforGeeks.
DSAMedium

Quickselect finds the k-th smallest element of an unsorted array by partitioning around a pivot, as quicksort does, but recursing into one side only. What are its average and worst-case running times?
1. O(n) average, O(n^2) worst
2. O(n log n) average, O(n log n) worst
3. O(log n) average, O(n) worst
4. O(n) average, O(n) worst
Show the answer

A. O(n) average, O(n^2) worst

Each partition is linear and, on average, halves the part still searched: n + n/2 + n/4 + ... = O(n). A bad pivot every time shrinks it by one element only, which gives O(n^2). A heap of size k gives O(n log k) every time, and the median-of-medians pivot makes quickselect linear in the worst case.

This topic is named in a candidate’s interview report: SDE-1 on-campus interview, 2021, on GeeksforGeeks.
DSAMedium

Coins of value 1, 3 and 4 are available in any number. To make 6, a greedy method keeps taking the largest coin that still fits. How many coins does greedy use, and how many does the best answer use?
1. 2 and 2
2. 3 and 3
3. 4 and 2
4. 3 and 2
Show the answer

D. 3 and 2

Greedy takes 4, then 1 and 1: three coins. Two 3s make 6 with two. Greedy is safe for coin sets like 1, 2, 5, 10 but not for every set, so the general minimum-coins problem is solved with dynamic programming: best[a] = 1 + the smallest best[a - c] over every coin c.

This topic is named in a candidate’s interview report: On-campus internship interview, 2015, on GeeksforGeeks.

Java 3

JavaMedium

Which is true of Hashtable compared with HashMap in Java?
1. Hashtable allows one null key; HashMap allows none
2. They are the same class under two names
3. HashMap keeps its keys sorted; Hashtable does not
4. Hashtable's methods are synchronized and it refuses null keys and values; HashMap is not synchronized and allows one null key and null values
Show the answer

D. Hashtable's methods are synchronized and it refuses null keys and values; HashMap is not synchronized and allows one null key and null values

Hashtable is a legacy class from Java 1.0 that locks the whole table on every call and throws NullPointerException on a null key or value. For a map shared between threads today, use ConcurrentHashMap, which also refuses nulls but locks far less.

This topic is named in a candidate’s interview report: On-campus internship interview, 2015, on GeeksforGeeks.
JavaHard

In Java 8 and later, what does a HashMap do when many keys land in the same bucket?
1. It throws an exception once a bucket holds 8 entries
2. It keeps a linked list in the bucket, and once that list grows past 8 entries in a table of at least 64 buckets, it turns the bucket into a red-black tree, so lookups there take O(log n)
3. It picks a new random hash seed and rehashes every key
4. It moves the extra keys into a second HashMap
Show the answer

B. It keeps a linked list in the bucket, and once that list grows past 8 entries in a table of at least 64 buckets, it turns the bucket into a red-black tree, so lookups there take O(log n)

Before Java 8 a bucket was always a list, so many colliding keys made get O(n). Now a crowded bucket becomes a tree (TREEIFY_THRESHOLD 8); in a table smaller than 64 buckets the map resizes instead, and a tree shrinks back to a list at 6 entries. A good hashCode keeps buckets short either way.

This topic is named in a candidate’s interview report: On-campus internship interview, 2015, on GeeksforGeeks.
JavaMedium

A HashMap made with new HashMap<>() has 16 buckets and a load factor of 0.75. Adding distinct keys one at a time, which put makes it grow to 32 buckets?
1. The 12th
2. The 16th
3. The 13th
4. The 17th
Show the answer

C. The 13th

The resize threshold is 16 x 0.75 = 12 entries, and the map doubles as soon as its size goes past it, which is on the 13th put. If you know you will store n entries, new HashMap<>(capacity) with capacity at least n / 0.75 avoids the repeated rehashing.

This topic is named in a candidate’s interview report: On-campus internship interview, 2015, on GeeksforGeeks.

Operating systems 1

Operating systemsMedium

Why is switching between two threads of one process cheaper than switching between two processes?
1. Threads have no registers to save
2. Threads are never scheduled by the OS
3. Processes switch only once a second
4. The threads share one address space, so the page tables stay as they are and the TLB and caches keep their contents
Show the answer

D. The threads share one address space, so the page tables stay as they are and the TLB and caches keep their contents

Both switches save and restore registers and the stack pointer. A process switch also changes the memory map, which flushes or tags the TLB and leaves the caches full of the old process's data. Sharing memory is also why threads need locks around shared data.

This topic is named in a candidate’s interview report: On-campus internship interview, 2015, on GeeksforGeeks.

Web development 1

Web developmentMedium

What does this print?
```
const arr = [10, 1, 3];
arr.sort();
console.log(arr);
```
1. [ 1, 3, 10 ]
2. [ 10, 3, 1 ]
3. [ 1, 10, 3 ]
4. [ 10, 1, 3 ]
Show the answer

C. [ 1, 10, 3 ]

With no compare function, sort turns the elements into strings and compares those, and "10" comes before "3" because "1" comes before "3". For numbers, write arr.sort((a, b) => a - b). sort also changes the array in place.

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

Software engineering 2

Software engineeringEasy

How does an agile process differ from the waterfall model?
1. They are the same process with different names
2. Waterfall runs requirements, design, build, test and release once, in order; agile delivers working software in short iterations and revises requirements as feedback comes in
3. Agile skips testing
4. Waterfall needs no documentation
Show the answer

B. Waterfall runs requirements, design, build, test and release once, in order; agile delivers working software in short iterations and revises requirements as feedback comes in

Waterfall suits fixed, well understood requirements, but a misunderstanding surfaces only at the end. Agile methods such as Scrum release every few weeks so mistakes are caught early. The iterative waterfall adds feedback between phases.

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

In Scrum, who decides the order of the product backlog?
1. The Product Owner
2. The Scrum Master
3. The most senior developer
4. Whoever writes the next story
Show the answer

A. The Product Owner

The Product Owner orders the backlog by value to users and the business. The Scrum Master guides the process and removes blockers; the developers choose how much they can take into a sprint and how to build it.

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

Prep for other employers

All employers

DSA 4

To group words that are anagrams of each other, such as eat, tea and ate, what makes a good hash map key?

Seven people stand in a circle, numbered 1 to 7. Counting starts at person 1 and every second person is removed (2 goes first, then 4, and so on) until one is left. Who survives?

Quickselect finds the k-th smallest element of an unsorted array by partitioning around a pivot, as quicksort does, but recursing into one side only. What are its average and worst-case running times?

Coins of value 1, 3 and 4 are available in any number. To make 6, a greedy method keeps taking the largest coin that still fits. How many coins does greedy use, and how many does the best answer use?

Java 3

Which is true of Hashtable compared with HashMap in Java?

In Java 8 and later, what does a HashMap do when many keys land in the same bucket?

A HashMap made with new HashMap<>() has 16 buckets and a load factor of 0.75. Adding distinct keys one at a time, which put makes it grow to 32 buckets?

Operating systems 1

Why is switching between two threads of one process cheaper than switching between two processes?

Web development 1

What does this print?

Software engineering 2

How does an agile process differ from the waterfall model?

In Scrum, who decides the order of the product backlog?

Prep for other employers