Software Development Engineer II, Advertising Products and Tech

Amazon

Given a graph represented as an adjacency list, write a function to perform a Depth-First Search (DFS) traversal starting from a given node. The function should print each visited node. Also, provide an example graph and demonstrate how your function would traverse it. Explain the time and space complexity of your solution. For example, consider the following graph: { 0: [1, 2], 1: [2], 2: [0, 3], 3: [3] } If we start the DFS traversal from node 2, the expected output would be: 2, 0, 1, 3 (or another valid DFS traversal order). Your function should: Take the graph (adjacency list) and a starting node as input. Implement DFS traversal. Print each visited node. Correctly handle cycles to avoid infinite loops. Analyze and state the time and space complexity of your implementation.

Amazon

Let's design a Twitter-like service. Consider the following: Core Functionality: How would you implement the ability for users to post tweets, follow other users, and view a timeline of tweets from the users they follow? Data Model: What database schema would you use to store tweets, user information, and follower relationships? Consider scalability and efficiency for reads and writes. Scalability: How would you handle a large number of users and tweets? Discuss strategies for sharding, caching, and load balancing. Real-time Updates: How would you ensure that users see new tweets in their timeline in near real-time? Consider using technologies like WebSockets or Server-Sent Events. Search: How would you implement a search feature that allows users to find tweets containing specific keywords or hashtags? Think about indexing strategies and search algorithms. Rate Limiting: How would you prevent abuse and ensure fair usage of the service? Describe your approach to rate limiting API requests. Example Scenario: Imagine a user, Alice, follows 1,000 other users, including Bob. Bob posts a tweet. Explain how that tweet would propagate to Alice's timeline, considering potential performance bottlenecks. Technology Stack: What technologies (programming languages, frameworks, databases, etc.) would you choose and why?

Amazon

Tell me about your work experience and current project.