Ashupriya
BAN USER- 1of 1 vote
AnswersHow to stop recursion stack as soon as we find a result.
- Ashupriya in United States
e.g. in a Tree recurion where the Order of the algo is O(n) and suppose we find the result just after 4 calls, can we empty the recursion stack and stop the ececution right away...| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm Data Structures General Questions and Comments Ideas Java
- 9 Answers I know its not ethical to [1...
I know its not ethical to
- Ashupriya July 26, 2012
[1] take help from the internet
[2] refer your own code (written earlier)
in a telephonic interview
But due to the very nature of the telephonic interviews, is it also granted from the interviewer's side to take help?
Should n't the telephonic rounds be replaced with video confrencings?
I know its a debatable topic, but would like to hear other's opinion...| Flag | PURGE
void MirrorAlternateWrapper(Node root){
if( root != null){
mirrorAlternate(root, 0);
}
}
void mirrorAlternate(Node root, int level){
if(root == null) return;
mirrorAlternate(root.left, level+1);
mirrorAlternate(root.right, level+1);
if(level %2 == 0){
Node temp = root.right;
root.right = root.left;
root.left = temp;
}
}
[1] Random variable being generated and used in some way in the code, some of the random number might cause the test to fail
[2] Loading an external library
[3] contacting the server may get timeout sometime and pass some other times
[3.1] Or any other kind of network related problem might occur on and off
[4] Race conditions
[5] Memory leaks
[6] The state of the code might depend on some other process's output and that may cause a failure sometime
[7] Use of extern variables which are set by other processes
[8] Use of shared memory locations
[9] Faulty RAM, (hardware problem)
[10] Multithreading
[11] When the code is using Singleton design pattern, unit testing is difficult for singleton as the state of the functions using singleton class's object may not be deterministic.
[12] Rarely though, but it can be due to a bug in the IDE being used eg Eclipse... sometime we need to restart the Eclipse and program starts working fine again
@Ryan: Slight modification in your code and now it will run in O(logN) time....
see the changed code below
public static int Power(int base, int expo){
if(expo == 0) return 1;
if(expo == 1)
return base;
if(expo%2==0)
return (Power(base*base,expo/2);
else
return base*Power(base*base,(expo-1)/2);
}
Note 1: we are using 64 Bits notation : It means maximum 64 bits can be on for a given number so the fib. num < 64 are 1,2,3,5,8,13,21,34,55
Initialize a lookup table with these numbers or we can use a hash table as well for O(1) lookup.
n = higherNumber
while(n ^ lowerNumber !=0)
{
int noOfBits = countBits(n); // Using bit wise operators this can be done in O(c) time, where c is the number of bits set in n. Hence constant time operation
if(presentInLookUpTable(noOfBits))
{
System.out.println(n);
}
n--;
}
An operating system crash commonly occurs when a hardware exception occurs that cannot be handled. Operating system crashes can also occur when internal sanity-checking logic within the operating system detects that the operating system has lost its internal self-consistency.
- Ashupriya August 21, 2012Simple solution :
public void rotateArrayLikeSTLRotate(int[] arr) throws Exception
{
if(arr != null && arr.length > 1)
{
int len = arr.length;
int mid = (len-1)/2;
int start = 0;
int end = len - 1;
for (int i = 0; i <= mid; i++)
{
//Swap i th element with end-mid+i th element
int temp = arr[i];
arr[i] = arr[end - mid + i];
arr[end - mid + i] = temp;
}
}
else
{
throw new Exception("Invalid input parameters");
}
}
Swapping individual bits with XOR
unsigned int i, j; // positions of bit sequences to swap
unsigned int n; // number of consecutive bits in each sequence
unsigned int b; // bits to swap reside in b
unsigned int r; // bit-swapped result goes here
unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary
r = b ^ ((x << i) | (x << j));
class Node <T>{
public T data;
public Node<T> next;
public Node<T> nextLarge; // To point the next large element in the list
Node (T t)
{
data = t;
}
}
public Node<T> applicationOfMergeSort(Node<T> head)
{
if(head == null || head.next == null) return head;
else
{
Node<T> slow = head;
Node<T> fast = head;
//Split
while(fast.next != null)
{
fast = fast.next;
if(fast.next != null)
fast = fast.next;
else
break;
slow = slow.next;
}
Node<T> List1 = head;
Node<T> List2 = slow.next;
Node<T> copyL2 = List2;
slow.next = null;
// Split complete
// Recursively Split and then merge until we reach a list of sizes 1
List1 = applicationOfMergeSort(List1);
List2 = applicationOfMergeSort(List2);
//Since List1 will ultimately hold the result of merging do lets reset the head to point to List1,
//head will be returned as a result of this function
head = List1;
//Merge
Node<T> prev = null;
while(List1 != null && List2!= null)
{
if((Integer) List1.data < (Integer) List2.data)
{
prev = List1;
List1 = List1.nextLarge;
}
else
{
Node<T> nextList2 = List2.nextLarge;
List2.nextLarge = List1;
if(prev == null)
{
head = List2;
}
else
{
prev.nextLarge = List2;
}
prev = List2;
List2 = nextList2;
}
}
if(List2 != null)
prev.nextLarge = List2;
// Merging Complete
// Now make the connection of next pointers, broken earlier in the split step
slow.next = copyL2;
return head;
}
}
What if you had no control at the time of the list creation?
this wont work,...
I have a solution based on the hash map, but that handles only 1 type of mal pointer out of 2 possible cases,
The solution below solves the case when there is a loop in list...
1-2-3 4-5-6-null, 3 points to 1
start traversing the list and make a hash map as below and look for collision if there is a collision then there is a bad pointer
1 Null
2 1
3 2
now comes 1 again and collision occurs...
But another case:
1-2-3 4-5-6-null, 3 points to 5
is not solvable here as we do not have a reference to 4...
Divide the file in N chunks, of 10,000 (e.g.) lines each
store the offset of these N chunks in another file / in memory.
For the last chunk, also count the line numbers (Let say have K line) in it, if it is less than 10,000 then store this information as well
Generate a number randomly between 1 to N, and open this chunk, by seeking to that position in that file.
Now generate another number between 1 and 10,000 and return taht line,
in case of the last chunk generate the number between 1 and K, and return that line....
I can not understand how is the mirrorAlt function is mirroring at alternate levels
- Ashupriya July 15, 2013