Skip to content

Commit 8ee3f3e

Browse files
shivam-maharshishivam-maharshi
committed
Added a few algorithms.
1 parent cf4b489 commit 8ee3f3e

File tree

10 files changed

+391
-34
lines changed

10 files changed

+391
-34
lines changed

‎src/main/java/array/FileUtil.java‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package array;
2+
3+
import java.io.BufferedReader;
4+
import java.io.BufferedWriter;
5+
import java.io.FileOutputStream;
6+
import java.io.FileReader;
7+
import java.io.IOException;
8+
import java.io.OutputStreamWriter;
9+
import java.io.Writer;
10+
import java.util.ArrayList;
11+
import java.util.List;
12+
13+
/**
14+
* Single class to be used for any interactions with Files.
15+
*
16+
* @author shivam.maharshi
17+
*/
18+
public class FileUtil {
19+
20+
public static List<String> read(String filepath, long startOffset, long readLimit) {
21+
System.out.println("Reading file : "+filepath);
22+
List<String> list = new ArrayList<String>();
23+
try {
24+
BufferedReader file = new BufferedReader(new FileReader(filepath));
25+
String line = null;
26+
while ((line = file.readLine()) != null && startOffset > 0) {
27+
startOffset--;
28+
}
29+
long count = 0;
30+
while ((line = file.readLine()) != null) {
31+
list.add(line.trim());
32+
count++;
33+
if (count >= readLimit)
34+
break;
35+
}
36+
file.close();
37+
} catch (IOException e) {
38+
e.printStackTrace();
39+
}
40+
System.out.println("Data read from : "+filepath);
41+
return list;
42+
}
43+
44+
public static List<String> read(String filepath) {
45+
return read(filepath, 0, Long.MAX_VALUE);
46+
}
47+
48+
public static List<String> read(String filepath, long readLimit) {
49+
return read(filepath, 0, readLimit);
50+
}
51+
52+
public static void write(List<String> list, String filepath) {
53+
System.out.println("Writing data to : "+filepath);
54+
try {
55+
Writer writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(filepath), "utf-8"));
56+
for (String line : list) {
57+
writer.write(line + "\n");
58+
}
59+
writer.flush();
60+
writer.close();
61+
System.out.println("Data written to : " + filepath);
62+
} catch (IOException e) {
63+
e.printStackTrace();
64+
}
65+
}
66+
67+
}

‎src/main/java/array/UriTesting.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package array;
2+
3+
import java.io.UnsupportedEncodingException;
4+
import java.net.URLEncoder;
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
8+
/**
9+
* @author shivam.maharshi
10+
*/
11+
public class UriTesting {
12+
13+
public static void main(String[] args) {
14+
long start = System.currentTimeMillis();
15+
String file = "C:/Users/Sam/Downloads/elwiki-20151201-all-titles-in-ns0.txt";
16+
List<String> urls = FileUtil.read(file);
17+
List<String> out = new ArrayList<>(), fail = new ArrayList<>();
18+
for (String url : urls)
19+
try {
20+
out.add(URLEncoder.encode(url, "UTF-8"));
21+
} catch (UnsupportedEncodingException e) {
22+
fail.add(url);
23+
}
24+
FileUtil.write(out, file + "encoded");
25+
FileUtil.write(fail, file + "failed");
26+
System.out.println("Encoded all URLs in: " + ((System.currentTimeMillis() - start) / 1000) + " seconds.");
27+
}
28+
29+
}

‎src/main/java/dp/PrintMaximumAWithFourKeys.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package dp;
2+
3+
import org.junit.Test;
4+
5+
import junit.framework.TestCase;
6+
7+
/**
8+
* Link:
9+
* http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/
10+
*
11+
* @author shivam.maharshi
12+
*/
13+
public class PrintMaximumAWithFourKeys extends TestCase {
14+
15+
@Test
16+
public static void test() {
17+
assertEquals(3, max(3));
18+
assertEquals(9, max(7));
19+
}
20+
21+
public static int max(int n) {
22+
int[] dp = new int[n], cp = new int[n];
23+
dp[0] = 1;
24+
dp[1] = 2;
25+
dp[2] = 3;
26+
cp[2] = 1;
27+
for (int i = 3; i < n; i++) {
28+
cp[i] = dp[i - 2];
29+
dp[i] = Math.max(i + 1, Math.max(2 * dp[i - 3], dp[i - 3] + cp[i - 1]));
30+
}
31+
return dp[n - 1];
32+
}
33+
34+
}

