CodeNameEagle
BAN USER- 2of 2 votes
AnswersSort an array which only has 0's and 1's. Do not use count sort.
- CodeNameEagle in India| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm Arrays
Assuming we only have lowercase a-z (We can extend this for all ASCII easily)
Following code has O(n) time and constant space. Space is Actually O(26) which is constant.
public class Test {
public static void printOnceReverse(char[] s) {
if(s.length == 0) return;
boolean[] flag = new boolean[26];
int i;
for(i=0; i<s.length; i++) {
int index = s[i] - 'a';
flag[index] = true;
}
for(i=s.length-1; i>=0; i--) {
int index = s[i] - 'a';
if(flag[index] == true) {
System.out.print(s[i]);
flag[index] = false;
}
}
System.out.println();
}
public static void main(String[] args) {
printOnceReverse("aabdceaaabbbcd".toCharArray());
printOnceReverse("aaaabbcddddccbbdaaeee".toCharArray());
printOnceReverse("aaafffcccddaabbeeddhhhaaabbccddaaaa".toCharArray());
}
}
Let
Array a = {1,2,3,4,5,5}
n = 5
Find the arithmetic sum of n integers n=5 means arithmetic sum=15
Next sum all the elements in array sum=20
missing number = sum - arithmetic sum = 20 - 15 = 5
public class Test {
public static int findRepeat(int[] a) {
int n = a.length-1;
int r1 = n*(n+1)/2;
int sum=0;
for(int i=0;i<=n;i++) {
sum+=a[i];
}
return sum-r1;
}
public static void main(String[] args) {
int[] a = {1,2,3,4,5,5};
System.out.println(findRepeat(a));
}
}
Taking example of some of the real cab systems. Here are things we should think about:
1. There will be a client emitting the location of each car (e.g. a GPS system)
2. There will be a server collecting or updating this data in its system
3. There will be another client asking for information about cabs from the server (e.g. Uber App on my phone)
4. In the end you would need to compute the distance between the points (p,q) and the coordinates (xi,yi) for cab i. This is followed by sorting.
Scenario 1: Let my app (or client) sends a request to the server telling it its coordinates (p,q). The server returns 5 nearest cabs.
Server will need calculate distance for each of the cab that is online from (p,q), followed by sorting and then returning the 5 nearest cabs.
Pros:
1. Client does not have to do much work and since clients are supposed to be light weight, this is good.
2. Server does computation and since servers are supposed to be powerful it can do that.
Cons:
1. Server needs to do computation for all the taxis for every given (p,q). This is lot of computation.
2. Meanwhile client can close the connection or cancel the operation so it sounds like a waste of resources.
Scenario 2: Server sends all cab coordinates to client and client finds the distance, sort it and find 5 closest cabs.
This is opposite of scenario 1.
Pros:
1. Server does not need to compute distance and sort them.
Cons:
1. puts a lot of burden on client. If there are 10000 cabs in the city then it has to find distance with all the cabs.
Scenario 3: Client knows its location (p,q). It asks the server to only send coordinates of cabs that are in 1 KM rectangular area from (p,q). Server sends coordinates and client computes distance for this subset of cabs and sort it.
Pros:
1. Client needs to process a small number of cab data.
2. If client dies or cancels the request then no harm done
3. Server is not computing distances and sorting them.
Cons:
1. What if there are no cabs within 1 KM area from (p,q). In this case we can expand the search.
Client logic should looks something like:
import java.util.Arrays;
public class CabClient {
private CabServer myserver; // assuming there is server class
private static int NumResults = 100;
private static int desiredResults = 5;
public CabClient(CabServer s) {
this.myserver = s;
}
public double[] findnearestcabs(int p, int q) {
int gridSize = 1; // Kilometers or miles
// we are asking for upto 100 cab locations near our vicinity
int[][] result = myserver.getCabCordinatesInGrid(p, q, gridSize, NumResults);
double[] distances = new double[NumResults];
for(int i=0;i<NumResults;i++) {
if(result[i][0] == 0 && result[i][1] == 0) {
continue; // This entry was not filled by server so ignore it
}
double dist = Math.pow(p-result[i][0], 2) + Math.pow(q-result[i][1], 2);
distances[i] = Math.sqrt(dist);
}
Arrays.sort(distances);
double[] retval = new double[desiredResults];
for(int j=0;j<desiredResults;j++) {
// assuming desiredResults < NumResults
retval[j] = distances[j];
}
return retval;
}
}
Server code will look like something
public class CabServer {
// contains x,y
private int[][] coordinatesAllCabs;
private static int numCabs = 10000;
public CabServer() {
coordinatesAllCabs = new int[numCabs][2];
}
private void populateCoordinates() {
// some logic
}
public int[][] getCabCordinatesInGrid(int p, int q, int gridSize, int n) {
int[][] result = new int[n][2];
int index = 0;
int xLeft = p - gridSize;
int xRight = p + gridSize;
int yDown = q - gridSize;
int yUp = q + gridSize;
for(int i =0; i < coordinatesAllCabs.length; i++) {
if(coordinatesAllCabs[i][0] >= xLeft && coordinatesAllCabs[i][0] <= xRight &&
coordinatesAllCabs[i][1] >= yDown && coordinatesAllCabs[i][1] <= yUp) {
result[index++][0] = coordinatesAllCabs[i][0];
result[index++][1] = coordinatesAllCabs[i][1];
}
if(index == n) {
// we only want up to n results
// This could mean that we found n cabs in vicinity but there
// could be other cabs that might be nearer which are not accounted for
// to take care of that we can use a large value of N
break;
}
}
return result;
}
}
1. Find the occurrence of an element using standard binary search
2. If found change the end index to the index of the found element and apply binary search again. Do this until the beginning pointer meets the end.
Complexity should be log(n)
Here is a code
public static int binSearch(int[] a, int beg, int end, int item) {
int mid;
while (beg <= end) {
mid = (beg + end) / 2;
if (a[mid] == item) {
if (beg == end) {
return mid;
} else {
return binSearch(a, beg, mid, item);
}
} else if (item < a[mid]) {
end = mid - 1;
} else {
beg = mid + 1;
}
}
return -1;
}
Here is the java code for dutch national flag problem. Catering this scenario.
The logic is to align 1's to the left and 3's to the right. the 2's will automatically get into their respective positions.
import java.util.Arrays;
public class DutchNationalFlag {
public static void dnf(int[] a, int low, int high) {
int startIndex = 0;
int endIndex = a.length - 1;
int temp;
for (int i = 0; i <= endIndex ;) {
if (a[i] < low) {
temp = a[i];
a[i] = a[startIndex];
a[startIndex] = temp;
i++;
startIndex++;
} else if (a[i] > high) {
temp = a[i];
a[i] = a[endIndex];
a[endIndex] = temp;
endIndex--;
// do not increment i. We have to revisit this again
} else {
i++;
}
}
}
public static void main(String[] args) {
int[] a = new int[] {1,3,2,2,3,1,1,1,3,2,2,1,1};
DutchNationalFlag.dnf(a, 2, 2);
System.out.println(Arrays.toString(a));
}
}
The above statement is not right. the search in sorted array can be O(log(n)) if you use binary search.
- CodeNameEagle May 16, 2013What exactly is your concern? Is is not compiling or has corner cases? This code has a limitation with array that has duplicates. But as far as I know it runs fine with other cases. I am pasting a complete running code for your reference. Let me know what are your concerns.
package arraysandstrings;
public class RotateArrayResetPoint {
public static int findNumRotation(int[] a) {
if (a.length <= 1) {
return 0;
}
int beg = 0, end = a.length - 1, mid, temp, index;
temp = a[0];
index = 0;
while (beg <= end) {
mid = (beg + end) / 2;
if (a[mid] < temp) {
temp = a[mid];
index = mid;
}
if (a[mid] <= a[end]) {
end = mid - 1;
} else {
beg = mid + 1;
}
}
return index;
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a = new int[] { 15, 18, 19, 21, 23, 2, 4, 6, 8, 9, 12 };
System.out.println(RotateArrayResetPoint.findNumRotation(a));
}
}
[Assumption: Array has unique elements. I am working on a generic solution.]
The following is a hybrid of Binary Search and selection sort select logic. To summarize I can do this if I can find the index of the minimum element in the sorted array. For example
1 2 3 4 5 - Original Sorted Array
5 1 2 3 4 - 1 Rotate (Notice index of the minimum element is 1)
4 5 1 2 3 - 2 Rotate (Notice index of the minimum element is 2)
3 4 5 1 2 - 3 Rotate (Notice index of the minimum element is 3)
2 3 4 5 1 - 4 Rotate (Notice index of the minimum element is 4)
1 2 3 4 5 - 5 rotate or no rotate (Notice index of the minimum element is 0)
For number of rotations >= array length lets assume it was never rotated
When I say selection sort, I mean the way you find the min/max in the unsorted array and update its position. In our case the array is sorted but rotated. We can choose which direction my min is going to be by using binary search like logic and eliminating half of the entries each time.
Here is a code that can find this in O(log(n)) for you.
public static int findNumRotation(int[] a) {
if (a.length <= 1) {
return 0;
}
int beg = 0, end = a.length - 1, mid, temp, index;
temp = a[0];
index = 0;
while (beg <= end) {
mid = (beg + end) / 2;
if (a[mid] < temp) {
temp = a[mid];
index = mid;
}
if (a[mid] <= a[end]) {
end = mid - 1;
} else {
beg = mid + 1;
}
}
return index;
}
1. If the node has right child. then return leftmost child of the right subtree.
2. Else if node is the left child of its parent then return its parent
3. Else go up to the parent until you find a node that is a left child of its parent. Return the parent.
4. Return null
Here is the code
public TreeElement findNextLargest(TreeElement n) {
if (n == null) {
return null;
}
TreeElement parent = n.parent;
TreeElement temp;
if (n.right != null) {
temp = n.right;
while (temp.left != null) {
temp = temp.left;
}
return temp;
} else if (parent != null && n == parent.left) {
return parent;
} else {
temp = n;
while (parent != null) {
if (temp == parent.left) {
return parent;
}
temp = parent;
parent = parent.parent;
}
}
return null;
}
I described this option but the interviewer was not that happy about it. But this is a good approach. I think he wanted me to pre process the dictionary may be. Not sure though.
- CodeNameEagle May 13, 2013I think you might be onto something. I thought about this but forgot to ask my interviewer. He did mention doing some computations initially so that its easier to find anagrams.
- CodeNameEagle May 13, 2013Assuming its large enough. Not sure what the interviewer was expecting though. I told him about length of words, Starting alphabet matching etc but he was not satisfied.
He stressed about the fact that not every word should be processed from the dictionary.
This is a modified version of reversing a doubly linked list. At the end we traverse back to the beginning to update the head node.
public void swapPairsInList(Node head) {
if (head == null || head.next == null) {
return; // 0 or 1 node
}
Node p;
Node q;
Node r = head;
while (r != null && r.next != null) {
p = r;
q = r.next;
r = q.next;
q.prev = p.prev;
if (p.prev != null) {
p.prev.next = q;
}
p.prev = q;
p.next = q.next;
if (q.next != null) {
q.next.prev = p;
}
q.next = p;
}
while(p.prev != null) {
p = p.prev;
}
this.head = p;
}
We could use heap for this, though I am concerned about the maximum size of heap in worst case. Here is some code (which assume a heap data structure exists). You can use priority queue in Java to implement this.
If we use checkin and checkout operations alternatively, then heap size will be zero. In worst case when we check out 1..N and then start checking in numbers < N then heap size can reach upto N-1
private long value = 1;
private Heap h = new Heap();
public long checkout() {
// We want the next number in the sequence
if(h.size() == 0) {
this.value++;
return value - 1;
} else {
// return the minimum value from heap
return h.removeRoot();
}
}
public void checkin(long val) {
// Checkin the previous number that was checkedout
if(val == this.value - 1) {
this.value--;
} else {
// insert into heap as its not in the sequence
h.add(val);
}
}
We can do this by modifying the original BST.
1. Do a post order traversal of the tree.
2. For each node:
If its value is less than min or greater than max delete the node.
We can do this in O(n) time and O(1) space if each node has a reference to its parent.
Also by the time we reach a node, the node only has 0 or 1 child. So deletion is straight forward.
Here is some code to get you started. The deletion routine can be further reduced and optimized.
public void postOrder(TreeElement root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
if (root.data < this.MIN || root.data > this.MAX) {
System.out.println("delete " + root.data);
delete(root);
}
}
public void delete(TreeElement root) {
TreeElement parent = root.parent;
if(parent == null) {
if(root.left != null) {
this.root = root.left;
} else {
this.root = root.right;
}
return;
}
if (root.left == null && root.right == null) {
if (root == parent.left) {
parent.left = null;
} else {
parent.right = null;
}
} else if (root.left == null) {
if (root == parent.left) {
parent.left = root.right;
} else {
parent.right = root.right;
}
} else if(root.right == null) {
if (root == parent.left) {
parent.left = root.left;
} else {
parent.right = root.left;
}
} else {
// Should not happen
}
}
Nice solution man.
- CodeNameEagle May 08, 20131. Create a hash from the string
2. Sort the hash
3. Return the character from the entry num-1 in this sorted array
Time complexity: O(m) + O(nlog(n)) where m is size of string and n is size of hash table/array
Space: O(n) where n is size of hash array
The implementation is Java specific but can be done in other languages
Instead of using char[] as hashMap we can use an array of HashElem[] as the hash where HashElem is
public class HashElem {
public char elem;
public int count;
public HashElem(char c, int count) {
this.elem = c;
this.count = count;
}
}
Now we can initialize this hash using the characters of the original string as index. Next step is to sort this hash (which is actually an array) based on the count or individual characters and if counts are same based on the character ascii value. I have overridden the standard comparator interface. Here is a sample code to get you started:
import java.util.Arrays;
import java.util.Comparator;
public class MostCommonChar {
public class HashElem {
public char elem;
public int count;
public HashElem(char c, int count) {
this.elem = c;
this.count = count;
}
}
public class MyComparator implements Comparator<HashElem> {
@Override
public int compare(HashElem o1, HashElem o2) {
int result = 0;
if (o1 == null && o2 == null) {
result = 0;
} else if (o1 == null) {
result = 1;
} else if (o2 == null) {
result = -1;
} else if (o1.count != o2.count) {
result = o2.count - o1.count;
} else if (o1.elem != o2.elem) {
result = o2.elem - o1.elem;
}
return result;
}
}
private HashElem[] h = new HashElem[256];
public char findMostCommonChar(String str, int k) {
if (k <= 0 || k > str.length()) {
return 0;
}
int i;
char index;
for (i = 0; i < 255; i++) {
h[i] = null;
}
for (i = 0; i < str.length(); i++) {
index = str.charAt(i);
if (h[index] == null) {
h[index] = new HashElem(index, 1);
} else {
h[index].count++;
}
}
Arrays.sort(h, new MyComparator());
return h[k - 1] == null ? 0 : h[k - 1].elem;
}
public static void main(String[] args) {
String s = "aabra ka daabra";
MostCommonChar m = new MostCommonChar();
System.out.println(m.findMostCommonChar(s, 1));
System.out.println(m.findMostCommonChar(s, 2));
System.out.println(m.findMostCommonChar(s, 3));
System.out.println(m.findMostCommonChar(s, 4));
System.out.println(m.findMostCommonChar(s, 5));
System.out.println(m.findMostCommonChar(s, 6));
}
}
// output: a r b <space> k d
- CodeNameEagle May 04, 2013Assumption for 1 digit per node
Time O(n)
SpaceO(1)
This will work for different length lists as well
public class SumTwoList2 {
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
// traverse through the list to find the size
private int size(Node head) {
Node temp = head;
int len = 0;
while (temp != null) {
len++;
temp = temp.next;
}
return len;
}
public Node addLists(Node head1, Node head2) {
// if either of the lists are empty then take appropriate action
if (head1 == null && head2 == null) {
return null;
} else if (head1 == null) {
return head2;
} else if (head2 == null) {
return head1;
}
Node result = null;
int l1 = size(head1);
int l2 = size(head2);
int len = 0;
int i;
// start pushing the bigger list items on the stack
if (l1 > l2) {
len = l2;
for (i = 0; i < l1 - l2; i++) {
Node n = new Node(head1.data);
head1 = head1.next;
n.next = result;
result = n;
}
} else if (l1 < l2) {
len = l1;
for (i = 0; i < l2 - l1; i++) {
Node n = new Node(head2.data);
head2 = head2.next;
n.next = result;
result = n;
}
}
// Now both lists are same length
for (i = 0; i < len; i++) {
Node n = new Node(head1.data + head2.data);
head1 = head1.next;
head2 = head2.next;
n.next = result;
result = n;
}
int sum = 0, carry = 0;
Node ptr = result;
// adjust the carry and forward it to next node
while(ptr != null) {
sum = ptr.data;
ptr.data = sum%10 + carry;
carry = sum / 10;
ptr = ptr.next;
}
// if a carry exists we need another node to put this
if (carry != 0) {
Node n = new Node(carry);
n.next = result;
result = n;
}
reverse(result);
return result;
}
public void reverse(Node head) {
if(head == null || head.next == null) {
return;
}
Node p = head;
Node q = head.next;
Node r = null;
while(q != null) {
r = q.next;
q.next = p;
p = q;
q = r;
}
head.next = null;
head = p;
}
}
Can we use a linked list to represents digits of the integer? If yes then this problem can be transformed into sum of two linked lists. If we want to make this more efficient then instead of storing one digit per node we can store n bytes per node. We just need to make sure that the sum and carry are propagated properly.
- CodeNameEagle May 03, 2013Assumption: All the coins have different values. If we have coins with same value then we will start getting duplicate results.
To me this problem looks like finding the combination of the coins and checking if that combination's total is the value we want to compute. So I can extend the find combinations algorithm to do this.
Here is a recursive solution:
public class Change {
public static int makeChange(int[] coins, int change, int start) {
int numWays = 0;
for (int i = start; i < coins.length; i++) {
if (change - coins[i] == 0) {
numWays++;
continue;
}
if (i < coins.length) {
numWays+= makeChange(coins, change - coins[i], i + 1);
}
}
return numWays;
}
public static void main(String[] args) {
int[] input = new int[]{1,2,3,4};
System.out.println(Change.makeChange(input, 4, 0));
}
}
Thanks f2003062, I really do not remember how I missed that. Its so basic. Thanks for the correction. I have fixed it now.
- CodeNameEagle May 01, 2013How about the following logic then:
1. Create another list which is the result of two lists in first pass. The next result is always put in front of the previous result.
2. Adjust the sum and carry in next pass
3. Reverse the adjusted linked list
Time O(n)
SpaceO(1)
This will work for different length lists as well
public class SumTwoList2 {
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
// traverse through the list to find the size
private int size(Node head) {
Node temp = head;
int len = 0;
while (temp != null) {
len++;
temp = temp.next;
}
return len;
}
public Node addLists(Node head1, Node head2) {
// if either of the lists are empty then take appropriate action
if (head1 == null && head2 == null) {
return null;
} else if (head1 == null) {
return head2;
} else if (head2 == null) {
return head1;
}
Node result = null;
int l1 = size(head1);
int l2 = size(head2);
int len = 0;
int i;
// start pushing the bigger list items on the stack
if (l1 > l2) {
len = l2;
for (i = 0; i < l1 - l2; i++) {
Node n = new Node(head1.data);
head1 = head1.next;
n.next = result;
result = n;
}
} else if (l1 < l2) {
len = l1;
for (i = 0; i < l2 - l1; i++) {
Node n = new Node(head2.data);
head2 = head2.next;
n.next = result;
result = n;
}
}
// Now both lists are same length
for (i = 0; i < len; i++) {
Node n = new Node(head1.data + head2.data);
head1 = head1.next;
head2 = head2.next;
n.next = result;
result = n;
}
int sum = 0, carry = 0;
Node ptr = result;
// adjust the carry and forward it to next node
while(ptr != null) {
sum = ptr.data;
ptr.data = sum%10 + carry;
carry = sum / 10;
ptr = ptr.next;
}
// if a carry exists we need another node to put this
if (carry != 0) {
Node n = new Node(carry);
n.next = result;
result = n;
}
reverse(result);
return result;
}
public void reverse(Node head) {
if(head == null || head.next == null) {
return;
}
Node p = head;
Node q = head.next;
Node r = null;
while(q != null) {
r = q.next;
q.next = p;
p = q;
q = r;
}
head.next = null;
head = p;
}
}
We can do this recursively or by using stack. I choose the latter. I am using a Stack of Integers. The following code will take care of the case where two lists are unequal length.
1. Start putting the integer value of each node of the bigger list on stack until the length of two lists become equal.
2. Start adding the values of data from two lists. At this point do not care about carry and just add them and push onto the stack.
3. Start popping values out of stack and putting them in newly created linked list node. You need to adjust the values by doing sum%10 and carry = sum/10. Use this carry for the next popped out entry. Every node that you create, put it in the front of the list.
NOTE: We might be able to get rid of the stack if we just add the two list and put them in a third list. Then adjust the third list for carry propagation and in the end reverse it. In this case time=O(n) auxiliary space O(1)
But even the stack approach should not be worse than the recursive way.
Here is a code to get you started:
package linkedlist;
import java.util.Stack;
public class SumTwoList {
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
// traverse through the list to find the size
private int size(Node head) {
Node temp = head;
int len = 0;
while (temp != null) {
len++;
temp = temp.next;
}
return len;
}
public Node addLists(Node head1, Node head2) {
// if either of the lists are empty then take appropriate action
if (head1 == null && head2 == null) {
return null;
} else if (head1 == null) {
return head2;
} else if (head2 == null) {
return head1;
}
Node result = null;
Stack<Integer> s = new Stack<Integer>();
int l1 = size(head1);
int l2 = size(head2);
int len = 0;
int i;
// start pushing the bigger list items on the stack
if (l1 > l2) {
len = l2;
for (i = 0; i < l1 - l2; i++) {
s.push(head1.data);
head1 = head1.next;
}
} else if (l1 < l2) {
len = l1;
for (i = 0; i < l2 - l1; i++) {
s.push(head2.data);
head2 = head2.next;
}
}
// Now both lists are same length push the sum on the stack
for (i = 0; i < len; i++) {
s.push(head1.data + head2.data);
}
int sum = 0, carry = 0;
// start popping the sum and adjusting the sum carry values and put it in a new list
while (s.isEmpty() == false) {
sum = s.pop() + carry;
Node n = new Node(sum % 10);
n.next = result;
result = n;
carry = sum / 10;
}
// if a carry exists we need another node to put this
if (carry != 0) {
Node n = new Node(carry);
n.next = result;
result = n;
}
return result;
}
}
What will we do when input is like abcd then out put should be a1b1c1d1. In this case we would require to expand the existing array. If we choose not to compress such strings then following should work:
package array;
public class RLC {
public static int rlc(char[] a) {
if (a.length == 0) {
return -1;
}
char elem = a[0];
int elemCount = 1;
int j = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] == elem) {
elemCount++;
} else {
if (j + 1 == i) {
System.out.println("Error: Can not compress");
return - 1;
}
a[j] = elem;
a[j + 1] = (char) elemCount;
j = j + 2;
elemCount = 1;
elem = a[i];
}
}
if (j + 1 < a.length) {
a[j] = elem;
a[j + 1] = (char) elemCount;
j += 2;
}
return j - 1;
}
}
Here is an O(nk) solution. But this is obvious solution. I am looking for more efficient solution.
package array;
import java.util.Arrays;
public class MaxEachSub {
public static int[] findMax(int[] a, int k) {
if (k > a.length) {
return new int[] { Integer.MIN_VALUE };
}
int[] output = new int[a.length - k + 1];
for (int i = 0; i <= a.length - k; i++) {
output[i] = max(a, i, i + k - 1);
}
return output;
}
private static int max(int[] a, int beg, int end) {
int max = a[beg];
for (int i = beg + 1; i <= end; i++) {
if (a[i] > max) {
max = a[i];
}
}
return max;
}
}
We could use Graph Transitive closure property. Which says if A is friends with B and B is friends with C, then A is friends with C. C would be our suggestion to the user. We can come u with a Connection Adjecency Matrix which can be written as
Connec[i][j] = Connection[i][j] | (Connect[i][k] && Connect[k][j])
For a user I we can suggest all the connections J which are already not in its list.
This is another recursive approach but does not use any min max variables.
The approach is
1. Figure out if the current node is following BST rule which is left.data <= root.data <= right.data
2. Now do this for left child and right child and return the result of steps 1 & 2
public boolean isBST(TreeElement root) {
if (root == null || (root.left == null && root.right == null)) {
return true;
}
boolean result = true;
if ((root.left != null && root.left.data > root.data)
|| (root.right != null && root.right.data < root.data)) {
result = false;
}
return result && isBST(root.left) && isBST(root.right);
}
The fact that k << n. Implies to me that instead of using hash map, I can use an int array of size k. This will be faster and efficient than using hash map although the logic is same.
Also if I have all the values [1,K] present in the array. I do not have to go till the end of this large array. I can count the number of unique entries and break as soon as I see that I have information for all K elements. This will save a lot of time. But if all the values are not present in the array then we have to go till the end.
Here is a sample code
package array;
import java.util.Arrays;
public class FindIndex {
public static int[] findIndex(int[] a, int k, int z) {
int[] result = new int[]{-1, -1};
if(a.length == 0 || z > 2 * k) {
return result;
}
int[] aux = new int[k];
int numElem = 0, i, j;
for(j = 0; j < aux.length; j++) {
aux[j] = -1;
}
for(i = 0; i < a.length; i++) {
if(aux[a[i] - 1] == -1) {
aux[a[i] - 1] = i;
numElem++;
}
if(numElem == k) {
// no need to traverse anymore. We have got all positions.
break;
}
}
System.out.println(Arrays.toString(aux));
int val;
for(i = 0; i < k; i++) {
if(aux[i] != -1) {
val = z - i - 1;
if(val > k) {
continue;
}
if(aux[val - 1] != -1) {
result[0] = aux[i];
result[1] = aux[val - 1];
return result;
}
}
}
return result;
}
public static void main(String[] args) {
int a[] = new int[]{1,5,2,4,3,5,4,3,2,1,1,3,2,4,5};
int z = 4;
int k = 5;
int[] result = FindIndex.findIndex(a, k, z);
System.out.println("The indices are "+ result[0] + " " + result[1]);
}
}
@nr
That's a valid point. You see in the constructor above I check
if (isDir == true)
this.subfiles = new ArrayList<file>();
So in the add routine if you check the existence of subfiles member before adding, you are good to go.
It actually depends on how you want to add a file. I assumed that I am already supplying parent directory.
@nishantfirst
The question clearly says that only multiple * are allowed as long as they are consecutive. Your input string does not match the requirement.
Here is an iterative solution. Complexity O(n)
Algorithm:
1. If the pattern starts with '*', start matching from the back until you hit the '*' and return result
2. If the pattern ends with '*' start matching from the beginning until you hit the * and return result
3. Perform 1 and 2 simultaneously and return result.
package stringalgos;
public class MyRegex {
public static boolean matchPattern(char[] pattern, char[] input) {
if (pattern.length == 0 || input.length == 0) {
return false;
}
if (pattern[0] == '*') {
return matchFromBack(pattern, input);
} else if (pattern[pattern.length - 1] == '*') {
return matchFromBeginning(pattern, input);
} else {
return (matchFromBeginning(pattern, input) && matchFromBack(
pattern, input));
}
}
public static boolean matchFromBeginning(char[] pattern, char[] input) {
boolean result = true;
int i, j;
for (i = 0, j = 0; i < input.length && j < pattern.length; i++, j++) {
if (pattern[j] == '*') {
return result;
} else if (pattern[j] != input[i]) {
result = false;
return result;
}
}
// input string did not finish
if (i != input.length) {
result = false;
}
return result;
}
public static boolean matchFromBack(char[] pattern, char[] input) {
boolean result = true;
int i, j;
for (i = input.length - 1, j = pattern.length - 1; i >= 0 && j >= 0; i--, j--) {
if (pattern[j] == '*') {
return result;
} else if (pattern[j] != input[i]) {
result = false;
return result;
}
}
// input string did not finish
if (i >= 0) {
result = false;
}
return result;
}
public static void main(String[] args) {
String pattern = "a*b";
String input = "acb";
System.out.println(MyRegex.matchPattern(pattern.toCharArray(),
input.toCharArray()));
pattern = "abc*";
input = "abbc";
System.out.println(MyRegex.matchPattern(pattern.toCharArray(),
input.toCharArray()));
pattern = "**bc";
input = "bc";
System.out.println(MyRegex.matchPattern(pattern.toCharArray(),
input.toCharArray()));
}
}
@nr that is a very interesting question. I did not thought about it that much when I was writing my class because I was trying to imitate a file system. But now that I think of it, every file can have a default permission of -rw-rw-r-- (similarly directory can have a default of drw-rw-r). This is because root and the current user have read write permissions. Secondly you can code a chmod function that can manipulate this boolean array. if you say chmod (file, 777) it should change the boolean permission array of the file to 0111111111 (0 means its a file) or in other words -rwxrwxrwx
- CodeNameEagle April 22, 2013@nr Sorry for replying as anonymous. I thought I was logged into my account. The above reply was mine.
- CodeNameEagle April 22, 2013A file system can be represented with a Tree data structure. We can have one class called file (a directory is also a file). This class can track its current directory, its parent directory and files in this directory (in case this file is a special file called directory). Then we can create a class to manage file system which is manipulating the nodes of the tree.
This is a bare minimum code to get you started.
package filesystem;
import java.util.ArrayList;
import java.util.Date;
public class FileSystem {
public class file {
private String name;
private long size;
private Date timeStamp;
private file currentDir;
private file parentDir;
// a directory is also a file containing reference to other files
private boolean isDirectory;
public ArrayList<file> subfiles;
// Advanced class members if required
private boolean[] permissions;
private String owner;
private String group;
public file(String name, file currentDir, boolean isDir) {
this.name = name;
this.currentDir = currentDir;
this.timeStamp = new Date();
this.isDirectory = isDir;
this.size = 0; // initial size
this.parentDir = currentDir.getParentDirectory();
if (isDir == true)
this.subfiles = new ArrayList<file>();
}
public void updateTimeStamp() {
this.timeStamp = new Date();
}
public file getParentDirectory() {
return this.parentDir;
}
public void rename(String name) {
this.name = name;
}
}
private file root; // root folder
public FileSystem() {
// every file system should have a root folder
this.root = new file("root", null, true);
}
public void createFile(String name, file curDir, boolean isDir) {
file f = new file(name, curDir, isDir);
curDir.subfiles.add(f);
}
}
This solution is iterative and has complexity O(n*2^n). But uses constant memory. The logic is to flip entries every time based on the position of the entry and the iteration number.
package array;
import java.util.Arrays;
public class TruthTable {
public static void printTruthTable(int n) {
if (n == 0) {
return;
}
char[] output = new char[n];
double[] coeff = new double[n];
int i, j;
double numResults = Math.pow(2, n);
for (i = 0; i < n; i++) {
output[i] = 'T';
coeff[i] = Math.pow(2, n - i - 1);
}
for (i = 1; i <= numResults; i++) {
System.out.println(Arrays.toString(output));
for (j = 0; j < n; j++) {
if (i % coeff[j] == 0) {
flip(output, j);
}
}
}
}
private static void flip(char[] output, int j) {
if(output[j] == 'T') {
output[j] = 'F';
} else {
output[j] = 'T';
}
}
public static void main(String[] args) {
System.out.println("n=0");
TruthTable.printTruthTable(0);
System.out.println("n=1");
TruthTable.printTruthTable(1);
System.out.println("n=2");
TruthTable.printTruthTable(2);
System.out.println("n=3");
TruthTable.printTruthTable(3);
}
}
Not necessarily.
1. Here its a string matching situation rather than character
2. You might end up shrinking the original string in case the pattern to be replaced is longer than the new pattern (e.g. BC -> U). In this case you have to start from the beginning of the original array. Whereas in expansion starting from the back is efficient
Can you please explain this with an example?
- CodeNameEagle April 17, 2013Assumptions
1. If the file is really large
2. The sequence to be searched is very small as compared to the size of the file
We can create a hashMap of strings that has all the permutations of the anagram to be searched. The complexity of this would be O(m!) where m is the size of the anagram to be searched. Once we have such a hashMap, we can read every word from the file and check it in the map. The search complexity would be O(1).
Total complexity = O(n) + O(m!) where n is the size of the file(or the count of words in the file) and m is the size of the anagram to be searched
Space complexity = O(m!) --> size of hash map
This method should work well as long as n >> m
Example: If file has 1000 words and we need to search TOP whose length is 3. Then the number of entries in the hash map should be 6.
The Following code gives the leftmost/ right most occurrence of an element.
#define NOT_IN_ARRAY -1
#define ARRAY_UNORDERED -2
#define ARRAY_EMPTY -3
//leftright = 0 find start limit leftright = 1 find end limit
int binarySearch(int * array, int beg, int end, int data, char leftright)
{
int mid;
if(array == NULL) return ARRAY_EMPTY;
int position = NOT_IN_ARRAY;
while(beg <= end)
{
mid = (beg + end)/2;
if(array[beg] > array[end]|| array[mid] > array[end])
return ARRAY_UNORDERED;
if(data == array[mid])
{
position = mid;
if(leftright)
{
beg = mid + 1;
}
else
{
end = mid - 1;
}
}
else if(data < array[mid]) end = mid - 1;
else if(data > array[mid]) beg = mid + 1;
else;
}
return position;
}
- CodeNameEagle July 15, 2016