Software Engineer, Chrome

Google

Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are: Players take turns placing characters into empty squares ''. The first player A always places 'X' characters, while the second player B always places 'O' characters. 'X' and 'O' characters are always placed into empty squares, never on filled ones. The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal. The game also ends if all squares are non-empty. No more moves can be played if the game is over. Given a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on gridrowi. return the winner of the game if it exists (A or B). In case the game ends in a draw return Draw. If there are still movements to play return Pending. You can assume that moves is valid (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first. For example: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] Output: A moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] Output: B moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]] Output: Draw

Google

Let's design a simplified distributed key-value store. Assume we need to handle a high volume of read and write requests. The key-value store should support the following operations: get(key): Retrieves the value associated with the given key. put(key, value): Stores the value associated with the given key. Here are some specific considerations for the design: Scalability: The system should be able to scale horizontally to handle increasing amounts of data and traffic. Consider how data will be distributed across multiple servers. Consistency: Discuss the consistency model you would implement. Would you choose strong consistency or eventual consistency? What are the trade-offs? Provide a rationale for your choice. Elaborate on how your design ensures that reads return the most up-to-date data (or how it handles potential inconsistencies, if any). Fault Tolerance: How would the system handle server failures? Describe the mechanisms you would implement to ensure data durability and availability in the face of node failures. Explain the role of replication and how it impacts consistency. Data Partitioning: Describe your data partitioning strategy. Consider using techniques like consistent hashing or range-based partitioning. Explain how your chosen strategy affects load balancing and data locality. Provide a concrete example of how keys would be mapped to specific servers in your design. Caching: Where would you incorporate caching in your system to improve read performance? Discuss different caching strategies (e.g., client-side caching, server-side caching) and their implications. Walk me through the architectural components of your key-value store, including the roles of different servers, the communication protocols used, and the data flow for get and put operations. Explain any potential bottlenecks and how you would address them. For example, if consistent hashing is used, how do you handle nodes being added or removed from the cluster?

Google

Tell me about a time you had to work with a signed contract. Describe the situation, your role, and the outcome. What were the key clauses or provisions that were most relevant to the situation? What challenges, if any, did you face in interpreting or adhering to the contract terms? How did you ensure that your actions were in compliance with the contract, and what steps did you take to mitigate potential risks or disputes? For example, consider a scenario where you were managing a project with a vendor, and the contract outlined specific deliverables, timelines, and payment terms. A conflict arose when the vendor failed to meet a critical deadline, potentially impacting the project's overall timeline and budget. How did you leverage the contract to address the issue, protect your company's interests, and find a resolution that was fair to both parties? Or, imagine you were involved in a negotiation where the other party wanted to change certain terms after the contract was signed. How did you handle the situation, ensuring that any modifications were properly documented and agreed upon by all parties involved? What did you learn from this experience, and how has it influenced your approach to working with contracts in subsequent projects or situations?