256.cool
BAN USER- 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 | PURGE
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^n-1 = 2^n)
- 256.cool in United States| Report Duplicate | Flag | PURGE
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 | PURGE
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 | PURGE
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(i-1)==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);
}
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