‎src/main/java/dp/WildCardPatternMatching.java‎

Lines changed: 0 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -36,10 +36,6 @@ public static void test() {
3636
assertEquals(true, match("abcdd", "....*"));
3737
}
3838

39-
public static void main(String[] args) {
40-
System.out.println(match("abc", "a*?*b?"));
41-
}
42-
4339
public static boolean match(String s, String p) {
4440
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
4541
populate(s, p, dp);

‎src/main/java/interview/amazon/FindHeavyCoin.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package interview.amazon;
2+
3+
import org.junit.Test;
4+
5+
import junit.framework.TestCase;
6+
7+
/**
8+
* Given an array of coins of same weight, find the single heavier coin.
9+
*
10+
* @author shivam.maharshi
11+
*/
12+
public class FindHeavyCoin extends TestCase {
13+
14+
@Test
15+
public static void test() {
16+
assertEquals(1, find(new int[] { 5, 8 }));
17+
assertEquals(0, find(new int[] { 8, 5 }));
18+
assertEquals(0, find(new int[] { 8, 5, 5 }));
19+
assertEquals(1, find(new int[] { 5, 8, 5 }));
20+
assertEquals(2, find(new int[] { 5, 5, 8 }));
21+
assertEquals(3, find(new int[] { 5, 5, 5, 8 }));
22+
assertEquals(2, find(new int[] { 5, 5, 8, 5 }));
23+
assertEquals(1, find(new int[] { 5, 8, 5, 5 }));
24+
assertEquals(0, find(new int[] { 8, 5, 5, 5 }));
25+
assertEquals(2, find(new int[] { 5, 5, 8, 5, 5, 5, 5, 5, 5, 5, 5 }));
26+
assertEquals(0, find(new int[] { 8, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }));
27+
assertEquals(10, find(new int[] { 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 8 }));
28+
assertEquals(2, find(new int[] { 5, 5, 8, 5, 5, 5, 5, 5, 5, 5 }));
29+
assertEquals(0, find(new int[] { 8, 5, 5, 5, 5, 5, 5, 5, 5, 5 }));
30+
assertEquals(9, find(new int[] { 5, 5, 5, 5, 5, 5, 5, 5, 5, 8 }));
31+
}
32+
33+
public static int find(int[] a) {
34+
if (a == null || a.length == 0 || a.length == 1)
35+
return -1;
36+
int l = 0, h = a.length - 1;
37+
while (h > l) {
38+
if (h - l == 1)
39+
return a[l] > a[h] ? l : h;
40+
int m = ((h - l) / 2) + l, ls = 0, hs = 0;
41+
ls = (h - l + 1) % 2 == 1 ? getSum(a, l, m - 1) : getSum(a, l, m);
42+
hs = getSum(a, m + 1, h);
43+
if (ls == hs)
44+
return m;
45+
if (ls < hs)
46+
l = m + 1;
47+
else
48+
h = (h - l + 1) % 2 == 1 ? m - 1 : m;
49+
}
50+
return l;
51+
}
52+
53+
public static int getSum(int[] a, int l, int h) {
54+
int r = 0;
55+
for (int i = l; i <= h; i++)
56+
r += a[i];
57+
return r;
58+
}
59+
60+
}

‎src/main/java/interview/amazon/InviteGuests.java‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package interview.amazon;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.List;
6+
import java.util.Map;
7+
8+
import org.junit.Test;
9+
10+
import junit.framework.TestCase;
11+
12+
/**
13+
* Given a list of guess figure out the people who should absolutely not be
14+
* invited to avoid reducing candies for the main host.
15+
*
16+
* @author shivam.maharshi
17+
*/
18+
public class InviteGuests extends TestCase {
19+
20+
@Test
21+
public static void childNotInvited() {
22+
String[] s = { "Guest,Inviter,CandyBrought,CandyConsumed",
23+
"Ivan,Cass,6,4", "Kale,Ivan,1,6",
24+
"Leon,Ivan,2,5", "Mark,Ivan,1,6" };
25+
assertEquals(3, getBlacklistedGuests(s).size());
26+
}
27+
28+
public static void main(String[] args) {
29+
String[] s = { "Guest,Inviter,CandyBrought,CandyConsumed",
30+
"Dole,Adam,2,3", "Greg,Dole,6,2" };
31+
List<String> l = getBlacklistedGuests(s);
32+
for (String ll : l)
33+
System.out.println(ll);
34+
}
35+
36+
public static List<String> getBlacklistedGuests(String[] s) {
37+
List<String> l = new ArrayList<>();
38+
// First entry is the header.
39+
if (s == null || s.length == 0 || s.length == 1)
40+
return l;
41+
Node root = populateTree(s);
42+
getBlacklistedGuests(root, l);
43+
return l;
44+
}
45+
46+
public static int getBlacklistedGuests(Node root, List<String> l) {
47+
for (String child : root.child.keySet())
48+
root.total += getBlacklistedGuests(root.child.get(child), l);
49+
if (root.total < 0) {
50+
l.add(root.name);
51+
return 0;
52+
} else
53+
return root.total;
54+
}
55+
56+
public static Node populateTree(String[] s) {
57+
Map<String, Node> m = new HashMap<>();
58+
String[] a = s[1].split(",");
59+
String root = a[1];
60+
m.put(a[1], new Node(a[1], 0));
61+
for (int i = 1; i < s.length; i++) {
62+
a = s[i].split(",");
63+
Node n = new Node(a[0], Integer.parseInt(a[2]) - Integer.parseInt(a[3]));
64+
m.put(n.name, n);
65+
m.get(a[1]).child.put(n.name, n);
66+
}
67+
return m.get(root);
68+
}
69+
70+
static class Node {
71+
String name;
72+
int val;
73+
int total;
74+
Map<String, Node> child;
75+
76+
public Node(String name, int value) {
77+
this.name = name;
78+
this.val = value;
79+
this.total = value;
80+
this.child = new HashMap<>();
81+
}
82+
83+
}
84+
85+
}

‎src/main/java/interview/amazon/OddTimesNumber.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package interview.amazon;
2+
3+
import java.util.Arrays;
4+
import java.util.List;
5+
6+
import org.junit.Test;
7+
8+
import junit.framework.TestCase;
9+
10+
/**
11+
* Find out the number present odd number of times in the given list.
12+
*
13+
* @author shivam.maharshi
14+
*/
15+
public class OddTimesNumber extends TestCase {
16+
17+
@Test
18+
public static void test() {
19+
assertEquals(5, get(Arrays.asList(new Integer[] { 1, 4, 2, 2, 7, 5, 7, 4, 1 })).intValue());
20+
}
21+
22+
public static Integer get(List<Integer> l) {
23+
if (l == null || l.isEmpty())
24+
return null;
25+
Integer r = l.get(0);
26+
for (int i = 1; i < l.size(); i++)
27+
r ^= l.get(i);
28+
return r;
29+
}
30+
31+
}

‎src/main/java/interview/google/MedianOfArray.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package interview.google;
2+
3+
import java.util.List;
4+
5+
/**
6+
* Link: https://www.interviewbit.com/problems/median-of-array/ Link:
7+
* http://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/
8+
*
9+
* @author shivam.maharshi
10+
*/
11+
public class MedianOfArray {
12+
13+
public static double findMedianSortedArrays(final List<Integer> a, final List<Integer> b) {
14+
if ((a == null || a.size() == 0) && (b == null || b.size() == 0))
15+
return -1;
16+
if (a == null || a.size() == 0)
17+
return b.size() % 2 == 1 ? b.get(b.size() / 2) : b.get((b.size() / 2) - 1);
18+
if (b == null || b.size() == 0)
19+
return a.size() % 2 == 1 ? a.get(a.size() / 2) : a.get((a.size() / 2) - 1);
20+
int as = a.size(), bs = b.size(), sum = as + bs;
21+
return sum % 2 == 1 ? find(a, b, sum / 2, 0, as, 0, bs, true) : find(a, b, (sum - 1) / 2, 0, as, 0, bs, false);
22+
}
23+
24+
public static double find(List<Integer> a, List<Integer> b, int k, int la, int ha, int lb, int hb, boolean odd) {
25+
double r = 0;
26+
return r;
27+
}
28+
29+
}

‎src/main/java/leetcode/hard/CountOfRangeSum.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package leetcode.hard;
2+
3+
import org.junit.Test;
4+
5+
import junit.framework.TestCase;
6+
7+
/**
8+
* Link: https://leetcode.com/problems/count-of-range-sum/
9+
*
10+
* @author shivam.maharshi
11+
*/
12+
public class CountOfRangeSum extends TestCase {
13+
14+
@Test
15+
public static void test() {
16+
}
17+
18+
public static int countRangeSum(int[] nums, int lower, int upper) {
19+
return 0;
20+
}
21+
22+
}

0 commit comments

Comments
 (0)