256.cool
 0of 0 votes
AnswersI was asked to design a stock ticker system. Stock ticker is simply the shortened name of company and its current stock size. e.g. for Apple  "AAPL" > "115"
 256.cool in United States
He asked me to design a data structure to store incoming stream of stock tickers. Stream can contain same company more than once but all the values of it had to be stored. I used HashMap<String, List<Integer>>. Then he was adding more functionalities to system I don't exactly remember the questions now but one of them was related to calculating some ratio in constant time. Some of the questions were challenging. Report Duplicate  Flag
Bloomberg LP Software Engineer / Developer System Design  0of 0 votes
AnswersGiven a set find its power set. (This question is from CTCI) Interviewer then discussed the complexity of my solution. He asked me to explain him how the complexity is 2^n? As per my solution, I was iterating over an arraylist which contained the set elements so the size of list was getting doubled in every iteration. Hence the complexity (2^0 + 2^1 + 2^2 +.....+2^n1 = 2^n)
 256.cool in United States Report Duplicate  Flag
Bloomberg LP Software Engineer / Developer Algorithm  0of 0 votes
AnswersGiven a string, add some characters to the from of it so that it becomes a palindrome. E.g.1) If input is "abc" then "bcabc" should be returned. 2) input > "ab" output > "bab" 3) input > "a" output > "a"
 256.cool in United States Report Duplicate  Flag
Bloomberg LP Software Engineer / Developer Algorithm  0of 0 votes
AnswersYou are given a binary tree. Each node in the tree is a house and the value of node is the cash present in the house. A thief can rob houses in alternate levels only. If thief decides to rob house at level 0 then he can rob houses in levels 2,4,6... or he can rob houses in levels 1,3,5,7...Find out the maximum possible amount thief can rob.
 256.cool in United States Report Duplicate  Flag
Bloomberg LP Software Engineer / Developer Trees and Graphs
static String getPaliSubString(String str)
{
if(str==null  str.length()<=1)
return str;
int i=0, j=str.length()1;
int st = 1, end = 1;
while(i<j)
{
char charI = str.charAt(i);
char charJ = str.charAt(j);
if(charI==charJ)
{
if(st==1 && end ==1)
{
st = i;
end = j;
}
}
else
{
if(i>0 && str.charAt(i1)==charJ)
{
st = i;
end = j;
}
else if(j<str.length()1 && str.charAt(j+1)==charI)
{
st = i;
end = ++j;
}
else
{
st = 1;
end = 1;
}
}
i++;
j;
}
if(st!=1 && end!=1)
return str.substring(st,end+1);
else
return str.substring(0,1);
}

256.cool
October 18, 2016 Open Chat in New Window
Do it using DP. start with 1 to n dice and m sides. Suppose we have 3 dice with 3 sides. Then we start loop with 1 to 3 for first die we have sums [1,2,3] > just 1 die involved, for second die we get sums like [(1+1),(1+2),(1+3),(2+1),(2+2),...,(3+2),(3+3)] similarly we iterate for 3 die and we get sums as [(1+1+1),(1+1+2),....,(3+3+3)] total m^n sums. Complexity of this solution is O(m*n). We can use hashmap to store sum to reduce space complexity.
 256.cool October 19, 2016