ahmad.m.bakr
BAN USERI am a software development engineer
Always simplify things and start building up.
Assume that we have a small set of videos that we need to track the counts. Also assume that we are not handling any spam. A basic approach is using relational databases (video_id, count) that is being incremented whenever a user clicks on.
What is the problem with this approach? The database operation is very expensive for each click. A possible solution we can have Memcache or Redis layer above the DB that counts the number of clicks for each video. And having a background job that reads the cached counts and reflects that in the DB. Pros: much faster, Cons: more complex, can lose data in case of server failure and cached values have not populated in the DB yet and the values in the DB are not the most recent values.
Another side of improvement is bandwidth wise. Assuem that it is not necessary that the number of hits to be really accurate. We can convert the connection request for increment to be based on UDP rather than TCP.
Again discuss with the interview the pros and cons and let him lead which direction should the discussion goes.
You assume the number exists in the array. If the number does not exist then your upper and lowers bounds will not work
- ahmad.m.bakr June 18, 2015O(n) .. taking advantage of a sorted array, given start and end pointers. if A[start]+A[end]>=n, it implies that all elements at positions > start achieve the condition. That's why we count+=end-start.
public static int count(int [] array, int n){
if(array == null) return 0;
int count=0;
int start=0;
int end=array.length-1;
while(end>start){
if(array[start] + array[end] >= n){
count+= end-start;
end--;
}else{
start++;
}
}
return count;
}
public static String findDifference(String aStream, String bStream){
StringBuilder result = new StringBuilder();
int index = 0;
boolean carry = false;
while(index < aStream.length()){
int a = aStream.charAt(index) - '0';
int b = 0;
if(index < bStream.length()){
b = bStream.charAt(index) - '0';
}
if(carry){
if(a == 0){
a = 10;
carry = true;
}
a-=1;
}
if(a < b){
a += 10;
carry = true;
}
result.append(a -b);
index++;
}
return result.reverse().toString();
}
A Max-Heap data structure could be a nice solution to this problem. Each node represents a page and the key is its views count. Building a heap from n entries requires O(n log n) and insertion/heapify is ofcourse O(log n) .. Finding the most k frequent pages is O(k).
- ahmad.m.bakr January 19, 2014This is a partition problem. The basic idea is to know if there is s subset of elements that can sum up to k .. where k is the sum of all elements in the array. The trick is to know how to find the elements that can sum up to K but consider that:
For any number on the array, there are two options: 1- Take it 2- Ignore it. For each of these options, you have to try all other possibilities for other number. This lead to 2^n performance.
A Java implementation
public boolean findPartition(int [] array){
int k = 0;
for (int i = 0; i < array.length; i++) k += array[i];
return isSubset(array, array.length, k);
}
public boolean isSubset(int [] array, int n, int sum){
if(sum==0) return true;
if(n==0 && sum!=0) return false;
// If last element is greater than sum, then ignore it
if(array[n-1]>sum) return isSubset(array, n-1, sum);
//check if sum can be obtained by any of the following
// (a) excluding the last element
// (b) including the last element
return isSubset(array, n-1, sum) || isSubset(array, n-1, sum-array[n-1]);
}
This can be done by BFS algorithm and you only consider nodes that at distance K from the given node. The given node is the parent of the tree we need to parse. A java code for this problem can be like that
public ArrayList<Node> printNodes(Node node, int k){
Queue<Node> queue = new LinkedList<>();
ArrayList<Node> list = new ArrayList<>();
int level = 0;
int nodesToProcess = 1;
int nodesInNextLevel =0;
queue.add(node);
while(!queue.isEmpty()){
Node n = queue.remove();
nodesToProcess--;
if(n.left!=null){
queue.add(n.left);
nodesInNextLevel++;
}
if(n.right!=null){
queue.add(n.right);
nodesInNextLevel++;
}
if(level == k) list.add(n);
if(nodesToProcess==0){
level++;
nodesToProcess = nodesInNextLevel;
nodesInNextLevel=0;
if(level>k) break;
}
}
return list;
}
The idea is simply to make use of the property that both arrays is sorted. In any sorted array you can find the median at:
1- Array[(Length/2)+1] if array length is odd
2- The average of Array[(Length/2)] + Array[(Length/2)+1] if the array length is even
Given m and n, it means that we need to process the smallest (m+n)/2 numbers before we reach the median. The following code makes the task and it considers the boundaries of the arrays as well.
public static double medianOfSortedArray(int [] a, int []b){
int medianPosition = (a.length+b.length)/2;
int aIndex=0;
int bIndex=0;
double median =0;
if((a.length+b.length)%2!=0) medianPosition++;
//loop till you reach the medianIndex
while((aIndex+bIndex)<medianPosition){
if((aIndex<a.length && bIndex<b.length && a[aIndex] <= b[bIndex]) || bIndex >= b.length ){
median = a[aIndex];
aIndex++;
}else{
median = b[bIndex];
bIndex++;
}
}
//in case of even numbers of integers
if((a.length+b.length)%2==0){
if((aIndex<a.length && bIndex<b.length && a[aIndex] <= b[bIndex]) || bIndex >= b.length){
median = ((median + a[aIndex])*1.0)/2;
}else{
median = ((median + b[bIndex])*1.0)/2;
}
}
return median;
}
That's not robust enough since you may go beyond the array index. Consider this case
a = {3,4,5}
b = {2}
after the first round j=1, then at the second round b[j] is out of the index (it should be b[j] not a[j])
Also you did not handle the case when the sum of lengths of both arrays is even
The idea is to use BFS while keeping track of the number of nodes in the current level as well as the depth of the current level. If the number of nodes at level i < 2^i AND there are nodes in the next level then we return false.
In the following method, we maintain four variables:
1- nodesToProcessInCurrentLevel keeps track of how how many nodes we have to process in the current level (and when it equals zero, it means that we done processing with the current level)
2- nodesInNextLevel keeps track with the number of nodes in the next level and it's incremented each time we insert a child of any node at the current level
3- nodesInCurrentLevel is the total number of nodes at the current level
4- depth is the depth of the current level
public static boolean checkLeavesAtSameLevel(Node root){
if(root == null) return true;
Queue<Node> queue = new LinkedList<Node>();
int nodesToProcessInCurrentLevel = 1;
int nodesInNextLevel = 0;
int nodesInCurrentLevel = 0;
int depth=0;
queue.add(root);
while(queue.size()>0){
Node node = queue.poll();
nodesInCurrentLevel++; //while polling keep track of the number of processed nodes
nodesToProcessInCurrentLevel--;
if(node.leftNode!=null){
queue.add(node.leftNode);
nodesInNextLevel++; //track the number of nodes of the next level
}
if(node.rightNode != null){
queue.add(node.rightNode);
nodesInNextLevel++;
}
if(nodesToProcessInCurrentLevel==0){
if(nodesInCurrentLevel < Math.pow(2, depth) && nodesInNextLevel>0) return false;
depth++;
nodesToProcessInCurrentLevel=nodesInNextLevel;
nodesInNextLevel=0;
nodesInCurrentLevel=0;
}
}
return true;
}
That's right, thanks @masterjaso for the correction :)
- ahmad.m.bakr June 05, 2013I implemented a recursive function for the solution. The initial guessIndex =0 and each recursive call, i calculate the offset for a possible jump
public static int findElement(int [] a, int target, int guessIndex){
if(guessIndex >= a.length ) return -1;
if(a[guessIndex] == target) return guessIndex;
int offset = target - a[guessIndex];
return findElement(a, target, guessIndex+offset);
}
Your solution is good however you can mention some other solutions like:
1- If equal arrays mean they are identical (i.e they have the same numbers at the same positions) then it can be done in O(n) and O(1) space just by looping in one of the arrays and compare each element to its corresponding element in the other array.
2- If you can know the range of the numbers in the array (like numbers are from 0 to N-1) then you will need an additional array of the same size instead of a hash table which will give you a faster access. By the additional array you can loop on one array, count the occurrences of each element then loop on the second array and subtract the occurrences. If the additional array has zero at each position then they are equal otherwise they are not. This requires four passes (initialize the temp array, count the occurrences of the first array, subtract the occurrences of the second array and finally check the temp array).
3- You can sort both arrays and apply approach #1 O(N log N)
4- You can use a hash table just like you did.
Ofcourse a comparison of the lengths of the both arrays can save much effort.
Hope that helps you .
The following code returns the indexes of the pairs which their sum is K.
public static int [] findParis(int [] array, int k){
int [] indexes = new int [2];
indexes[0]= indexes[1] =-1;
Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
for (int i = 0; i < array.length; i++) {
if(hash.containsKey(array[i])){
indexes[0] = hash.get(array[i]);
indexes[1] = i;
break;
}
hash.put(k-array[i], i);
}
return indexes;
}
This can be done by a recursive inorder traversal of the BST and keeping global value to know when you reach the kth smallest number. Assume k is 4, the following code will assign and return the target node if found.
static int k =4;
public static Node inOrderTraversal( Node node, Node target ){
if(node == null)return null;
inOrderTraversal(node.leftNode, target );
if(--k==0) target= node;
inOrderTraversal(node.rightNode, target);
return target;
}
You have 2^n sets to generate (including the empty set). You can loop for each integer value 'i' from 0 to 2^n and for each binary representation of 'i', print characters of string that corresponding to 1s in the binary representation. For example, a s = "123" and i="101" then you have set "13".
public static void printPowerSet(String s){
char [] array = s.toCharArray();
for(int i=0; i< Math.pow(2, array.length); i++){
char [] values = Integer.toBinaryString(i).toCharArray();
StringBuffer buffer = new StringBuffer();
int index=0;
for(int j=values.length-1; j>=0;j--){
if(values[j]=='1') buffer.append(array[index]);
index++;
}
System.out.println(buffer.toString());
}
}
Given an exmaple A= {1,2,3,4,5,6} and n = 10. Keep start and end pointer. When A[start] + A[end] >= n then all elements from start, start+1, start+2, .... end-1 are >= n. And so on
- ahmad.m.bakr July 14, 2015