# Archives: Answers

Answer

### What does a typical the microservice architecture look like?

The diagram below shows a typical microservice architecture. Load Balancer: This distributes incoming traffic across multiple backend services. CDN (Content Delivery Network): CDN is a group of geographically distributed servers that hold static content for faster delivery. The clients look for content in CDN first, then progress to backend services. API Gateway: This handles incoming…

### Implement strstr() – return the index of the first occurrence of needle in haystack or -1

O(nm) runtime, O(1) space – Brute force: Difficulty: Easy, Frequency: High Returns the index of the first occurrence of needle in haystack, or –1 if needle is not part of haystack. There are known efficient algorithms such as Rabin-Karp algorithm, KMP algorithm, or the Boyer-Moore algorithm. Since these algorithms are usually studied in an advanced…

### Valid Palindrome: converting uppercase to lowercase and removing non-alphanumeric characters

O(n) runtime, O(1) space: The idea is simple, have two pointers – one at the head while the other one at the tail. Move them towards each other until they meet while skipping non-alphanumeric characters. Consider the case where given string contains only non-alphanumeric characters. This is a valid palindrome because the empty string is…

### Two Sum: Data structure design

add – O(n) runtime, find – O(1) runtime, O(n2) space – Store pair sums in hash table: We could store all possible pair sums into a hash table. The extra space needed is in the order of O(n2). You would also need an extra O(n) space to store the list of added numbers. Each add…

### Two Sum: Input array is sorted

Of course we could still apply the [Hash table] approach, but it costs us O(n) extra space, plus it does not make use of the fact that the input is already sorted. O(n log n) runtime, O(1) space – Binary search: For each element x, we could look up if target – x exists in…

### Two Sum: find two number from array of integers and thats sum equal to target integer

O(n2) runtime, O(1) space – Brute force: The brute force approach is simple. Loop through each element x and find if there is another value that equals to target – x. As finding another value requires looping through the rest of array, its runtime complexity is O(n2). O(n) runtime, O(n) space – Hash table: We…

- 1
- 2