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
Solution: O(n) time and excluding the result space + O(1) space if there are no duplicates (if there are duplicates we can move them to the end of the array and use extra HashMap to count the duplicates)
Here is the java code for nonDuplicate version (can be easyly modified for duplicates) :
public int[] getFirstElements(int[] arr, int k) {
int[] result = new int[k];
int currK = 0;
for (int i = 0; i < arr.length && currK < k; i++)
if (arr[i] != 0)
result[currk++] = arr[i];
return result
}
//O(n) time
private void sortArr(int[] arr) {
for (int i = 0; i < arr.length; i++)
while (arr[i] != i  arr[i] != 0)
swap(arr, arr[i], i);
}

GKalchev
June 23, 2012 If there are no repeated nodes and nodes in the tree has a link to the parent the Eugene solution is just perfect (+1 from me).
Still if the tree has no link to the parent or the tree can have repeated nodes we have to traverse all the possible combinations. Here is the java code for that
public boolean isIsotropicBT(TreeNode t1, TreeNode t2) {
boolean result = false;
if (t1 ==null && t2 == null)
result = true;
else if (t1 != null && t2 != null && t1.data == t2.data) {
result = isIsotropicBT(t1.left, t2.left) && isIsotropicBT(t1.right, t2.right);
result = isIsotropicBT(t1.left, t2.right) && isIsotropicBT(t1.right, t2.left);
}
return result;
}

GKalchev
June 23, 2012 I can think of 3 solutions:
1.) use augmented interval three  O(nlogn) build time, O(logn) insert and search
2.) sort the sets by lower bound of the interval O(nlogn). Take the high bound of each element and do a binary search for next or equal lower bound element O(nlogn) => Total O(nlogn)
3.) if you know the interval is complete (not sparse) and the difference between max and min elements is small we can count the ranges in array (for every interval we increment the count[i], when finished we check where count[i] > 1 and this is the result)  O(sum(ranges) + (highest  lowest))
this is a O(nlogn) solution. It is like the usual DP solution just keep the smallest element in the specified idx(order) in the DP[]. So instead of checking all the elements in dp we just do binary search if the element is smaller than the last one or increment the size if it is bigger. here is the code bellow:
public int LIS(int[] arr) {
int[] dp = new int[arr.length];
dp[0] = Integer.MIN_VALUE;
int size = 1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < dp[0])
dp[0] = arr[i];
else if (arr[i] > dp[size  1])
dp[size++] = arr[i];
else {
int k = binSearchNextOrEqual(dp, arr[i]);
dp[k] = arr[i];
}
}
return size;
}

GKalchev
June 21, 2012 Here is the Java implementation. Here is in short what it does :
1.) doing preorder traversel
2.) keep if the node is on the most left or right side
3.) print nodes if they are end node or are most left or right node
public void printOutSideBoundries(TreeNode root) {
printOutSideBoundries(root, true, true);
}
private void printOutSideBoundries(TreeNode node, boolean left, boolean right) {
if (node != null) {
if (node.left == null  node.right == null  left)
System.out.format(“%s, ”, node.data);
printOutSideBoundries(node.left, left, false);
printOutSideBoundries(node.right, false, right);
if (right && !(node.left == null  node.right == null  left))
System.out.format(“%s, ”, node.data);
}
}

GKalchev
June 21, 2012 Here is a O(logn) time and O(1) space
public void changeRoot(TreeNode newRoot) {
//the standard method remove node in BST
removeNode(newRoot);
//check root will be on the left or right side from the newRoot
if (this.root.compareTo(newRoot) < 0) //root stays on left
newRoot.leftChild = root;
else
newRoot.rightChild = root;
this.root.parent = newRoot;
this.root = newRoot;
}

GKalchev
June 14, 2012 Here is a java code that generate it:
private static void printCombinations(int n, String currResult, int startI) {
if (n == 0)
System.out.println(currResult);
else if (n > 0) {
for (int i = startI; i > 0; i= 2)
printCombinations(n  i, currResult + i
+ (n  i == 0 ? "" : " + "), i);
}
}
public static void printCombinations(int n) {
int startI = n;
if (startI % 2 == 0)
startI;
printCombinations(n, "", startI);
}

