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