Dhass
BAN USERHere Facebook friend functionality would be a graph data structure.
We could have HashMap or key value store of (UserId,List of friends). This key value store can be partitioned based on names of the user or based on user location so that they could loaded in different servers.
Friend object can contain all the details of his friends and his posts.
For caching, we could cache just the accessed friend objects for a particular user in our local cache.
Using recursion we can find all possible ways to sum up to a dollar.
Code:
public void count_ways(int N, int i, int arr[], int t[]) {
if (N == 0) {
print(t, arr, i);
return;
}
if (i == arr.length)
return;
for (int j = 0; j * arr[i] <= N; j++) {
{
t[i] = arr[i] * j;
count_ways(N - t[i], i + 1, arr, t);
}
}
}
public void print(int t[], int a[], int n) {
for (int i = 0; i < n; i++)
System.out.print(a[i] + "*" + t[i] / a[i] + " ");
System.out.println();
}
Invocation:
int a[] = { 1, 5, 10, 25, 50 };
int val = 100;
int t[] = new int[a.length];
count_ways(val, 0, a, t);
Iterative approach. Time complexity: O(n) and O(1) space complexity.
Here we use the populated sibling ptr to traverse the tree in the zigzag manner and populate the sibling ptr of root's child.
Code:
public BinaryTreeNode populateSiblingPtr(BinaryTreeNode root) {
if (root == null)
return null;
BinaryTreeNode finalRoot = root;
root.sibling = null;
//start will have first node at from left at next level
BinaryTreeNode start = root.left != null ? root.left : root.right;
while (root != null) {
if (root.left != null)
root.left.sibling = root.right;
if (root.right != null)
root.right.sibling = root.sibling == null ? null : root.sibling.left;
if (start == null)
start = root.left != null ? root.left : root.right;
if (root.sibling == null) {
root = start;
if (start != null)
start = start.left != null ? start.left : start.right;
} else
root = root.sibling;
}
return finalRoot;
}
Traverse the tree in postorder and pass on the sums from child nodes to its parent.
Code:
public int getSumOfChildNodes(BinaryTree root) {
if (root == null)
return 0;
int left = getSumOfChildNodes(root.left);
int right = getSumOfChildNodes(root.right);
int sum = left + right + root.data;
System.out.println(root.data + " " + sum);
return sum;
}
Use binarysearch.
Code:
public int binSearch(int a[], int low, int high) {
if (low > high)
return -1;
int mid = low + (high - low) / 2;
if (a[mid] == 1 && (mid == 0 || a[mid - 1] == 0))
return mid;
else if (a[mid] == 1 && a[mid - 1] != 0)
return binSearch(a, low, mid - 1);
else
return binSearch(a, mid + 1, high);
}
Binary Search tree can be used here as the Insert and Delete can be achieved in O(log n).For get random element,we could have a extra field in the tree size and populate the size of left+right childs + 1. So getting Kth smallest element can be achieved in O(log n).
Code for finding Kth element in log(n):
public int calculateSize(BinaryTree root) {
if (root == null)
return 0;
root.size = calculateSize(root.left) + calculateSize(root.right) + 1;
return root.size;
}
public BinaryTree getKthSmallestElmt(BinaryTree root, int K) {
int s = (root.left == null ? 0 : root.left.size) + 1;
if (s == K)
return root;
if (K > s)
return getKthSmallestElmt(root.left, K);
else
return getKthSmallestElmt(root.right, K - s);
}
public int minEdits(char s1[], char s2[]) {
int m = s1.length, n = s2.length;
int d[][] = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0)
d[i][j] = j * I;
else if (j == 0)
d[i][j] = i * D;
else {
if (j < i)
d[i][j] = minimum(d[i - 1][j - 1]
+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
d[i - 1][j] + R, d[i][j - 1] + I);
else
d[i][j] = minimum(d[i - 1][j - 1]
+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
d[i - 1][j] + R, d[i][j - 1] + D);
}
}
}
return d[m][n];
}
Using Edit distance algo
Code:
public final int I = 8;
public final int D = 6;
public final int R = 8;
public int minEdits(char s1[], char s2[]) {
int m = s1.length, n = s2.length;
int d[][] = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0)
d[i][j] = j * I;
else if (j == 0)
d[i][j] = i * D;
else {
if (j < i)
d[i][j] = minimum(d[i - 1][j - 1]
+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
d[i - 1][j] + R, d[i][j - 1] + I);
else
d[i][j] = minimum(d[i - 1][j - 1]
+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
d[i - 1][j] + R, d[i][j - 1] + D);
}
}
}
return d[m][n];
}
Using Edit distance algo.
Code:
public final int I = 8;
public final int D = 6;
public final int R = 8;
public int minEdits(char s1[], char s2[]) {
int m = s1.length, n = s2.length;
int d[][] = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0)
d[i][j] = j * I;
else if (j == 0)
d[i][j] = i * D;
else {
if (j < i)
d[i][j] = minimum(d[i - 1][j - 1]
+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
d[i - 1][j] + R, d[i][j - 1] + I);
else
d[i][j] = minimum(d[i - 1][j - 1]
+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
d[i - 1][j] + R, d[i][j - 1] + D);
}
}
}
return d[m][n];
}
public int minimum(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
Using Edit distance algorithm:
Code:
public final int I = 8;
public final int D = 6;
public final int R = 8;
public int minEdits(char s1[], char s2[]) {
int m = s1.length, n = s2.length;
int d[][] = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0)
d[i][j] = j * I;
else if (j == 0)
d[i][j] = i * D;
else {
if (j < i)
d[i][j] = minimum(d[i - 1][j - 1]
+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
d[i - 1][j] + R, d[i][j - 1] + I);
else
d[i][j] = minimum(d[i - 1][j - 1]
+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
d[i - 1][j] + R, d[i][j - 1] + D);
}
}
}
return d[m][n];
}
public int minimum(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
Java code:
boolean matchExp(char exp[], char str[], int i, int j) {
if (i == exp.length && j == str.length)
return true;
if ((i == exp.length && j != str.length)
|| (i != exp.length && j == str.length))
return false;
if (exp[i] == '?' || exp[i] == str[j])
return matchExp(exp, str, i + 1, j + 1);
if (exp[i] == '*')
return matchExp(exp, str, i + 1, j) || matchExp(exp, str, i, j + 1)
|| matchExp(exp, str, i + 1, j + 1);
return false;
}
Code:
public void printSpiralOrder(int a[][]) {
int m = a.length,n = a[0].length;
int rowStart = 0, rowEnd = m - 1, colStart = 0, colEnd = n - 1;
while (rowStart <= rowEnd && colStart <= colEnd) {
int i = rowStart, j = colStart;
for (j = colStart; j <= colEnd; j++)
System.out.print(a[i][j] + " ");
for (i = rowStart + 1, j--; i <= rowEnd; i++)
System.out.print(a[i][j] + " ");
for (j = colEnd - 1, i--; j >= colStart; j--)
System.out.print(a[i][j] + " ");
for (i = rowEnd - 1, j++; i > rowStart; i--)
System.out.print(a[i][j] + " ");
rowStart++;rowEnd--;colStart++;colEnd--;
}
}
a) Have a hashmap with <string,count> and min heap. While reading every word,increment the count of word in the hashmap and check the head of min heap.If the count of the head is less the count of current word,remove the head and add the current word to head.
b) Hashmap of <letters,count>
Code:
public void printSubArraysSumZero(int a[]) {
int s[] = new int[a.length];
int l = a.length;
for (int i = 0; i < l; i++) {
if (i == 0)
s[i] = a[i];
else
s[i] = s[i - 1] + a[i];
}
HashMap<Integer, ArrayList<Integer>> h = new HashMap<Integer, ArrayList<Integer>>();
ArrayList<Integer> t = new ArrayList<Integer>();
t.add(-1);
h.put(0, t);
for (int i = 0; i < l; i++) {
if (h.containsKey(s[i])) {
for (Integer v : h.get(s[i]))
printArray(a, v + 1, i);
h.get(s[i]).add(i);
} else {
ArrayList<Integer> in = new ArrayList<Integer>();
in.add(i);
h.put(s[i], in);
}
}
}
public void printArray(int a[], int i, int j) {
for (int n = i; n <= j; n++)
System.out.print(a[n] + " ");
System.out.println();
}
We can print using binary equivalent of number from 0 to pow(2,n)
Code:
public void truthTable(int n) {
int p = (int) Math.pow(2, n);
for (int i = 0; i < p; i++) {
for (int k = 0; k < n; k++) {
int v = i & 1 << n - 1 - k;
System.out.print(v == 0 ? "T" : "F");
}
System.out.println();
}
}
One more solution:
Find the last occurrence of element by traversing from end.
Code:
public void maxDistance(int a[]) {
TreeSet<Integer> t = new TreeSet<Integer>();
for (int i = 0; i < a.length; i++) {
if (!t.contains(a[i])) {
int j = a.length - 1;
while (j >= i) {
if (a[i] == a[j]) {
t.add(a[i]);
System.out.println("Max(" + a[i] + ")= " + (j - i));
break;
}
j--;
}
}
}
}
Using DP we can solve this.
Code:
public void findMinCostAndQuantity(int q[], int p[], int tot) {
int c[] = new int[tot + 1];
int price[] = new int[tot + 1];
for (int i = 0; i <= tot; i++) {
c[i] = i;
price[i] = 10000000;
}
for (int i = 1; i <= tot; i++) {
for (int j = 0; j < q.length && q[j] <= i; j++) {
if (i == q[j] && price[i] > p[j]) {
c[i] = 1;
price[i] = p[j];
}
if ((price[i] > price[i - q[j]] + p[j])
|| (price[i] == price[i - q[j]] + p[j] && (c[i] > c[i
- q[j]] + 1))) {
price[i] = price[i - q[j]] + p[j];
c[i] = c[i - q[j]] + 1;
}
}
}
System.out.println(c[tot]);
System.out.println(price[tot]);
}
Here I have kept the price to be optimum and then the quantity.
- Dhass April 14, 2013Traverse right,center and left. Inorder in opposite direction.
Code:
int count=0;
public void findKthLargest(BinarySearchTree root, int K) {
if (root != null) {
findKthLargest(root.getRight(), K);
count++;
if (count == K)
System.out.println(root.getData());
findKthLargest(root.getLeft(), K);
}
}
Code:
public void intersectionOfSortedArrays(int a[], int b[]) {
int al = a.length, bl = b.length;
int c[] = new int[al + bl];
int i = 0, j = 0, k = 0;
while (i <= al - 1 && j <= bl - 1) {
if (i < al && j < bl) {
if (a[i] == b[j]) {
if (k == 0 || c[k - 1] != a[i]) {
c[k] = a[i];
k++;
i++;
j++;
} else {
i++;
j++;
}
} else if (a[i] < b[j]) {
i++;
} else
j++;
}
}
//Output
for (int n = 0; n < k; n++)
System.out.print(a[n] + " ");
}
public void printSpiralOrder(char a[][]) {
int m = a.length;int n = a[0].length;
int rowStart = 0, rowEnd = m - 1, colStart = 0, colEnd = n - 1;
while (rowStart <= rowEnd && colStart <= colEnd) {
int i = rowStart, j = colStart;
for (j = colStart; j <= colEnd; j++)
System.out.print(a[i][j] + " ");
for (i = rowStart + 1, j--; i <= rowEnd; i++)
System.out.print(a[i][j] + " ");
for (j = colEnd - 1, i--; j >= colStart; j--)
System.out.print(a[i][j] + " ");
for (i = rowEnd - 1, j++; i >= rowStart; i--)
System.out.print(a[i][j] + " ");
rowStart++;rowEnd--;colStart++;colEnd--;
}
}
This can be done in linear time.First reverse the sentence and then reverse the individual words.
Code:
public class ReverseSentence {
public static void main(String[] args) {
String a = "Today is Wednesday";
a = a.trim();
char[] cArr = a.toCharArray();
ReverseSentence r = new ReverseSentence();
r.reverse(cArr, 0, cArr.length-1);
int s = 0;
for (int i = 0; i < cArr.length; i++) {
if (cArr[i] == ' ') {
r.reverse(cArr, s, i - 1);
s = i + 1;
}
}
//call for the last word in the sentence
r.reverse(cArr, s, cArr.length-1);
System.out.println(cArr);
}
public void reverse(char c[], int i, int j) {
char t;
while (i < j) {
t = c[i];
c[i] = c[j];
c[j] = t;
i++;j--;
}
}
}
Move the first pointer for n steps and then start second pointer from head.When the first pointer reaches the end,second pointer will be in the nth node from last.
Code:
public Node nthNodeFromLast(Node head,int n){
Node cur=head;Node cur1=head;
int count=0;
while(cur.next!=null){
cur = cur.next;
count++;
if(count>=n)
cur1 = cur1.next;
}
return cur1;
}
Yes..We can use DP to get the shortest path here..Complexity would be O(n2)
Code:
public int getMinCostPath(int a[][]) {
int tc[][] = new int[a.length][a.length];
tc[0][0] = a[0][0];
for (int i = 1; i < a.length; i++) {
tc[i][0] = tc[i - 1][0] + a[i][0];
}
for (int j = 1; j < a.length; j++) {
tc[0][j] = tc[0][j - 1] + a[0][j];
}
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a.length; j++) {
tc[i][j] = min(tc[i - 1][j], tc[i][j - 1], tc[i - 1][j - 1])
+ a[i][j];
}
}
return tc[a.length - 1][a.length - 1];
}
Here the start and end are first and last node.That can be modified.
- Dhass April 11, 2013
This can solved by the following.
- Dhass January 07, 2015- Add the pairs(JFK -> LXA, SNA -> RKJ, LXA -> SNA ) in List to a hashMap as key value pair.
- Maintain a visited set which just holds the city names.
- Then start fetching the elements from the start element in the list from hashMap. While fetching add the key in the visited Set.
- Add the retrieved key value pair in the result list which you are going to return
- Stop when you cannot find value for the given key or the retrieved value is already in the visited set(which will stop a cycle).