Uber prep

  1. In this problem, I was given a 2D Array, with 0s and 1s similar to:
[0,0,0,0,0,0,0,0,0,0
 0,0,0,0,0,0,0,0,0,0
 0,0,0,1,1,1,1,1,1,1
 0,0,0,1,1,1,1,1,1,1
 0,0,0,0,0,0,0,0,0,0]

+ I had to return the height and width that 1s have by scanning this matrix, for example, height in the above example is 2 ( since there are 2 rows of 1) and width is 7, I wrote a simple basic solution which passed all the tests. He asked me to optimize it, so to calculate the width I applied Binary search which also passed all the tests.

System Design Prep

  • https://betterprogramming.pub/an-app-developers-guide-to-mobile-system-design-interviews-74cd552bd963

  • Photo by Christopher Gower on Unsplash

  • Every time you search for a mobile system design resource on the internet, you’re bombarded with lots of articles. But alas, once you open them, you find out that they’re just a sham. They turn out to be articles related to backend system design instead of mobile system design.

  • The lack of mobile-specific system design articles is just astounding!

  • In this article, I will try to tackle the general problems that you might face in a mobile system design interview. I will try to cover as much ground as possible in this article.

  • This article is not a writeup on how to solve an exact system design problem, like building a messaging app like WhatsApp, because there is no single right answer to a system design question, and also, each question might take up an article by itself. But rather, it’s to equip you with a certain set of tools and a mindset to make sure you can navigate your way through the interview.

  • I generally break down the entire interview into four parts:

    1. Problem statement and clarification of features
    1. Proposal of high-level system design
    1. Low-level design decisions
    1. Implementation

  • Things to keep in mind in a mobile system design interview

  • A mobile system design interview is slightly similar to a backend system design interview in terms of code but not so much in terms of solutions.

  • Here’s a list of things that you have to keep in mind when it comes to designing solutions for a mobile app:

    • General API communication design
    • Internet connectivity issues —i.e., the app has bad connectivity or is offline
    • Offline storage
    • Handling app lifecycle callbacks
    • Notifications
    • Security
    • Actual implementation details with respect to code (which I’ve discussed in the Implementation section)

  • Communication: the obvious but not-so-used key

  • The three most important facets of the interview are going to be your clarity into the problem statement, your solutions, and how you effectively communicate your solution to the person conducting your interview. At each step of the process, make sure you’re talking to the interviewer about what you’re thinking. Communication seems like a very obvious key to any interview, but you’ll be shocked to find how many people forget to do this because of whatever reason it might be.

  • Take a few seconds to understand the problem statement in front of you, then think about how you would approach it. It may be the easiest answer you find in your mind and there might be some logical inconsistencies, but go ahead and communicate that with your interviewer. If you are sure about your answer and have thought of the edge cases, then it is definitely a plus, but even if your solution does not solve all the cases, let the interviewer know about the edge case(s) that you couldn’t solve for and think about it, and maybe they will help you out with it or provide you with hints.

  • The right balance to find here is in the time that you’re thinking about the solution before answering. Don’t just randomly answer without thinking, but don’t think too much without giving your interviewer any visibility into your thought process. Think of it like committing your code to Git. You don’t want to keep your code uncommitted for too long, now would you?

  • In any case, the interviewer is going to set their expectations depending on your experience, so if you’re new to the industry, no one is going to expect you to blurt out the right answers every time you open your mouth.

  • Now that we have the communication piece solved, let’s move ahead with the actual process.

  • I’ve encountered both generic and specific types of problem statements while giving these system design interviews. Some example questions are:

    • Design an image downloading library — Kinda specific but still very open ended.
    • Design a networking library — Very open ended.
    • Design a product analytics event tracking system — Again a little open ended.
    • Design a product analytics event tracking system that does X and Y (where X and Y are specific features) — Pretty specific.
    • Design some famous app out there, like Uber/Twitter/Spotify/WhatsApp.

  • And it’s okay even if you haven’t heard of a particular app. The general problem statement will anyway be broken down into tangible requirements, e.g., I want to build a ride-sharing service or an app to manage and download songs.

  • Clarification of the problem statement

  • The first important step in the process is to clarify the problem statement into tangible requirements that you can build. A very generic statement like “design a messaging app or ride-sharing app” will not help you move forward. You will have to ask the interviewer for more specific features, and you can propose the features as well.

  • The goal here is to be able to figure out what are the specific features the interviewer wants you to actually implement. They’re going to check if you’re familiar with the problem at hand and can come up with the core engineering problem associated with the problem statement or not. Remember, it’s always okay to ask them for the specific features they want implemented even if you’re not able to figure it out.

  • The interviewer and you can then finalize certain features that you will definitely have to build and maybe propose some which you might explore if you have time left.

  • For our purposes in this article, let’s take the example of building a messaging app. A few features that might be put on the table to solve for are:

    • Online/offline status of a particular user
    • One-on-one chat feature — Should probably be the most basic feature that has to be implemented since the problem statement is to build a messaging app.
    • Group chat feature
    • Image uploading service

  • Now that you have a few requirements chalked out in the clarification process, you will have to discuss how you are going to solve each feature.

  • Always try to keep a pen and paper handy so that you can jot down your points. If you can do it in your mind, more power to you, but I’ve found writing it down gives you a better mental map of what your thought process looks like. Anyway, write down the steps needed to actually build the feature.

  • That’s easier said than done, so let’s take the example of online/offline status of a particular user on the messaging app and maybe how to implement a general chat between two users. Let’s say that, post the clarification step, you and the interviewer decide on two features.

  • Feature 1 — Let’s say Person A comes online on the app and Person B opens up Person A’s profile on their phone. Person B should be able to see Person A’s status as either online or offline.

  • Feature 2 — The users should be able to send each other messages.

  • Clarify the different cases and their outcomes here with the interviewer and note them down.

  • You can always look at the “things to keep in mind” section for the different cases.

  • For example, what should happen if Person A loses connectivity while chatting? What should happen if the user closes the app or gets a call while they’re online? What should happen if the user sends a message when they do not have an active internet connection? Etc.

  • Discuss the general positive/negative cases and their behaviors first and then move on to the edge cases.

  • Now that you have the requirements in place, you need to actually get down the low-level design aspects of it. Let’s gloss over the “things to keep in mind section” and how your solution is going to morph into something that might actually work.

  • So the flow for the online/offline status feature might look something like this:

  • Person A (mobile app) -> Comes online -> Tells servers that they’re online

  • Person B (mobile app) -> Comes online -> Tells servers that they’re online -> Opens Person A’s profile -> Requests server for Person A’s status -> Server responds that Person A is online.

  • Let’s try and go through the general “things to keep in mind” checklist:

  • Backend API design

  • In the API design section, you’ll have to decide on what kind of communication you expect between the client and the servers, and how you define it.

  • Will the communication be single-sided, which can be satisfied by simple REST APIs? Or will they need some kind of bidirectional communication, which might involve sockets or maybe high-frequency polling or long polling? Figure out what suits your use case based on how important is it and how real-time you want your solution to be.

  • Once you’ve decided on the kind of communication, you’ll need to determine what parameters you actually send in those APIs.

  • For example, for the online/offline feature, we can see that there is a communication between the mobile app and the server when the person comes online and the parameters being passed to it should definitely include the userId so that the server knows who’s online.

  • So you can probably give them a structure like this:

  • POST — /online with parameters as userId or maybe a header which identifies the userId

  • In the case of the chat, you might end up using a socket connection since sending messages need to be real-time.

  • Some interviewers do not look for exact API specifications, but it’s always a good sign if you know the best practices (pagination, batch uploads, etc). I think if you’re able to communicate the bare minimum to your interviewer, you should be good, but anything more than that will definitely give you brownie points. The interviewer will let you know if they do not need any more information on it anyway.

  • Internet connectivity + offline storage

  • These two are generally interconnected with each other, although offline storage can be the solution to a problem statement on its own. Let’s take some examples here again:

  • For the online/offline feature — What if person A comes online, is using the app and then suddenly the device’s internet is cut off? At that point, the interviewer might say that if the internet goes off, the person’s status should say Offline. Now, the only way to solve this problem is that the server needs to infer that the user is not online when their internet connectivity is cut off (because the client cannot communicate with the server anyway). You could suggest a heartbeat mechanism to tackle this problem, then. The client needs to keep hitting the online endpoint every X seconds. If the internet connection is cut off, the server will not receive a call on the online endpoint for that userId, and the server can update that user’s status to offline.

  • The general use case for offline storage is to persist data across app launches. With offline storage, the first thing that you need to figure out is whether your offline storage is going to be file-based or record-based. For example, storing files or images might not require databases. You could probably save them in the device file system.

  • For record-based storage, you’ll have to figure out if you want to use a simple shared preferences (Android) / user defaults (iOS) kind of storage or a database solution. In the case of a database solution, you’ll have to figure out the table structure and the columns that the table will hold. You’ll need to figure out the data types for them, as well, and how you’re going to be querying your data.

  • For example, in the case of sending messages, the interviewer might pose a requirement that the user should be able to send messages even if there is no internet connection. This definitely calls for a record-based solution. In this case, one solution could be that you store the messages sent when the device is not connected to the internet in your persistent storage with a boolean variable which represents the status of whether that particular message was synced with the servers or not. The structure might look something like this:

  • Again, that variable could be a boolean or it could be a string that represents a few finite states the message can have, like SENT , READ, and UNSYNCED; it would all depend on the requirement.

  • Now when the connection comes back, you can sync all the un-synced messages to your server by querying for all messages in your DB that have syncStatus as false and sending them over to your server.

  • Notifications

  • These might involve both local notifications and remote push notifications. Be careful about using remote notifications as your answer as a solution to a particular question because they are dependent on both the internet connection of the user and whether the user has given the app permission to receive push notifications.

  • You could always fall back to silent push notifications for your syncs in case the solution demands it (but then again, you still have to take care of the case where there is no internet connection). Your solution can then involve some kind of polling mechanism in combination with app lifecycle callbacks, which brings me to my next section.

  • App lifecycle handling

  • App lifecycle method handling is required for you to react to changes in the app lifecycle (duh!). It is especially required when you want to optimize for data sync between your app and the server.

  • For example, you might want to sync when the app comes to the foreground, or you might want to sync only when the user is in the background, instead of doing multiple syncs when the app is in the foreground.

  • This also involves a little bit of overlap with your offline storage sometimes, when you want to deal with sync issues when the user terminates the app (and does not just push it to the background).

  • Security

  • This will involve talking about things like whether you want to store personal identity information or some critical information on the device or not. If you want to, you’ll probably have to get into discussions on how to store it securely, what different authentication mechanisms you might have to implement to store such data, and what kind of encryption mechanisms you might use.

  • This section is a beast by itself. This is the portion where you might have to give specific implementation details of your low-level design. The scalability problem on apps is not related to the number of users using the app since it’s mostly just one person interacting with their app on their phone in the actual world. The scalability issues here are related to writing code in a modular and sustainable way.

  • The usual focus on this part of the interview is going to be how you design your internal framework. You should focus on what your Class Diagrams are going to look like and the APIs each class is going to expose.

  • Now in the context of the Class Diagrams and the APIs and their inner working the things to take care of here are:

    • Re-usability of code — Try to break down your code into more reusable components. Figure out the kind of design patterns that you might use to implement the different blocks of your solution.
    • User Friendly APIs — And I don’t mean backend APIs over here. I’m talking about the functions and variables that you might expose. They need to be user-friendly and configurable to the extent that the caller of the API can take decisions on “what” they want easily but your APIs shouldn’t usually expect the caller to take decisions on “how” they want it to be done. That should be decided by your code based on whatever parameters you can use to determine the best approach to tackle the problem.
    • Architectural and state management decisions — What, according to you, might be a good architecture for the scale of features that you’re implementing (e.g., MVC or MVVM) and also a good state management solution for your codebase (e.g., Redux)?
    • Communication between the different components within your app — Will there be one-on-one communication using a delegation pattern or will the communication have to be implemented using some kind of broadcast mechanism?
    • Multi-threading, and how you would implement that — For example, with questions that involve multiple parallel downloads/uploads, you might end up with discussions around this.
    • Caching and cache eviction policies —Discussions around this will come up when you need to download heavy assets from your servers and probably show them with minimal effect on the smoothness of your app. They might come up for different reasons as well, but this is a very common use case when cache comes up. Do not confuse this with offline storage.
    • Throttling and debouncing — Do you have to call your backend API services multiple times? Is your interviewer not happy with the fact that the frequency of these API calls is too damn high?! Start thinking about how you can reduce that frequency. Usually, throttling/debouncing helps in such scenarios. You can also fall back to timers or app lifecycle state observing to figure out what the best time to call such APIs would be.
    • Unit Testing — Make sure the APIs that you decide on are easily unit testable.

  • I hope I’ve given you a general idea about the directions a system design interview can take. But to be very honest, these questions are so generic and the requirements can be shaped in so many different ways that you might never end up using the same solution for two similar-sounding requirements.

  • These discussions are meant to be open-ended, and the biggest suggestion I can give to you is to practice. How do you do that? Just pick up an app and figure out how they might be implementing a particular feature. It can be as simple as how to implement liking a post on your Instagram feed or how live location sharing works in WhatsApp. Think about the implementation of these features with the general constraints we’ve talked about, like loss of connectivity/offline mode, etc., in mind.

  • It also helps to look at different open source frameworks that are available to help you write better APIs. Look at the kind of configurations they expose through their APIs and their general API structure. Look at the inner workings of these libraries to get an idea about the low-level implementation details as well (eg: the design patterns they use, how they manage threading, how they manage offline scenarios etc.).

  • What that will do is help you prepare for these requirements that might be given to you. It might be difficult to answer questions, especially if they’re the kind you’re encountering for the first time. Practice writing your solutions down since you need to be able to communicate your solutions properly.

  • Lastly, I guess you should have fun while appearing for the system design rounds (again, easier said than done). You should already be equipped with some of the general tools required to solve your question, based on this article (hopefully).

    • OODesign — a website to learn about object-oriented design patterns
    • SOLID Principles
    • Caches and cache eviction
    • Database solutions for apps (e.g., CoreData for iOS and Room for Android probably)
    • Heartbeats and silent notifications
    • Push notifications
    • Broadcast and delegation pattern
    • Threading on iOS and Android (whichever platform you’re giving your interview for)
    • App lifecycle methods