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);
}
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;
}
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;
}
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);
}
}
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;
}
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);
}
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;
}
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
// 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;
}
}
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;
}
}
// 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;
}
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:
cut-point | 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;
}
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;
}
// 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;
}
}
//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;
}
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;
}
@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);
}
}
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!
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