SKJ
BAN USER- 0of 0 votes
AnswersPlease share your thoughts over this designing question (If you need any more info, pls. do let me know):
- SKJ in United States
GIVEN: Let's say we have a popular eCommerce site with lots of sellers and millions of products.
The system has a CatalogManager Service which is being called by various seller platforms to update info (attributes) about seller and it's products. For e.g. Seller can say 'Hey, my brand name has changed to New_Brand', 'Hey, My Product P1 weight has changed to 6kg'. The catalog manager service has it's own datastore and cache in place where it goes and update accordingly. Imagine the sclae of these update requests to be very high as we have thousands of sellers and millions of products and each may have 50-60 attributes which could be chaned. The CatalogManager service is able to handle all these updates smartly.
TO DESIGN:
There are various other back-end services (ShippingService, SearchService) in the system who must me notified about these changes in REAL TIME. For e.g. ShippingService must be notified by CatalogManager that 'Hey, Product P1 of seller S1 weight has changed to 6 kg'. Other example, SearchService must be notified that 'Hey, Seller S1 brand name has changed to New_Brand' so that it can change it's index to be searched.
* Design such a system which can scale & is fault tolerant ensuring all edge cases including one mentioned below:-
* Every back-end service may not be interested in all the events. It may only wish to listen subset of attributes. E.g. ShippingService may only want if product dimension related attributes change. So how will you ensure that only related messages reach to consumer services?
* How will you ensure that event message published by producer service (CatalogManager) reacheed to the related consumer service for sure and in REAL TIME?
* How can you ensure the messages passed to backend services are in sync (in order it's important)
* How to ensure that same event is not messaged twice to the consumers? Although, eventually it will result in same data state but still looking at scale of the events this would be a burden to backend system
How would you design such a system?| Report Duplicate | Flag | PURGE
Software Architect System Design
This solution is O(mn).
private static class AlexState {
int rv = 0;
int cv = 0;
DIR dir = DIR.MINUS_R;
private enum DIR {
MINUS_R(0), PLUS_C(1), PLUS_R(2), MINUS_C(3);
private int val;
private DIR(int val) {
this.val = val;
}
}
}
public static void main(String[] args) {
int rc = 9, cc = 9;
boolean[][] cells = new boolean[rc][cc];
for (int i = 0; i < rc; i++) {
for (int j = 0; j < cc; j++) {
cells[i][j] = false;
}
}
AlexState state = new AlexState();
cells[0][0] = true;
System.out.println(findVisitedCellsCount(cells, rc, cc, state));
}
public static int findVisitedCellsCount(boolean[][] cells, int rc, int cc, AlexState s) {
int cnt = 0;
int vc = 1;
while (cnt < 4) {
cnt++;
switch (s.dir) {
case MINUS_R:
s.dir = AlexState.DIR.PLUS_C;
if (s.cv < cc - 1 && !cells[s.rv][s.cv + 1]) {
cnt = 0;
cells[s.rv][s.cv + 1] = true;
s.cv++;
vc++;
}
break;
case PLUS_C:
s.dir = AlexState.DIR.PLUS_R;
if (s.rv < rc - 1 && !cells[s.rv + 1][s.cv]) {
cnt = 0;
cells[s.rv + 1][s.cv] = true;
s.rv++;
vc++;
}
break;
case PLUS_R:
s.dir = AlexState.DIR.MINUS_C;
if (s.cv > 0 && !cells[s.rv][s.cv - 1]) {
cnt = 0;
cells[s.rv][s.cv - 1] = true;
s.cv--;
vc++;
}
break;
case MINUS_C:
s.dir = AlexState.DIR.MINUS_R;
if (s.rv > 0 && !cells[s.rv - 1][s.cv]) {
cnt = 0;
cells[s.rv - 1][s.cv] = true;
s.rv--;
vc++;
}
break;
}
}
return vc;
}
For e.g. passed string is 'bcd', then
1- 1(a)*25(b-z)*25(a,c-z) plus
2- 1(b)*1(a)*25(b-z) plus
3- 1(b)*1(c)*3(a,b,d) = 653
Similar idea is used here. During, each sstring generation, I have checked whether it's all it's previous chars are bounded or not. By bounded, I mean that the char at current index is same as passed string char at that index. So, if all previous chars are bounded so current char cannot go beyond the passed string char at current index else it can have any 25 chars.
private static int cnt = 0;
public static void main(String[] args) {
String passedString = "bbb";
// input string char array
char[] passedStringCharArray = passedString.toCharArray();
int len = passedString.length();
// used to store currently considered sstring char array
char[] sStringCharArray = new char[l];
countSStrings(passedStringCharArray, sStringCharArray, 0, false);
System.out.println(cnt % 1009);
}
/**
* This function will count all possible sstrings.
*
* @param passedStringCharArray
* @param sStringCharArray
* will hold the sstring being constructed right now
* @param d
* current index of the sstring being constructed
* @param pEqual
* true, when all previous chars are equal to passed strings
* chars at that corresponding index else false
*/
public static void countSStrings(char[] passedStringCharArray,
char[] sStringCharArray, int d, boolean pEqual) {
if (d >= sStringCharArray.length)
return;
boolean meEqual = false;
// Try to construct a string which is sstring and on success increment
// count
for (char i = 'a'; checkLimit(passedStringCharArray, d, i, meEqual); i++) {
sStringCharArray[d] = i;
// if current char at index 0 is equal to passed string char at
// index 0. This means the char at index 1 cannot go beyond passed
// string char at index 1.
if (d == 0 && sStringCharArray[d] == passedStringCharArray[d])
// At index 0, I cannot take chars beyond i
meEqual = true;
// If all my previous chars are bounded i.e. equal to corresponding
// char in passed string array and I am also bounded now
else if (pEqual && sStringCharArray[d] == passedStringCharArray[d])
// I cannot take chars beyond i
meEqual = true;
// checking no two duplicate chars sitting next to each other
if (d > 0 && sStringCharArray[d - 1] == i)
continue;
countSStrings(passedStringCharArray, sStringCharArray, d + 1,
meEqual);
// if sstring is made successfully
if (d == sStringCharArray.length - 1) {
++cnt;
}
}
}
private static boolean checkLimit(char[] sStringCharArray, int d, int i,
boolean meEqual) {
if ((meEqual && i > sStringCharArray[d]) || i > 'z')
return false;
return true;
}
True.
- SKJ January 22, 2015I have updated the question with more points to focus while designing. Let's discuss in more in-depth details about the design of the system