GKalchev
June 07, 2012 My solution would be:
1.) use an array or hashtable or tree with the prime number + count.
2.) each number of n! can be represented by prime numbers so add count the prime numbers used in 1.
3.) iterate from the structure in 1.) and multiply
3.1) here you can optimize a little  shift left when there is multiplication of 2 instead of multiply
Here is a Java implementation:
public TreeNode preOrderSpecial(TreeNode root) {
TreeNode currNode = root;
while (currNode != null) {
if (currNode.left != null) {
TreeNode mostRight = getMostRightNode(currNode);
mostRight.right = currNode.right;
currNode.right = mostRight;
currNode.left = null;
}
currNode = currNode.right;
}
return root;
}
protected TreeNode getMostRightNode(TreeNode t) {
TreeNode result = t;
while (result.right != null)
result = result.right;
return result;
}

GKalchev
June 01, 2012 Here is another solution (P = parent, R = right, L = left):
1.) you traverse the tree and when you see a node P with left Node just put that node on the right side  there you link P.R to the most right node from the L (L.R.R)
2.) continue this untill there are no left nodes. Here is a picture of the trees:
//
4
/ \
2 5
/ \ \
1 3 6
//
4
2
1 3
5
6
//
4
2
1
3
5
6

GKalchev
June 01, 2012 // Complexity  O(k logk) time O(k) space
//a[] → 9 7 5 2 1 0 1 5
//b[] → 11 2 0 4 7
//Using PriorityQueue > take the best element and add its neighbours
//i.e(a,b): add(9, 11),
//poll(9,11), add(9,2), add(7,11)
//poll(7,11), add(7,2), add(5,11)
//poll(5,11), add(5,2), add(2,11)
//etc....
here is the code:
public int selectLargestSum(int[] a, int[] b, int k) {
int resultSum = 1;
int currK = 0;
PriorityQueue<Item> q = new PriorityQueue<Item>(11, Collections.reverseOrder());
int idxA = 0;
int idxB = 0;
addItem(q, a, b, idxA, idxB);
Item qItem = null;
while (!q.isEmpty()) {
currK++;
qItem = q.poll();
if (currK == k) {
resultSum = qItem.value;
break;
} else {
addItem(q, a, b, qItem.idxA + 1, qItem.idxB);
addItem(q, a, b, qItem.idxA, qItem.idxB + 1);
}
}
return resultSum;
}
protected void addItem(PriorityQueue<Item> q, int[] a, int[] b, int idxA, int idxB) {
if (idxA < a.length && idxB < b.length())
q.add(new Item(a[idxA] + b[idxB], idxA, idxB));
}
protected class Item implements Comparable<Item> {
int value;
int idxA;
int idxB;
protected Item(int value, int idxA, int idxB) {
this.value = value;
this.idxA = idxA;
this.idxB = idxB;
}
@Override
public int compareTo(Item x) {
return this.value  x.value;
}
}

GKalchev
June 01, 2012 I do not think this would be absolutely equal possibility for all numbers :
for the
a = 4*rand_0_or_1() + 2*rand_0_or_1() + rand_0_or_1())==0
ypu have:
num > possibility
1 > 1/2
2 > 1/2
3(1 + 2) > 1/2 + 1/2 = 1/4
4 > 1/2
etc...
probably the best way here is to find least common multiple of 5 and 7 = 35 and have s = sum(rand5()) > 7 times(LCM/5) and return s%7
//Find(print) all numbers with same popcount number
public void getNums(int popCount) {
getNums(popCount, 32, 0);
}
private void getNums(int popCount, int maxLen, int num) {
if (popCount == 0)
System.out.format("%s, ", num);
else
for (int i = popCount  1; i < maxLen; i++) {
int mask = 1 << i;
num = mask;
getNums(popCount  1, i, num);
num ^= mask;
}
}

