Amazon SDE Internship Interview Experience – 2 DSA Questions
I recently attended an Amazon SDE Internship interview and was asked two DSA questions during the technical round. Sharing them here in case they are useful for others preparing for interviews.
Question 1 – Find the Center of a Star Graph
I was given an undirected graph consisting of n nodes labeled from 1 to n.
A star graph has one center node, and every other node is connected directly to that center.
Given an array of edges, where edges[i] = [u, v] represents an edge between nodes u and v, find the center node.
Example
Input:
edges = [[1,2], [2,3], [4,2]]
Output:
2Key observation
The center node appears in every edge.
Therefore, we only need to look at the first two edges. The node common to both edges must be the center.
For example:
[1, 2]
[2, 3]The common node is 2, so the answer is 2.
Time Complexity: O(1)
Space Complexity: O(1)
Question 2 – Rearrange String
Given a string containing repeated lowercase English characters, rearrange the characters so that no two adjacent characters are equal.
Constraints:
1 <= len(s) <= 10^5
s contains lowercase English lettersExample
Input:
"aabbbcdeefg"
Possible output:
"ababcdegfeb"The exact arrangement can vary as long as no two adjacent characters are the same.
Approach
I initially thought about repeatedly selecting characters based on their frequency.
The standard approach is to use a max heap:
- Count the frequency of each character.
- Put the characters and their frequencies into a max heap.
- At every step, take the most frequent character that is different from the previously placed character.
- Place it in the result and decrease its frequency.
- Put it back into the heap if it still has remaining occurrences.
- If no valid character is available, then the rearrangement is impossible.
This gives:
Time Complexity: O(n log k), where k is the number of distinct characters.
Space Complexity: O(k).
Since the input contains only lowercase English letters, k <= 26.
These were the two DSA questions I encountered in the interview. Sharing them for anyone preparing for SDE internship interviews.
If anyone knows of LeetCode problems that are very similar to these, feel free to share them below.


