Achilles
BAN USER- 0of 0 votes
AnswersGiven a 10GB file of integers and a RAM that can hold only 4GB values, how would you sort the integers in the file.
- Achilles in United States| Report Duplicate | Flag | PURGE
Vdopia Algorithm - 0of 0 votes
AnswersGiven a binary tree print all the nodes that lie in a vertical line. So say the binary tree is root 11 -> left child 2 and right child is 15. 2 has left child 10 and right child 1 and 15 has left child 6 and right child 7.
- Achilles in United States
The output will be
10
2
11,1,6
15
7
The tree is drawn in such a way that from a node, if a left and a right traversal is done, the node lies in the vertical line with the grand parent.| Report Duplicate | Flag | PURGE
Vdopia Algorithm - 0of 0 votes
AnswersGiven a m x n array that contains integers (positive and negative) find the rectangular sub array for which the sum of elements is maximum i.e. from all the sub arrays that can be formed from the given array, the sum of which sub array is the maximum.
- Achilles in United States
The brute force method takes O(n^4), is there any better way to do this?| Report Duplicate | Flag | PURGE
Vdopia Algorithm
I don't know about C++ but Java provides the same "java.util.Deque" in two classes, one using an array and the other using a linked list. Also, refer to Data Structure in Java by Goodrich and Tamasia, they have also provided the implementation using LinkedList.
LinkedList may not be the ideal candidate for Deque but is definitely one of the best amongst the known data structures.
A Deque is a doubly ended queue, that allows insertion and deletion at both the ends.This can be implemented by using a doubly linked list with all the operations in O(1).
Implementation can very easily be provided as follows by creating two extra empty nodes header and tailer pointing to each other at the start. Manipulate the pointers for adding and deleting.
@vinay :- We can calculate the last D digits of any exponential by modular exponential method, i.e. b^e mod (10^d) would give me the last d digits of b^e in O(lg e).
Here, what I am trying to do is to find the last d digits of N^N where d is number of digits in K/N (don't know yet how to calculate this), which I am matching with the last d digits of K.
Doing this recursively, dividing K and N^N with N and then finding the digits in N^(N-1) and matching the same, till all digits are matched.
Though there are things that need to be added to make it complete, but I think it should make the idea clear.
We can find the last k digits in binary using modular exponential method.
Algorithm :-
Match the digits of N^N mod 10^(number of digits of (K) - number of digits of (K/N)) with the same number of digits of K.
Make K = K/N.
Match the digits of N^(N-1) mod 10^(number of digits of (K) - number of digits of (K/N)) with the same number of digits of K.
Do this recursively till the exponential reduces to 0.
In the worst case when the numbers are equal all the numbers are required to be matched.
The finding of number of digits in K/N still needs to be figured out without doing the actual division.
Without using catalan number :
Let A[] contain the nodes in sorted order.
int numberOfTrees(int[] A, int start, int end) {
int count;
if (start == end) return 0; //0 nodes
if (start+1 == end) return 1; //1 node
if (start+2 == end) return 2; //2 nodes
for (int i = start; i < end; i++) {
int left += numberOfTrees(A, 0, start);
int right += numberOfTrees(A,start+1, A.length);
count += left*right;
}
return count;
}
number of trees can be known by calling numberOfTrees(A,0,A.length)
The array has been taken in sorted order, so that the binary search trees are formed, which will be different in all the cases, and hence there would be no overlapping of structurally same binary trees and at the same time, take into
The size of the table would be 60*60*24. Generating such a hash table would be very costly. We can reduce the cost by maintaining a hashtable of the entries based on 15 mins or 30 mins. When the number of people are to be obtained then the values can be iterated to find the exact number.
- Achilles June 03, 2012If we were to call the function multiple times it would be better to create a BST based on the exit time (or entry time). Each node would keep the other value saved as well.
For the input time we can do a search for the input time and then count the number of people inside in the sub tree.
The entry time will be in ascending order. Assuming that the exit time can be in any order, i.e. the first person to enter is not the first one to exit.
Iterate over the indexes till the entryTime > inputTime. Increase count whenever entryTime < inputTime < exitTime
int CountPeople (Calendar inputTime) {
int peopleInside = 0;
BufferedReader br = new BufferedReader(new FileReader("filePath"));
String line;
try {
while ((line = br.readLine() )!=null) {
Calendar entryTime = Calendar.getInstance();
String entryTimeInString = line.subString(0, line.indexOf(" "));
//fill the time in entryTime using entryTimeInString
if (entryTime.after(inputTime) {
break;
}
Calendar exitTime = Calendar.getInstance();
String exitTimeInString = line.subString(line.indexOf(" ") + 1, line.length());
//fill the time in exitTime using exitTimeInString
if (exitTime.after(inputTime) {
peopleInside++;
}
} catch (IOExecption e) {
e.printStackTrace();
}
return peopleInside;
}
Using Kdane's algorithm it can be done in O(n) and O(k) space.
func(int[] a) {
int startIndex=-1,endIndex=-1,maxEndingHere=0,maxSoFar=0;
int tempStartIndex=-1,tempEndIndex=-1;
for (int i=0;i<a.length;i++) {
//finding the maximum sum of all arrays that end at i
if (a[i] >= maxEndingHere+a[i]) {
tempStartIndex=tempEndIndex=i;
maxEndingHere = a[i];
} else {
tempEndIndex=i;
maxEndingHere = maxEndingHere+a[i];
}
//The maximum sum so far will be the sum of all the subarrays considered so far or all the
// sub arrays ending at this position.
if (maxEndingHere >= maxSoFar) {
startIndex = tempStartIndex;
endIndex = tempEndIndex;
maxSoFar = maxEndingHere;
}
}
return startIndex,endIndex;
}
public class LifeCycle implements Runnable {
int state = 0;
public void run() {
while (true)
if (state = 0) {
System.out.println("Running from Ready");
state = 1;
}
else
System.out.println("Running from Waiting");
}
public static void main(String[] args) {
LifeCycle c = new LifeCycle();
Thread t = new Thread(c);
t.run();
}
}
//This is the super interface for all the watches
public interface Watch{
public void incrementHour(int hour);
public void incrementMinutes(int min);
public void incrementSec(int sec);
}
public interface DigitalWatch extends Watch {
public void setMode(Mode mode); //Mode refers to 24 hour format or 12 hour format
}
//Implementation can easily be written
Test cases :-
1) Boundary conditions
2) Switching from one mode to the other.
public void changePassword(String userId, String oldPassword, String password, Connection conn) {
StringBuilder str = new StringBuilder();
sbr.append("Update table set password = :pass where userId = :user and password = :oldPass");
PreparedStatement psmt = conn.prepareStatement("Update table set password = :pass where userId = :user and password = :oldPass");
psmt.setString("pass",password);
psmt.setString("user",userId);
psmt.setString("oldPass",oldPassword);
int out = psmt.executeUpdate();
if (out == 1)
//successful
else
//unsuccessful
}
It can be solved in O(m^2 * n^2) which I mentioned as O(n^4) as follows :-
Iterate over the sub-array from 1 to n
Iterate over the sub-array from 1 to m
iterate over the rows
iterate over the columns
In the above 4 iterations all the possible sub-arrays can be covered. which is O(n^4).
Finding the largest 2 elements may not solve the problem. As we have to add all the elements of the sub-array, hence the two largest may contain a very low element, which could make it lesser than the individual sub-array.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class Platter{
static int globalTime = 1;
static boolean moveForward = true;
static int head = 1;
public static void main(String[] args) {
int numberOfPlatters = 3;
int finalTime = 53;
List<Request> inputList = new ArrayList<Request>();
inputList.add(new Request(2,3,50));
inputList.add(new Request(51,1,2));
inputList.add(new Request(1,1,3));
inputList.add(new Request(51,1,2));
inputList.add(new Request(1,2,80));
inputList.add(new Request(2,2,5));
inputList.add(new Request(2,2,1));
Map<Integer, Integer> resultSet = new HashMap<Integer, Integer>();
List<Request> requestList = new ArrayList<Request>();
Collections.sort(inputList, new Comparator<Request>() {
@Override
public int compare(Request o1, Request o2) {
return o1.timeOfArrival - o2.timeOfArrival;
}
});
for (int j=1; j <= finalTime; j++) {
if (!inputList.isEmpty() && finalTime >= inputList.get(0).timeOfArrival ){
Request first = inputList.remove(0);
Platter.globalTime = first.timeOfArrival;
boolean requestProcessed = false;
requestList.add(first);
while (!requestProcessed && !inputList.isEmpty()) {
Request req = inputList.get(0);
if (req.timeOfArrival <= globalTime) {
requestList.add(inputList.remove(0));
} else {
requestProcessed = true;
}
}
}
for(Iterator <Request> iter =requestList.iterator();iter.hasNext();) {
Request request = iter.next();
if (request.trackNumber == head) {
Integer plat = resultSet.get(request.platterNumber);
if (plat==null) {
plat = 1;
} else {
plat++;
}
resultSet.put(request.platterNumber, plat);
iter.remove();
}
}
int trackNumber = 0;
for (Request request : requestList) {
int minRequest = 9999;
if (Math.abs(Platter.head- request.trackNumber) < minRequest) {
minRequest = Math.abs(Platter.head-request.trackNumber);
trackNumber = request.trackNumber;
}
if (Math.abs(Platter.head-request.trackNumber) == minRequest) {
if ((moveForward && Platter.head < request.trackNumber) || (!moveForward && Platter.head > request.trackNumber)) {
minRequest = Math.abs(Platter.globalTime-request.trackNumber);
trackNumber = request.trackNumber;
}
}
}
if (trackNumber == 0) {
continue;
}
if (trackNumber > Platter.head) {
Platter.head++;
moveForward = true;
} else if (trackNumber < Platter.head) {
Platter.head--;
moveForward = false;
}
}
printVals(resultSet);
}
private static void printVals(Map<Integer, Integer> resultSet) {
for (Map.Entry<Integer, Integer> iter : resultSet.entrySet()) {
System.out.println(iter.getKey() + " " + iter.getValue());
}
}
private static class Request {
int timeOfArrival;
int platterNumber;
int trackNumber;
public Request(int timeOfArrival, int platterNumber, int trackNumber) {
this.timeOfArrival = timeOfArrival;
this.platterNumber = platterNumber;
this.trackNumber = trackNumber;
}
}
}
Modifications for input reading and check on the track number can be added.
public class BST{
public Integer value = null;
public BST left = null;
public BST right = null;
public static void main(String[] args) {
int[] base = {1, 3, 2, 4};
int[] alternative = {1, 3, 4, 2};
BST root = createBST(base);
BST alter = createBST(alternative);
System.out.println(checkIfBSTEqual(root,alter));
printDepthDifference(root,alter);
}
private static boolean checkIfBSTEqual(BST root, BST alter) {
if (root == null && alter == null) {
return true;
} else if (root == null && alter != null) {
return false;
} else if (root != null && alter == null) {
return false;
} else return (checkIfBSTEqual(root.left,alter.left) && checkIfBSTEqual(root.right,alter.right));
}
private static void printDepthDifference(BST root, BST alter) {
int depth = findDepth(root);
int depth2 = findDepth(alter);
System.out.println(depth2 - depth);
}
private static int findDepth(BST root) {
int left = 1;
int right = 1;
if (root.left != null) {
left = findDepth(root.left);
}
if (root.right != null) {
right = findDepth(root.right);
}
return Math.max(left, right);
}
private static BST createBST(int[] base) {
BST root = new BST();
root.value = base[0];
for (int i = 1; i < base.length; i++) {
BST temp = root;
int val = base[i];
boolean pos = false;
while (!pos) {
if (val > temp.value) {
if (temp.right !=null) {
temp = temp.right;
} else {
BST newBST = new BST();
newBST.value = val;
temp.right = newBST;
pos = true;
}
} else {
if (temp.left !=null) {
temp = temp.left;
} else {
BST newBST = new BST();
newBST.value = val;
temp.left = newBST;
pos = true;
}
}
}
}
return root;
}
}
Space is O(1) as no extra space is required to merge the two sorted lists.
- Achilles February 19, 2013Remove the elements from the original list and add them to the sorted list.
E.g. 1-3-5 and 2-4 can be merged by moving 1 to the head of new list (3-5, 2-4) remain. Then add 2 making the sorted list 1-2 (3-5,4) remain and so on.
No extra space was required and hence is O(1) in space.