GKalchev
May 28, 2012 // O(n) time O(1) space
//move a window as soon as it is equal stop.
// If it is greater move left pointer ++
// if it is lower move right pointer ++
public int[] findSubArray(int[] arr, int value) {
int[] result = null;
if (arr != null && value >= 0) {
int i = 0;
int j = 0;
int sum = 0;
boolean hasResult = false;
boolean jChanged = true;
boolean iChanged = false;
while (j < arr.length) {
if (jChanged) {
sum += arr[j];
jChanged = false;
}
if (iChanged) {
sum = arr[i];
iChanged = false;
}
if (sum == value) {
hasResult = true;
break;
} else if ( sum < value) {
j++;
jChanged = true;;
} else {
if(i == j) {
j++;
jChanged = true;
}
i++;
iChanged = true;
}
}
if (hasResult)
result = Arrays.copyOfRange(arr, i, j + 1);
}
return result;
}

GKalchev
May 04, 2012 I am not sure what are the numbers you have added. I assume these are the possible cuts. So what is the length of the log? Can you explain in more details what you mean.
How I see it for example the Len of the log is lets say 5 and I keep your cuts in 1,2,3,4. So still the greedy approach works  always cut middle(closest to middle) so that we get lowest price:
cutpoint  price (len)
2  5
1  2
3  3
4  2
Total Price 12.
Can you give me a better one?
Here is a Java solution with O(n) time, O(logn) space
public int maxDiff(TreeNode root, RefInt maxDiff) {
int depth = 0;
if ( root != null) {
int leftD = maxDiff(root.left, maxDiff);
int rightD = maxDiff(root.right, maxDiff);
int currDiff =lefD + rightD;
depth = Math.max(leftD, rightD) + 1;
if (maxDiff.myInt < currDiff)
maxDiff.myInt = currDiff;
}
return depth;
}
public class RefInt{
public int myInt;
}

