GKalchev
BAN USER- 0of 0 votes
Answersdesign a server architecture for serving Google maps images
- GKalchev in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer System Design
- 3 Answers Microsoft SDE
Hello all,
- GKalchev June 22, 2012
I am looking for a SDE position in Microsoft. I have looked through the jobs at Microsoft Careers but the problem is I do not know where(which team) I would fit. So the real question is: is there any chance to go through the interview process and Microsoft decide for which position I will be the best to suit? How can this happen?
I am also applying at Google but there I am talking with the recruiter for almost two months now and still I am waiting for the interview set up.
Any advice is very much welcome :)| Flag | PURGE
O(1) space and O(n) time solution:
1.) traverse the LL to find the size of all letters(we do not care about the size of the LL).
2.) find the middle charecter MID = n >> 1 - 1.
3.) traverse the LL to find in which node MID character is.
4.) split the node int two parts - 1st part with the characters before mid(included), 2nd with chars after MID.
5.) reverse the second part of the LL (including the 2nd splitted node)
6.) traverse with two pointers 1st from the start, 2nd to the reversed part, untill we hit MID
7.) after 6.) we know if this is palindrom just need to restore the LL if the task require it --> will skip the restoring since it will be easy, just undo what you have done till step 5
We can simply use an array keeping a track of every second. The length of the array for 24 hours = 24 * 60 * 60. So we will have int[] clicksPerSec = new int[86400];
To make it O(1) amortized(since summing) time to find the clicks in last minute/ hour/ day or any query in a range, we can sum the clicks int the array arr[i] += arr[i-1] (note: here we can overflow the integer). So whenever we need to have the clicks for a specific second we return arr[second] - arr[second - 1]. For minutes we return arr[minute * 60] - arr[(minute - 1) * 60], etc..
There is a recursive implementation
1.) get the root - in my case since I use a matrix it will be the most left-bottom Character
2.) recursively go inorder --> left (leftY = pY * 2), childX = pX - 1 then print the curr character then rightY = leftY + 1
Here is a java implementation:
public void printInorderCartesian(Character[][] tree) {
int rootX = tree.length - 1, rootY = 0;
printInorderCartesian(tree, rootX, rootY);
}
private void printInorderCartesian(Character[][] tree, int x, int y) {
int childX = x - 1;
int leftY = parentY << 1;
int rightY = leftY + 1;
if (x >= 0 && y < tree[0].length) {
printInorderCartesian(tree, childX, leftY)
System.out.println(tree[x][y]);
printInorderCartesian(tree, childX, rightY)
}
}
Expected time O(nlogn), worst O(n^2):
take each node(we can take it random to escape worst case complexity n^2) and add it to a tree. While inserting we check if new node won over the current node goes right, else left. The needed result is the inorder traversal of the tree.
Nice solution. But there is something I do not understand:
how do you compare the characters in step 4. I am asking since I can think of only O(n/2)log(n/2) complexity.
e.g. abanavacam
p.s
In non general case: If you have only 26 symbols you can simply use use an array cnt with size = 26 and keep the indexs of the first elements. This will be constant time and your approach will be O(n). But in general case it seems to me like O(nlogn)
yes in a Graph definition of a subgraph (as a tree) is different and is as you did it. But here the idea is simply about the tree. Do you think the interviewer is meaning subGraph(if so he would probably ask the question in the context of a graph). That is why your solution is too complicated for this problem and if you not mention that we are talking about graphs it would be wrong. Otherwise it is an interesting approach but for different question.
thanks for the discussion and good luck :)
Thanks for the answer @algo. I think you are wrong with the terminology of a subtree. Check en.wikipedia.org/wiki/Tree_(data_structure)#Terminology specially last parahraph (emphasize on "ALL of its descendants in T."). So you cannot say that (2,4) is a subtree of the example you gave. If you take 2 as the root of the subtree so the answer would be (2,4,5). Hope we are on the same line here.
- GKalchev October 02, 2012this is a special case O(n). If the max value is close to the arr.length and if we have only positive values. In that private case we can also do count sort, index sort etc. all in O(n) time.
I do not think if there is a variant to do it O(n) in general case.
algos: are you sure about that explanation. I am not familiar with the "uni-value sub-trees" term but still I do not see why in your example you take 1,4,5 as a possible subtrees. Can we take just the root as a "subtree" and cut its leaves? I am asking since according to me a subtree is of a tree T is a tree consisting of a node in T and all of its descendants in T. So according this definition all possible subtrees in your example are 3 - No: 2,3,6. Please explain if I miss something?
- GKalchev October 02, 2012//use 2 Hash<ID, TreeNode> h1 and h2> first(h1) one will have the ID as the key and here we have all the elements, the second(h2) one will have ParentID as key and the elements there will be only the elements that still haven’t been attached to their parent where after all the elements from the file are taken we will iterate to remove the elements from. The structure that will keep the elements in order will be a tree(where the keys will be the Names) structure with a NIL root where we attach all the elements with ParentID = 0. So here is what we do:
1.) we add the NIL node in the h1 with id 0
2.) start traversing nodes from the file
2.1) we check if the parent id is in the h1.
2.1.1) if it exists we add the new node as a child to it
2.1.2) if it DOES NOT exist we add the new element under h2
2.2) we add the new element in the h1.
2.3) check if the element ID exists in h2.
2.3.1) if it exists we add the element from h2 as a child to the new element and remove the element from h2.
3.) finally take from h1 the node with ID = 0(NIL node) as the root and do an inorder traverse of the tree is the answer
public class TreeNode implements Comparable<TreeNode>{
String name;
Integer parentId, Integer id;
Set<TreeNode> children;
public TreeNode (String name, Integer id, Integer parentId) {
this.name = name;
this.children = new TreeSet<TreeNode>();
…....
}
public int compareTo(TreeNode other) {return this.name.comaperTo(other.name);}
}
public class Item {
int parentId, id;
String name;
}
//Implementation
public void printMailBox (Item[] fromFile){
Map<Integer, TreeNode> h1 = new HashMap<Integer, TreeNode>();
Map<Integer, List<TreeNode>> h2 = new HashMap<Integer, List<TreeNode>>();
TreeNode currElement = new TreeNode(null, null, null);
h1.put(0, currElement); //1
//2
for (int i = 0; i < fromFile.length; i++) {
currElement = new TreeNode(fromFile[i].name, fromFile[i].id, fromFile[i].parentId);
//2.1
if (h1.containsKey(currElement.parentId)){
TreeNode parent = h1.get(currElement.parentId);
parent.children.put(currElement);
} else {
if (!h2.containsKey(currElement.parentId))
h2.put(currElement.parentId, new LinkedList<TreeNode>());
h2.get(currElement.parentId).add(currElement);
}
//2.2
h1.put(currElement.id, currElement);
//2.3
if (h2.containsKey(currElement.id)) {
Iterator<TreeNode> iter = h2.get(currElement.id).iterator();
while (iter.hasNext())
currElement.children.put(iter.next());
h2.remove(currElement.id);
}
}
//3. Simple inorter print.
//Implementation skipped
}
Recursion with memoization
//call with uniqueTreesRec(0, arr.length -1, dp)
private int uniqueTreesRec(int N, int startIdx, int endIdx, int[] dp) {
int possibilities = 0;
if (startIdx == endIdx && startIdx >= 0 && &&endIdx < N)
possibilities = 1;
else if (startIdx >= 0 && endIdx < N) {
if (dp[endIdx - startIdx] > 0)
return dp[endIdx - startIdx];
for (int idx = startIdx; idx <= endIdx; idx++) {
int leftNodesCnt = idx - startIdx;
int rightNodesCnt = endIdx - idx;
int leftPoss = dp[leftNodesCnt];
int rightPoss = dp[rightNodesCnt];
if (leftPoss == 0)
leftPoss = uniqueTreesRec(N, startIdx, idx - 1, dp);
if (rightPoss == 0)
rightPoss = uniqueTreesRec(N, idx + 1, endIdx, dp);
possibilities += Mat.max(leftPoss, rightPoss);
}
dp[endIdx - startIdx] = possibilities;
}
return possibilities;
}
DP solution
public int uniqueTreesRec(int N) {
int[] dp = new int[N + 1];
dp[1] = 1;
for (int i = 2; i <= N; i++) {
int ithSum = 0;
for (int j = i - 1; j >= (i >> 1); j--)
ithSum += dp[j] << 1;
//example for 12345 we will have 14+5+2+5+14 = 2*14 + 2*5 + 1*2
if (i & 1 == 0)
dp[i] = ithSum - dp[i>>1];
else
dp[i] = ithSum;
}
return dp[N];
}
DP or recursive solutions (code of each are bellow in the comments). Base state is 1 element has 1 possibility and then for every next element sum possibilities with each root.
Example i.e. lets take [1,2,3]. We have dp[0,1,2,5] (dp[i] = j where i is the number of nodes and j are the combinations count) because 123 can have:
1.) root 1 and 23. So possibilites are dp[3] += Math.max(dp[left.len], dp[right.len]) = Math.max(dp[0], dp[2]) = 2
2.) root 2 and 13. So possibilites are dp[3] += Math.max(dp[left.len], dp[right.len]) = Math.max(dp[1], dp[1]) = 1 ⇒ dp = 2 + 1 = 3
3.) root 2 and 13. So possibilites are dp[3] += Math.max(dp[left.len], dp[right.len]) = Math.max(dp[0], dp[2]) = 2 ⇒ dp = 3 + 2 = 5
Solution O(n) time and space →
1.) sum the elements from left to right in same or other array a[].
2.) in a new array b[] from left to right keep the index of the smallest element.
3.) the reslt is the max(a[i] - a[b[i - 1]])
public void maxSumSubArr(int[] a) {
if (a == null || a.length == 0)
System.out.println(-1);
//1
for (int i = 1; i < a.length; i++)
a[i] += a[i-1];
//2
int[] b = new int[a.length];
for (int i = 1; i < b.length; i++)
if (a[b[i - 1] > a[i] )
b[i] = i;
else
b[i] = b[i - 1];
//3.
int maxSum = a[0];
int idxStart = 0;
int idxEnd = 0;
for (int i = 1; i < a.length; i++)
if (maxSum < a[i] - a[b[i - 1]]) {
maxSum = a[i] - a[b[i - 1]];
idxStart = b[i - 1];
idxEnd = i;
}
//Print results
System.out.format(“Max Array: startIdx is %s, endIdx is %s, sum is %s”, idxStart, idxEnd, maxSum);
}
//O(n) time, O(1) space solution. Just move right (while we have 1s) and down. Keep a track of longest row
public int getLongestRowIdx(int[][] m) {
int longestRowIdx = 0;
int longestClmnIdx = 0;
int i = 0;
int j = 0;
for (int i = 0; i < m.length; i++) {
while (j < m[0].length && m[i][j] == 1)
j++;
if (j - 1 > longestClmnIdx) {
longestRowIdx = i;
longestClmnIdx = j - 1;
}
}
return longestRowIdx;
}
If we convert the problem to: "Find the two non repeated elements....." it will become trivial problem. So here is an idea how to find the third element:
1.) if we XOR all the numbers we will get the bits that are repeated 3 times or Non 3 times (i.e. one time in our case).
2.) so we are looking for the elements that are repeated Non three times and Non even times in the code bellow they I call them "one".
3.) after we have the third number and all we have to do is exclude that number and we have the trivial problem with two non repeated elements.
Here is the Java code for finding the third non-repeted element:
public int getThirdElement(int[] nums) {
int newOne = 0;
int one = 0;
int two = 0;
int three = 0;
int four = 0;
int xorAll = 0;
for (int num : nums) {
xorAll ^= num;
newOne = four & num;
four &= (~newOne);
four |= three & num;
three &= (~four);
three |= two & num;
two &= (~three);
two |= one & num;
//one &= (~two);
one = (~(four | three | two)) & num;
one |= newOne;
}
return getNum(nums, one);
}
private int getNum(int[] nums, int oneRep) {
int result = 0;
int diffBit = oneRep & ~(oneRep - 1);
for (int num : nums)
if ((num & diffBit) > 0)
result ^= num;
return result;
}
(rand(3) -1)*3 + (rand(3) - 1)*1 + 1
Do it as you would generate a number in base 3 number.
Example:
Just for the example lets say rand(3) generates numbers 0,1,2 and we are looking form numbers from 0-8 (rand(9)). In base 3 system the max number with length 2 will be 22 = 2*3^1 + 2*3^0 = 2*3 + 2*1 = 8 (eq1). So we just do generate the number in base 3 and find what it is:
in eq1 we change the numbers: rand(9) = rand(3)*3 + rand(3)*1
so now changing rand(3) return 1-3, and rand(9) must return 1-9
and final equation is: rand(9) = (rand(3) -1)*3 + (rand(3) - 1)*1 + 1
1.) we can check how the elements distribute over a given range
2.) we can check how many times one number is hit and what is the difference between the most hit number and the least hit one.
3.) *Visually check for patterns of each number hits by looking (in the code bellow I would look) the "map".
point 1.) sample Java code:
public static double randPercent() {
int N = 1000;
int[] map = new int[N];
int cnt = 0;
int rand;
for (int i = 0; i < N; i++) {
rand = (int) (Math.random() * N);
map[rand]++;
if (map[rand] == 0)
cnt++;
}
//System.out.format("Result is %s (different numbers) out of %s", cnt, N);
return (double) cnt / N;
}
The 3rd level degree will look like user1-->user2-->user3-->user4. Lets say on average each user has N(on average N would be less than 1000) friends(just to make it more visible). So if we do simple BFS we go O(N^level) --> in our case we need 3rd level so O(n^3) .
We can make it a bit faster to O(n^ceil(level/2)) here by using O(n^floor(level / 2)) space --> in our case O(n^2) time and O(n) space.
Simple idea here is to start BFS from both ends and meet in the middle. In our case:
1.) we start traversing from user1 in depth cail(3/2) = 2
2.) and from user4 in depth floor(3/2) = 1.
So from 2.) we can hash friends of user4 = O(n) space and check for a matching the user found from 1.) in O(n^2)
This approach will work fine up to level 6 where we can improve O(n^6) to O(n^3) time and space. If it goes higher I think will not be a good idea if we use simple hashing.
public int[] plusOne(int[] num) {
int[] result = new int[num.length];
int carry = 1;
for (int i = num.length - 1; i >= 0; i++) {
result[i] = num[i] + carry;
carry = result[i] / 10;
result[i] %= 10;
}
//this will happen very rear -> 1 / (sum(9*10^i)), i = [0, num.length)
if (carry > 0){
int[] oldResult = result;
result = new int[num.length + 1];
System.arraycopy(oldResult, 0, result, 1, oldResult.length);
result[0] = carry;
}
return result;
}
I think the same. Just do not forget to check the three cases with the count of the elements equal to 0 (at least do not devide by 0 check):
1.) cnt = 0 --> just the case you have mentioned
2.) cnt = 1 --> all the elements are 0 except the element == 0
3.) cnt > 1 --> all the elements are 0
If we need to keep the original array R we need two traversals:
1.) count the number of duplicates D
2.) create new array[R - D] and add only the non repeated elements
return the array from 2.)
Here is a sample Java code:
public int[] getUnique(int[] sortedArr) {
if (srotedArr = null || sortedArr.length = 0)
return sortedArr;
int[] clearedArr = new int[sortedArr.length - countDuplicate(sortedArr)];
int insIdx = 0;
Integer lastValue = null;
for (int i = 0; i < sortedArr.length; i++)
if (lastValue == null || lastValue != sortedArr[i])
clearedArr[insIdx++] = sortedArr[i];
lastValue = sortedArr[i];
}
return clearedArr;
}
private int countDuplicate(int[] sortedArr) {
int cnt = 0;
Integer lastValue = null;
for (int i = 0; i < sortedArr.length; i++)
if (lastValue != null && lastValue == sortedArr[i])
cnt++;
else
lastValue = sortedArr[i];
return cnt;
}
- GKalchev August 09, 2012+1
Good solution! The complexity here is n*(4^n) I think. The following lines:
Set<Integer> lefts = eval(values, start, i);
Set<Integer> rights = eval(values, i + 1, end);
in your code you calculate multiple times same values. So keeping the previously calculated values will be a good optimization (memoization using for example start and end as keys) - this is only if you have very very much memory or very short array :)
- GKalchev August 07, 2012in 4b imagine this input [4,2,1,4,3]. Resetting count of the array count[1,1,0,1] at that point will not return the right value, i.e. 1,2,3,4 as the right answer. So here resetting will not be the right idea. Probably keeping the index where this value has been found(lets call it X) and after that traverse from the start index to that to X and int the count[] clearing only the elements in-between will do the job.
- GKalchev August 07, 2012Here is an idea of O(n*logm) amortized time. n = "length of the array" and m = "length of longest continuous sequence".
Here is the array A[]= {4,5,1,5,7,6,8,4,1} (from the example)
The idea is to use a HashMap<Integer, TreeNode> hMap (TreeNodes will be sorted by the index in the array). Here are steps:
1.) start traversing A[i], i = 1..n, and add it in the hMap as follow:
1.1.) if hMap.contains(A[i])
1.1.1) traverse the tree in A[i] and check if this is currently longest result. (here we do versioning of the Tree so if we have already checked the tree previously do not do it again.)
1.1.2) cut the left subtree at A[i]
1.2) else
1.2.1) If hMap.contains(i-1/i+1) merge the Trees A[i - 1] + A[i] + A[i + 1]
1.2.2) else just add the value to hMap
2.) Finally iterate the hMap and do 1.1.1) point
Here is the stack implementation:
public int getDuplCountStack(TreeNode t) {
int count = 0;
Stack<TreeNode> parents = new Stack<TreeNode>();
TreeNode prev = null;
while (t != null || !parents.isEmpty()) {
if (t == null) {
t = parents.pop();
if (prev != null && t.data = prev.data)
count++;
prev = t;
t = t.right;
} else {
parents.push(t);
t = t.left;
}
}
return count;
}
1.) If we have link to the parent is really easy --> just iterate through the successors and check if curr node is duplicate to its successor. We will need O(1) space and O(n) time.
2.) The harder case is when there is no link to the parent node. This can be solved by recursion or using stack for traversing the inOrder of the tree. Both of them are O(n) time and O(logn) space. An example Java code for the recursion is bellow:
public int getDuplCount(TreeNode t, TreeNode prev) {
int count = 0;
if (t != null) {
count += getDuplCount(t.left, prev);
if (prev != null && t.data == prev.data)
count++;
//This will be needed if and Equal node goes on the left. In the example it goes on the right so it is commented here
//if (t.left != null && t.data == t.left.data)
//count++;
count += getDuplCount(t.right, t);
}
return count;
}
The idea here is to use the Grey code.
In Short Grey Code is: The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit (copied from the wiki).
So by description Grey code is exactly what we need - each Grey Code number is representation of one set . So in place of the bits we put the elements from the set.
Here is a sample:
Decimal Binary Gray code
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
Using two stacks(use each one to find the successors of the nodes) the time will be O(n + m) and space will be O(logn + logm)
Here is the java implementation:
//with stack
public void printAscStack(TreeNode t1, TreeNode t2) {
Stack<TreeNode> s1 = new Stack();
Stack<TreeNode> s2 = new Stack();
while (!(t1 == null && t2 == null && s1.isEmpty() && s2.isEmpty)) {
if (t1 != null && t2 != null) {
s1.push(t1);
s2.push(t2);
t1 = t1.left;
t2 = t2.left;
} else if (t1 != null) {
s2.push(t1);
t1 = t1.left;
} else if (t2 != null) {
s2.push(t2);
t2 = t2.left;
} else {
if (!s1.isEmpty() && !s2.isEmpty) {
if (s1.peek.data.compareTo(s2.peek.data) < 0) {
t1 = s1.poll();
System.out.println(t1.data);
t1 = t1.right;
} else {
t2 = s2.poll();
System.out.println(t2.data);
t2 = t2.right;
}
} else if (!s1.isEmpty()) {
t1 = s1.poll();
System.out.println(t1.data);
t1 = t1.right;
} else {
t2 = s2.poll();
System.out.println(t2.data);
t2 = t2.right;
}
}
}
}
Good one. You can do it with a memoization as well. Here is the Java code:
public int getMaxSum(int[][] input, int[][] dp, int i, int j) {
int N = intput.length;
int result = 0;
if (i >= 0 && i < N && j >= 0 && j < N) {
if (dp[i][j] != 0)
result = dp[i][j];
else {
result = Math.max(result, getMaxSum(input,dp, i + 1, j - 1) );
result = Math.max(result, getMaxSum(input,dp, i + 1, j) );
result = Math.max(result, getMaxSum(input,dp, i + 1, j + 1) );
result += input[i][j];
dp[i][j] = result;
}
}
return result;
}
Just using a recursion with memoization so that we do not check the paths again. This will be O(n) time and space. Here is the Java code bellow:
public int maxDistance(int[] arr) {
int[] dp = new int[arr.length];
int result = 0;
for (int i = 0; i < arr.length; i++)
result = Math.max(result, maxDistance(arr, dp, i));
return result;
}
private int maxDistRec(int[] arr, int[] dp, int i) {
int result = 0;
if (dp[i] != 0 || arr[i] == -1)
result = dp[i];
else {
result = maxDistRec(arr, dp, arr[i]) + 1;
dp[i] = result;
}
return result;
}
just saw the "jilong.liao" who has a point.
So if there are negative values we can do max heap of len 3 to keep the min values (just the same logic as the min heap).
Then we remove the first element from the max heap and return Math.Max("maxHeap.poll() * maxHeap.poll() * minHeap.peek()", "minHeap.poll() * minHeap.poll() * minHeap.poll()")
we still keep the Linear time and constant space
Here is a sample Java code:
private final static int NUMS = 3;
public int maxProduct(int[] arr) {
int result = arr.length > 0 ? 1 : 0;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i = 0; i < arr.length && i < NUMS; i++)
pq.add(arr[i]);
for (int i = NUMS; i < arr.length; i++)
if (pq.peek() < arr[i]) {
pq.poll();
pq.add(arr[i]);
}
while (pq.size() > 0)
result *= pq.poll();
return result;
}
traverse the array by checking each day price change. If it is negative this is a lost so we sum to the result. Otherwise we do not. Here is the Java code:
public int maxLoss(int[] a) {
int result = 0;
for (int i = 1; i < a.length; i++)
result += Math.min(0, a[i] - a[i - 1]);
return result;
}
since the question is not clear about if the array is sorted here are the solutions with both options:
1.) if the array is not sorted sort it in O(nlogn) and go to step 2 (if needed O(n) time with O(n) space you can use hashset over key = sum - arr[i] and then traverse the array and search if the value is in the hashset)
2.) if the array is sorted set two pointers in both ends and move the low++ or high-- depending on the sum requested. This is O(n)
here is Java implementation
public void printPair(int[] arr, int sum) {
int low = 0;
int high = arr.length - 1;
while (low < high) {
if (arr[low] + arr[high] == sum)
System.out.format(“(%s, %s) ”, arr[low++], arr[high]);
else if (arr[low] + arr[high] < sum)
low++;
else
high--;
}
}
Repomarcdei, Android Engineer at Abs india pvt. ltd.
I'm Omar. I am working as a Mail carrier in Manning's Cafeterias company. I love to learn and ...
Repnyladsomerville, abc
Want to purchase best quality silencer at affordable price manufactured by top most trusted brand Innovative Arms.
Contact Stonefirearms now!
Great idea! Specially points 3. and 4. !
- GKalchev October 25, 2012