Asif Garhi
BAN USERSorry but I fail to understand the question. Can you please explain a couple of 'true' and a couple of 'false' condition. Also failing to understand why 2 loops were needed to solve this. It's possible I haven't got the question right.
- Asif Garhi April 20, 2018Can someone please explain what a balanced max heap is? Please note I know what a max heap is.
- Asif Garhi April 05, 2016I don't know much about balanced max heap (I am studying about it now) but here is my attempt at it. I assume that min weight will always be at a node which has 2 leafs under it. If you go any higher - the weight will only increase.
public class SmallestWeightTree {
private static int height = 0, weight = Integer.MAX_VALUE;
private static Node nodeMinWeight = null;
public static int weigh(Node node, int level) {
int leftWeight = 0, rightWeight = 0, selfWeight = 0, totalWeight = 0;
if(node.hasLeft()) {
leftWeight = weigh(node.getLeft(), level + 1);
}
if(node.hasRight()) {
rightWeight = weigh(node.getRight(), level + 1);
}
if(node.isLeaf()) {
height = height < level ? level : height;
}
selfWeight = level * node.getValue();
totalWeight = leftWeight + rightWeight + selfWeight;
if(level == height - 1) { // At the level right above a leaf, time to compare weights
if(totalWeight < weight) {
weight = totalWeight;
nodeMinWeight = node;
}
}
return totalWeight;
}
}
int i = 1352;
String str = i + "";
Can we not use a Map? The keys would be name of the song presented to the user and values would be the actual media files. This covers random access in O(1). Map implementations like LinkedHashMap in java can also allow ordered access which solved the sequential access issue. Please add to this discussion if you feel this is not appropriate.
- Asif Garhi March 23, 2016package company.amazon;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class PatternFinderIn2DArray {
int[][] arr = {{9,5,3,5,3,8,4},
{3,8,9,5,0,8,4}};
int row = 2, col = 7;
public void find(int[][]arr, Map<String, Integer> patterns) {
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
Iterator<String> it = patterns.keySet().iterator();
while(it.hasNext()) {
String key = it.next();
char[] arrStr = key.toCharArray();
int idx = patterns.get(key);
if((arrStr[idx]+"").equals(arr[i][j]+"")) {
++idx;
if(idx == key.length()) {
System.out.println("Found "+key+", at row:"+i+",col:"+(j-key.length()+1));
idx = 0;
}
patterns.put(key, idx);
} else {
if(idx > 0) {
idx = 0;
patterns.put(key, idx);
}
}
}
}
}
}
public static void main(String[] args) {
PatternFinderIn2DArray util = new PatternFinderIn2DArray();
Map<String,Integer> patterns = new HashMap<String, Integer>();
patterns.put("950", 0);
patterns.put("384", 0);
patterns.put("353", 0);
util.find(util.arr, patterns);
}
}
public String findPattern(String logicalPattern) {
String pattern = "";
int numOfIncrements = countNumOfInc(logicalPattern);
int i = 1, j = logicalPattern.length() + 1;
char[] arr = logicalPattern.toCharArray();
for(int n = 0; n < logicalPattern.length();) {
if(arr[n] == 'I') {
pattern += i;
i = setI(i,pattern,j);
n++;
--numOfIncrements;
} else {
int temp = j - numOfIncrements;
while(arr[n] == 'D') {
pattern += temp--;
n++;
}
}
}
while(pattern.length() < logicalPattern.length() + 1) {
pattern += i++;
}
return pattern;
}
private int setI(int i, String pattern, int j) {
while(pattern.contains(i+"") && i <= j) ++i;
return i;
}
private int countNumOfInc(String logicalPattern) {
int count = 0;
for(char c : logicalPattern.toCharArray()) {
if(c == 'I') ++count;
}
return count;
}
I don't understand the question. Can you give an example please?
- Asif Garhi February 21, 2016For each cell that has 1, check each adjacent cell only if it falls behind this cell or above this cell (i.e. only back check). If none of them are 1 - increment islands.
public int find(int[][] arr, int rows, int cols) {
int numOfIslands = 0;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < rows; j++) {
if(
arr[i][j] == 1 &&
(j-1 < 0 || arr[i][j-1] != 1) &&
(i-1 < 0 || j-1 < 0 || arr[i-1][j-1] != 1) &&
(i-1 < 0 || arr[i-1][j]!=1) &&
(i-1 < 0 || j+1 >= cols || arr[i-1][j+1]!=1)
) {
++numOfIslands;
}
}
}
return numOfIslands;
}
For each cell check each adjacent cell only if it falls behind this cell or above this cell (i.e. only back check). If none of them are X - increment islands.
- Asif Garhi February 21, 2016Map<Integer,Map<String,LinkedList<String>>>
For Map<#ofVisits,Map<PageName,List<Usernames>>>
and then another Map<String,Integer> for Map<PageName,#ofVisits>
When a page is visited, you find it from the second map, based on the #of visits you find it from the first map, add the newly visited user to the list and move that page in the first map e.g. if it was mapped against 2, you move it to 3.
At any given moment, it is easy to answer the 3 questions from the first map.
- Find the min and max
- factor=max-min/length-1
- if factor is not an integer - this is not a sequence
- Go through each element
-- Save element in a map
-- If element is already in map - this is not a sequence
-- if the difference between current and previous is not a multiple of factor or is greater than the factor - it is not a sequence
Otherwise it is a sequence
Ritika shah can you please explain the question a bit more?
- Asif Garhi February 18, 2016Not quite sure if I understood the question right but I am assuming we want to sort them in asc/desc order of height. If that is the case why not Quick sort them? It is nlogn and requires only 5 swaps for the input given. Simplifying the input given here is how the initial array looks like: 3,4,1,2,0,6,5
After swap 1: 0,4,1,2,3,6,5
After swap 2: 0,2,1,4,3,6,5
After swap 3: 0,1,2,4,3,6,5
After swap 4: 0,1,2,4,3,5,6
After swap 5: 0,1,2,3,4,5,6
Other nlogn sorting algorithms - merge sort doesn't swap in its simple form and heap sort has more swaps than quicksort.
How much time do you get for such a question? It took me almost 4 hours to come to the most efficient solution I could come up with. I know that is very poor timing. What should I do to improve?
- Asif Garhi February 17, 2016private int[] arr = {1,1,0,0,1,1,0,1,1,1};
private int k = 2;
private int max = 0;
public void find() {
int cnt = 0,k_=k,i_=-1;
for (int i = 0; i < arr.length;) {
if(arr[i] == 1) {
++cnt;
++i;
} else if(arr[i] == 0 && k_-- > 0) {
if(i_== -1) {
i_ = i + 1;
}
++cnt;
++i;
} else {
max = max > cnt ? max : cnt;
k_ = k;
i = i_;
i_ = -1;
cnt = 0;
}
}
max = max > cnt ? max : cnt;
}
Were you required to construct an Employee java object here which I think needs reflection knowledge. If that is not the case I would put everything in a map starting with the main map called employee. Then start putting everything as key value until I see an input like [address] for which I will create another map and save this as a nested map inside the main map and so on.
On retrieval, if I get employee.name - I will turn it into employee.get("name") and check if it instance of String, if it is - just output it, If not - it will be instance of Map and I can in that case continue until I find the String I am looking for.
I agree we can take help from the Composite pattern.
Exactly what I was thinking. However if we need functions like name like 'a%' or name like '%a%' or name like '%a' I would have a Map<Character, NameInfo>. Where NameInfo has 3 binary trees. Tree 1 has entry for all IDs with names starting with that Character, Tree 2 has all ending with it and Tree 3 with all names containing it. This is a lot of space I know but makes the retrieval faster.
- Asif Garhi September 05, 2015public class PrintRepeatPattern {
private static int[] arr = {1,1,1,1,2,3,4,5,5,6,7,7,7,8,8,8};
public static void main(String[] args) {
doPrint(3);
}
private static void doPrint(int skip) {
int cnt = 1, i = 0;
for(; i < arr.length; ) {
if(i > 0 && arr[i] != arr[i-1]) {
print(arr[i-1],cnt);
cnt = 1;
}
if(chunk(i,skip)) {
cnt = cnt + skip - 1;
i += skip;
} else {
if(arr[i] == arr[i - 1]) ++cnt;
++i;
}
}
print(arr[i-1],cnt);
}
private static boolean chunk(int i, int skip) {
return (i + skip - 1 < arr.length && arr[i] == arr[i + skip - 1]);
}
private static void print(int number, int cnt) {
if(cnt > 1) {
System.out.printf("%d occurs %d times\n",number,cnt);
}
}
}
We can take advantage of the fact that some patterns repeat. So we can check in chunks of say 3 or 5 etc. For example for chunk of 3 if arr[0]==arr[2] we can directly say that the number repeats at least 3 times and skip i to i+3, if not we can go linear. The performance may be a little better than O(N)
- Asif Garhi August 12, 2015public class MaxWithinARangeFinder {
private static int k;
private static int[] arr = new int[100];
private static int maxIdx = 1, currIdx;
private static int doFind(int i) {
arr[currIdx] = i; // {10, 9, 52, 13, 53} 2
if(k == 1) return arr[currIdx];
maxIdx = calculateMax(currIdx);
++currIdx;
return maxIdx;
}
private static int calculateMax(int currIdx) {
// 1. check if current max is -1, if so - assign the first element and return
int maxIdxLocal = maxIdx;
if(maxIdx == -1) maxIdxLocal = 0;
else {
// check if prev max is within range
if(currIdx - k < maxIdx) {
// return max of prevMax and currIdx
maxIdxLocal = max(maxIdx, currIdx);
} else {
// prev Max is gone out of the window size, calculate new max
maxIdxLocal = calculateNewMax(currIdx);
}
}
maxIdx = maxIdxLocal;
return maxIdxLocal;
}
private static int max(int maxIdx, int currIdx) {
return (arr[maxIdx] > arr[currIdx]) ? maxIdx : currIdx;
}
private static int calculateNewMax(int currIdx) {
int cnt = k;
int mIdx = currIdx;
while(cnt > 0) {
if(arr[currIdx] > arr[mIdx]) mIdx = currIdx;
--currIdx;
--cnt;
}
return mIdx;
}
}
1. For each appointment fill a Map<Integer,List<String>> e.g. if the first appointment is 1 to 5, put following entries in a map:
1: 1-5
2: 1-5
3: 1-5
4: 1-5
5: 1-5
2. When another appointment arrives, try doing the same thing again.
3. If the map is already having a value, check if there is a conflict (because 5-6 is not conflicting with 1-5 and 5 will have a value in both the cases)
This goes through each appointment once but has to go through the mapped hours multiple times. Not sure if you can call it O(N)?
Please suggest.
When you say parent of the ith node - the sequence in which the tree is traversed to populate this array matters. Can you please specify the sequence in which the tree is traversed and also what is the type of the array P[]? Is it array of Nodes with each Node having value and children fields?
Please suggest.
Thanks
If I have understood the question properly:
int lastIdx = arr.length - 1;
int height = 1;
while(lastIdx > 0) {
++height;
lastIdx = arr[lastIdx - 1];
}
return height;
1. Imagine nodes are numbered 1 to n.
2. The value at index 0 is -1 because there is no parent for root or the 1st node, at index 1 is the node number of parent of 2nd node and so on.
3. Start from the last element of the array and jump on to the parents until there are none.
On the other hand, if the array holds the value (and not the number i.e. 1st, 2nd etc.) of parent node the answer to this question is the number of unique nodes in the array.
If someone disagrees, please share an example of how that array is created possibly with a picture of the tree. Thanks
TreeNode<String> newCurrRoot = null, newRoot = null, root = null;
public void doTurn(TreeNode<String> root) {
if(root.hasLeft()) {
doTurn(root.getLeft());
} else {
newRoot = breakLinks(root);
}
if(root.hasRight()) {
newCurrRoot.setLeft(root.getRight());
}
if(newCurrRoot != null) {
newCurrRoot.setRight(root);
}
newCurrRoot = breakLinks(root);
}
private TreeNode<String> breakLinks(TreeNode<String> root) {
if(root == null) return root;
root.setLeft(null);
root.setRight(null);
return root;
}
I have either failed to understand the requirement or some solutions posted above but this is my version. Visits only left nodes and reuses the nodes to make the new one. I would be glad to have some feedback. Sorry I haven't checked for edge/null cases.
- Asif Garhi October 18, 2014Best solution so far according to me. Thanks Nilesh.
- Asif Garhi October 03, 2014This is nice and covers all Cases. A similar program in java below.
- Asif Garhi October 02, 2014If we maintain an array of nodes DBEAFCG and a hash D:0, B:1 ... G:7 we can achieve all the requirements in O(N). Let's call the first array above as arr_1 and the second hash hash_2.
Algorithm:
1. Set cntr = 0;
2. In an inorder traversal starting with D do the following recursively:
a) Check if successor of this node is null - if it is - set it to arr_1[++cntr]; If not null go to step b)
b) Check if the already populated successor if present in hash_2, if not - set it to arr_1[++cntr] else go to step c)
c) Get the index of already populated successor from hash_2. If this index is greater than index of current node - do nothing else go to step d)
d) Set the successor to arr_1[++cntr]
Please let me know the inefficiencies related to this solution - One inefficiency is extra space but If we had to do this in O(n) I guess we need readily saved the immediate next successor (which we do in arr_1) and index of all other nodes to check if a node is before or after this node (which we do in hash_2).
*Edit*
Here is some code:
public class FindSuccessor {
private Map<TreeNode,Integer> hash_2 = new HashMap<>();
private TreeNode[] arr_1;
private int ctr = 0;
public void doFind(TreeNode root) {
if(root.getLeft()!=null) doFind(root.getLeft());
assignSuccessor(root);
if(root.getRight()!=null) doFind(root.getRight());
}
private void assignSuccessor(TreeNode<String> root) {
if(root.getSucc() == null) {
setNextAsSucc(root);
} else {
TreeNode<String> succ = root.getSucc();
if(!hashInorderNodes.containsKey(succ)) {
setNextAsSucc(root);
} else {
if(hashInorderNodes.get(succ) < hashInorderNodes.get(root)) {
setNextAsSucc(root);
} else {
++ctr;
}
}
}
}
private void setNextAsSucc(TreeNode root) {
try {
root.setSucc(arr_1[++ctr]);
} catch(ArrayIndexOutOfBoundsException a) {
root.setSucc(null); // not required becuase null by default but here for readibility
}
}
}
I am not sure how you achieve this in O(N) O(1) but for those who want to use an extra buffer - the most efficient way I think is to use another array of same size (VS 2 arrays for negative and positive each etc.). In this array, fill the positive indices from start of the array and negative indices from the end. Alternate values can then be retrieved from this array (idxArray) using:
for(int i = 0, j = arr.length - 1, n = 0; n < arr.length; n++) {
int nextIdx = idxArr[n % 2 == 0 ? (i < pc ? i++ : j--) : (j > nc ? j-- : i++)];
...
}
where pc is positive count and nc is negative count
- Asif Garhi September 06, 2014Neat but doesn't handle sentences with last character as space well I guess. So my version of your code:
public String revWordsInAGo(String s) {
if(s == null || s.isEmpty() || s.length() == 1) return s;
String r = "", w = "";
char[] c = s.toCharArray();
int i = 0;
for(; i < c.length; i++) {
char ch = c[i];
if(ch == ' ') {
r = r + w + ch;
w = "";
} else {
w = ch + w;
}
}
if(c[i - 1] != ' ') { // In case last character is not space
r = r + w;
}
return r;
}
I initially used 2 pointers to point to start and end of a word and then swap them in place but not sure if this is more efficient than yours:
public String doReverse(String str) {
if(str == null || str.length() < 2) return str;
char[] chars = str.toCharArray();
int ptr1, ptr2;
for(int i = 0; i < chars.length;) {
if(chars[i]!=' ') {
ptr1 = i;
for(ptr2 = i + 1; ptr2 < chars.length && chars[ptr2] != ' '; ptr2++) {}
if(ptr2 != chars.length - 1) --ptr2;
if(ptr2 - ptr1 > 0) {
swapWord(chars, ptr2, ptr1); // method not shown for simplicity
}
i = ptr2 + 2; // 2 because ptr2 points to last character of current word and next character is a space
} else {
++i;
}
}
return new String(chars);
}
I think this code doesn't consider the situation when the last character of the sentence is space - it will add the last reversed word twice. But this is clean otherwise and gets my vote.
public String revWordsInAGo(String s) {
if(s == null || s.isEmpty() || s.length() == 1) return s;
String r = "", w = "";
char[] c = s.toCharArray();
int i = 0;
for(; i < c.length; i++) {
char ch = c[i];
if(ch == ' ') {
r = r + w + ch;
w = "";
} else {
w = ch + w;
}
}
if(c[i - 1] != ' ') { // In case last character is not space
r = r + w;
}
return r;
}
One can also use 2 pointers pointing to start and end of a word and then reverse that word and move to the next word and so on but I am not sure if it is more efficient than your approach:
public String doReverse(String str) {
if(str == null || str.length() < 2) return str;
char[] chars = str.toCharArray();
int ptr1, ptr2;
for(int i = 0; i < chars.length;) {
if(chars[i]!=' ') {
ptr1 = i;
for(ptr2 = i + 1; ptr2 < chars.length && chars[ptr2] != ' '; ptr2++) {}
if(ptr2 != chars.length - 1) --ptr2;
if(ptr2 - ptr1 > 0) {
swapWord(chars, ptr2, ptr1);
}
i = ptr2 + 2; // 2 because ptr2 points to last character of current word and next character is a space
} else {
++i;
}
}
return new String(chars);
}
One more improvement to binary search method above can be to check on the top of the method
if (arr[startIndex] == arr[endIndex]) {
return endIndex - startIndex + 1;
}
This is especially helpful for arrays like 13,13,13,13,13,52,53,53,53,53,53
Nice binary search approach by the way.
/**
*
* @param <T>
* @param midNode points to 50
* @param newNode contains 40
*/
public void myAnswer(Node<T> midNode, Node<T> newNode) {
T prevVal = newNode.getValue();
T currValue = null;
while(midNode!=null) {
currValue = midNode.getValue();
midNode.setValue(prevVal);
if(midNode.getNext()!=null) midNode = midNode.getNext();
prevVal = currValue;
}
midNode.setNext(new Node(prevVal));
}
You mind adding some example to the question?
- Asif Garhi April 20, 2018