GKalchev
April 25, 2012 Here is a Java sample with recursion without reversing:
public ListNode addLists(ListNode l1, ListNode l2) {
ListNode result = null;
int l1Len = lsitLen(l1);
int l2Len = lsitLen(l2);
int diff = Math.abs(l1Len  l2Len);
if (l1Len > l2Len) {
addLists(l1, l2, diff);
result l1;
}
else{
addLists(l2, l1, diff);
result l2;
}
return result;
}
//return carry
private int addLists(ListNode l1, ListNode l2, int diff) {
int carry = 0;
if (l1 != null && l2 != null) {
if (diff == 0) {
carry = addList(l1.right, l2.right, diff);
l1.data += l2.data;
} else {
carry = addList(l1.right, l2, diff  1);
l1.data += carry;
carry = l1.data / 10;
l1.data %= 10;
}
return carry;
}
private int listLen(ListNode node) {
int result = 0;
while (node != null) {
node= node.right;
result ++;
}
return result;
}

GKalchev
April 25, 2012 // idx[](i) 0 1 2 3 4 5 6 7
// container[] = 0 1,3,5,6,25
// dp[] 0 1 2 3 2...
// mapC[] 0 1 1 3 3...
// dp[i] = min(dp[i], dp[i  container[j]] + 1)
public ArrayList<Integer> getMinSteps(int[] containers, int value) {
int[] dp = new int[value + 1];
//here we keep the container to extrakt from idx(=value)
int mapC = new int[value + 1];
for (int i = 1; i < dp.length; i++) {
for (int c = 0; c < containers.length; c++) {
if (value  container[c] >=0 && (dp[value] == 0  dp[value] > dp[value  container[c]] + 1)) {
dp[value] = dp[value  container[c]] + 1;
mapC[value] = container[c];
}
}
}
ArrayList<Integer> result = new ArrayListI<<Integer>();
while (value > 0) {
int container = mapC[value];
result.add(container);
value=container;
}
}

GKalchev
April 25, 2012 //merge two BST into a balanced tree time O(n+m) space O(1)
//12345678
// 5
// 3 7
// 2 4 6 8
// 1
public static class TreeNode {
TreeNode left;
TreeNode right;
int data;
}
public TreeNode mergeTrees(TreeNode rootA, TreeNode rootB) {
TreeNode sortedListA = treeToList(rootA, null);
TreeNode sortedListB = treeToList(rootB, null);
int[] refSize = new int[] {0}; // cheat for reference
TreeNode mergedLists = mergeList(sortedListA, sortedListB, refSize);
return sortedListToBST(new TreeNode[] {mergedLists}, 0, refSize[0]);
}
//return balanced BST
private TreeNode sortedListToBST(TreeNode[] refSortedList, int startIdx, int endIdx) {
TreeNode root = null;
if (startIdx < endIdx) {
int midIdx = (startIdx + endIdx) >> 1;
TreeNode left = sortedListToBST(refSortedList, startIdx, midIdx);
root = refSortedList[0];
root.left = left;
refSortedList[0] = refSortedList[0].right;
root.right = sortedListToBST(refSortedList, midIdx, endIdx);
}
return root;
}
private TreeNode treeToList(TreeNode tree, TreeNode head) {
if (tree == null)
return head;
TreeNode left = treeToList(tree.left, head);
tree.left = left;
return treeToList(tree.right, tree);
}
private TreeNode mergeList(TreeNode listA, TreeNode listB, int[] size) {
TreeNode result = null;
while (listA != null  listB != null) {
size[0]++;
if (listA == null) {
result = addNodeToList(result, listB);
listB = nextNode(listB, true);
} else if (listB == null) {
result = addNodeToList(result, listA);
listA = nextNode(listA, true);
} else {
if (listA.data > listB.data) {
result = addNodeToList(result, listA);
listA = nextNode(listA, true);
} else {
result = addNodeToList(result, listB);
listB = nextNode(listB, true);
}
}
}
return result;
}
private TreeNode addNodeToList(TreeNode list, TreeNode newNode) {
if (list == null)
return newNode;
newNode.right = list.right;
list.right = newNode;
return list;
}
private TreeNode nextNode(TreeNode list, boolean unlink) {
TreeNode result = list.left;
if (unlink)
list.left = null;
return result;
}

GKalchev
March 28, 2012 This can be done in O(n) time and O(1) space. Since we have "more than a half" of the candidates we take the politicions in pairs. To explain it clearly I would use array A[] of n elements which only use equal() and an KeyValueEntry  here the key is the polition and value is int (count) of the politiotions. So what we do:
1.) for each A we check if the key in KeyValueEntry
1.1.) if they match count++ the value (KeyValueEntry ).
1.2.) if the KeyValueEntry is empty or the count == 0 we change the element with the new one and count = 1
1.3) if the KeyValueEntry has count > 0 we change the element with "count  1"
2.) as soon as there are no more elements in A[] we know that the element left in the KeyValueEntry is the majority one since they have "more than a half".
I think that is it. If I miss something please write a comment :)
A solution with O(n + m) time and O(1) space would be iterating through node successors on each tree and compare them node by node. Here is the Java code bellow:
public void printAsc(TreeNode aRoot, TreeNode bRoot) {
TreeNode nextA = minNode(aRoot);
TreeNode nextB = minNode(bRoot);
//Iterate node by node on each tree
while (nextA != null  nextB != null) {
if (nextA != null && nextB != null) {
if (nextA.data.compareTo(nextB.data) < 0) {
nextA = nextPrint(nextA);
else
nextB = nextPrint(nextB);
}
else if (nextA != null)
nextA = nextPrint(nextA);
else
nextB = nextPrint(nextB);
}
}
private TreeNode nextPrint(TreeNode n) {
System.out.println(n.data);
return successor(n);
}
private TreeNode successor(TreeNode n) {
if (n.right != null)
n = minNode(n.right);
else {
TreeNode child = n;
TreeNode p = child.parent;
while(p != null && child == p.right) {
child = p;
p = child.parent;
}
n = p;
}
return n;
}
private TreeNode minNode(TreeNode node) {
while (node.left != null)
node = node.left;
return node;
}

GKalchev
March 26, 2012 @anony.. the second question is related to the first one.
3 numbers can sum to 0 under the following conditions
1. A[a] == A[b], c== 0 exist
2. A[a] == (A[b]+A[c]) exist
3. 0, 0, 0
so the so the 1 and 3 are easy to be checked. and for 2 you have already the sums a = c+b
bellow is the java implementation
public ArrayList<Integer> findRepetedElements(int[] arr, int M) {
ArrayList<Integer> result = new ArrayList<Integer>();
TreeMap<Integer, Integer> tm = new TreeMap<Integer, Integer>();
int minCount = (int) Math.ceil(((double) arr.length) / M);
for (int i = 0; i < arr.length; i++)
add(tm, arr[i], M);
// find count of elements left in the tree
Iterator<Entry<Integer, Integer>> iter = tm.entrySet().iterator();
Entry<Integer, Integer> e;
int value;
int currCount;
while (iter.hasNext()) {
currCount = 0;
e = iter.next();
value = e.getValue();
for (int i = 0; i < arr.length; i++)
if (arr[i] == value)
currCount++;
if (currCount >= minCount)
result.add(value);
}
return result;
}
private void add(TreeMap<Integer, Integer> tm, Integer key, int maxSize) {
Integer mpValue = tm.get(key);
if (mpValue == null)
tm.put(key, 1);
else
tm.put(key, mpValue + 1);
if (tm.size() == maxSize)
clearRow(tm);
}
private void clearRow(TreeMap<Integer, Integer> tm) {
Iterator<Entry<Integer, Integer>> iter = tm.entrySet().iterator();
Entry<Integer, Integer> e;
int value;
while (iter.hasNext()) {
e = iter.next();
value = e.getValue();
if (value == 1)
iter.remove();
else
e.setValue(value  1);
}
}

GKalchev
March 15, 2012 lets take an array A[1...P] (P > N).
We make an array with the runs arr[1.. P] R where all the elements from single run (except the last one which goes in the next sequence) are colored the same (have same number).
(All the sub arrays bellow are marked just with indexes)
Follow L Rule: So lets split the array to a sub arrays that follow the L rules. We make an help array B[1..P](I used it to build R array) which we fill with the difference between the current and previous elements (B[i] = A[i]  A[i  1]) and we split the array on the point where abs(B[i]) > L. Now we have sub arrays that follow the L rule.
Follow the K rule: here we just split the sub arrays from above(after L rule) on the points where A[i] > K;
Follow the N and M rule: here we iterate all possible sub arrays with length = N and count the color change in R to be equal to M.
If tall the rules are true we count++;
public ArrayList<String> getWordSequences(Set<String> dict, String text) {
ArrayList<String> results = new ArrayList<String>();
getWordSequences(dict, results, text, new Stack<String>());
return results;
}
private void getWordSequences(Set<String> dict, ArrayList<String> results,
String text, Stack<String> currResult) {
if (text.length() == 0) {
String result = getSentence(currResult);
if (!results.contains(result))
results.add(result);
}
else {
String leftWord;
for (int i = 1; i < text.length(); i++) {
leftWord = text.substring(0, i);
if (dict.contains(leftWord)) {
currResult.add(leftWord);
getWordSequences(dict, text.substring(i));
currResult.pop();
}
}
}
}
private String getSentence(Stack<String> r) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < r.size(); i++)
result.append(r.get(i) + " ");
return result.toString().trim();
}
 GKalchev March 05, 2012
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!
Open Chat in New Window
O(1) insert, delete search
Implementation is easy. Just each entry of the hashTable shall have a links to the next and prev entry. So whenever accessed the entry you just move it to the head of the LinkedList like entries. If you want to add a max count of the elements in cache just whenever new node added remove the last one from the LinkedList like entries. Here is a very simple java implementation using the built in LinkedHashTable :
 GKalchev June 26, 2012