Expressions
BAN USERYou can implement Comparable or use a Comparator. Following is an example where we want to compare two accounts based on balance.
public class Account implements Comparable<Account>{
@Override
public int compareTo(Account account) {
return (this.balance < account.balance ) ? -1: (this.balance > account.balance ) ? 1:0 ;
}
}
public class AccountBalanceComparator implements Comparator<Account>{
@Override
public int compare(Account accountA, Account accountB) {
return (accountA.getBalance() < accountB.getBalance() ) ? -1: (accountA.getBalance() > accountB.getBalance() ) ? 1:0 ;
}
}
If the inorder traversal of the tree is sorted, the tree is BST else not.
- Expressions October 27, 2013Create three groups of 3 balls each.
Compare two of these groups (1st comparison)
If equal
Compare the two balls in second group (2nd comparison)
If equal
Return the uncompared ball
Else
Return the ball that is heavier
Else
Compare the balls in the group which came heavy in first comparison (2nd comparison)
If equal
Return the uncompared ball
Else
Return the ball that is heavier
In fact the above algorithm works in every case where the number of balls is 3^n for n>1 with one additional comparison.
e.g.
For 27 balls this can be done in 3 steps.
For 81 balls this can be done in 4 steps.
Just group the balls in 3 groups. i.e. 27/3 which reduced it to the original problem.
Average of an AP is (first_tearm+last_term)*Number_Of_Elements/2
So expected sum would be (average* number of items).
To get the missing number subtract actual_sum from expected_sum.
Following is the code.
public static int getMissingTermInAP(int[] arr, int n) {
if (n < 3)
throw new RuntimeException("n cannot be less than 3");
int average = (arr[0] + arr[arr.length - 1]) / 2;
int actualSum = 0;
for (int x : arr)
actualSum += x;
return average * n - actualSum;
}
Test Cases:
{-1,3,7,15} => 11
{1,3,7,9} => 5
You can find the info at stroustrup's bs_faq2
Google for stroustrup's bs_faq2. Links are not allowed on Careercup.
Exactly!
- Expressions April 09, 2013Start with top right element
Loop:
Compare this element e with x
i) if they are equal then return its position
ii) e < x then move it to down
iii) e > x then move it to left
Repeat above 3 steps till you find element
If not found return false
Make a check at each step that the index is not out of bound.
Time Complexity: O(n)
Space Complexity: O(1)
1. The standard does not allow objects (and classes thereof) of size 0, since that would make it possible for two distinct objects to have the same memory address. That's why even empty classes must have a size of (at least) 1.
2. Default constructor, Copy constructor, Copy-assignment, Destructor, Move constructor, Move-assignment operator
3. Yes it depends on CPU architecture. It will at least be 1 byte.
This is just Maximum single-sell profit question in different format.
Solution is in O(n)
def main(arr):
if len(arr) == 0:
return 0
max_diff = 0
min_val = arr[0]
for i in range(1, len(arr)):
min_val = min(min_val, arr[i])
max_diff = max(max_diff, arr[i] - min_val)
return max_diff
Keep track of values of current i and j here and your solution is done.
- Expressions April 09, 2013A single element can be placed to its final location in log(n) time.
- Expressions April 06, 2013Use two pointers both pointing to the head of the linked list. Move one of the pointers k ahead. Now move both of the pointers one node ahead at a time. When the first one reaches the end the second one would be k nodes behind it.
void printKthFromLast(struct node *head, int k){
struct node *main_ptr = head;
struct node *ref_ptr = head;
int count = 0;
if(head != NULL){
while( count < k ){
if(ref_ptr == NULL){
printf("There are fewer than %d nodes in the list", k);
return;
}
ref_ptr = ref_ptr->next;
count++;
}
while(ref_ptr != NULL){
main_ptr = main_ptr->next;
ref_ptr = ref_ptr->next;
}
printf("%d the node from the end is %d",
k, main_ptr->data);
}
}
Net Vertical Movement = No Of Ns- No Of Ss
Net Horizontal Movement = No Of Es- No Of Ws
So its a simple array summation problem. Only thing to take care is at every summation the
horizontal sum <= (Right Edge-Current X Position)
and >=Left Edge-Current X Position
vertical sum <= (Top Edge-Current Y Position)
and >=Bottom Edge-Current Y Position
Following is one of the many ways to do this.
Take the inorder traversal. Since it is sorted you easily check the number of nodes having values between a and b.
O(n) where n is total number of nodes.
You can optimize the above if you count the node during traversal itself and reject the left child of nodes having values less than a and right child of nodes having values greater than b.
- Expressions April 04, 2013Yes the primitive data types inside an object are part of the object hence would be on heap.
- Expressions April 04, 2013Stack memory stores primitive types and the addresses of objects.
The object values are stored in heap memory. An object reference on the stack is only an address that refers to the place in heap memory where that object is kept.
You can send the tree as preorder and in order traversals or XML tree and then parse to reconstruct the tree.
- Expressions April 03, 2013@jv
Yes that is the premise of LRU. In case you want a cache system to retain values based on how often they were accessed you can use
LFU (Least Frequently Used)
cache design which counts how often an item is needed. Those that are used least often are discarded first.
Else you can use
ARC (Adaptive Replacement Cache)
which balances between LRU and LFU, to give improved result. It dynamically updates the size of protected segment and the probationary segment so to make optimum use of available cache space.
Updated my main answer as well for completeness.
Implement an
LRU (Least Recently Used)
cache.
How to implement LRU caching scheme? What data structures should be used?
We are given total possible page numbers that can be referred. We are also given cache (or memory) size (Number of page frames that cache can hold at a time). The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache. Please see the Galvin book for more details (see the LRU page replacement slide here).
We use two data structures to implement an LRU Cache.
1. A Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).
The most recently used pages will be near front end and least recently pages will be near rear end.
2. A Hash with page number as key and address of the corresponding queue node as value.
When a page is referenced, the required page may be in the memory. If it is in the memory, we need to detach the node of the list and bring it to the front of the queue.
If the required page is not in the memory, we bring that in memory. In simple words, we add a new node to the front of the queue and update the corresponding node address in the hash. If the queue is full, i.e. all the frames are full, we remove a node from the rear of queue, and add the new node to the front of queue.
Reference: geeksforgeeks
In case you want a cache system to retain values based on how often they were accessed you can use
LFU (Least Frequently Used)
cache design which counts how often an item is needed. Those that are used least often are discarded first.
Else you can use
ARC (Adaptive Replacement Cache)
which balances between LRU and LFU, to give improved result. It dynamically updates the size of protected segment and the probationary segment so to make optimum use of available cache space.
- Expressions April 02, 2013@J
Your reasoning is perfectly valid. Thanks
Not 1 to N but 0 to N. And the assumption is given in the question.
How to find a missing value in an size N unsorted array (value from 0 to N but missing one of them).
In any case you will need to visit every node once O(n) is the best that can be achieved.
In the above case the worst case complexity would be O(n^2)
To do it in O(n) use queues for level order traversal.
That is a typo that came in automatically. remove the semicolons at both the places.
It stays even after editing and updating.
In my profiling experiments I have found XOR and Integer taking same time.
A comparison of N(N+1)/2 and Sum(arr) will have total of N+1 operations.
N inividual XORs and then again XORing them N-1 times making total operations as 2*N-1.
Can you please point why doing XOR would be preferable?
In Python:
def findMissing(a,N):
sum=0
for x in a:
sum+=x
print (N*(N+1)/2)-sum
Test:
findMissing([0,1,4,2],4)
3
@Eugene
The comment was for PKT's solution where an array is being used and looked up every time.
My bad, failed to see the <anonymous/>
- Expressions March 27, 2013Hey Minku,
The algo dfinitely leads us to result. You will be XORing two different sets and each of them will have the two numbers separately. I am posting my implementation.
public class Main {
public static void main(String[] args) {
int a[]={2,3,2,3,3,4,5,4,2,2,5,6};
Integer XOR = null;
for(int i=0;i<a.length;i++){
if(XOR==null)
XOR=a[i];
else
XOR^=a[i];
}
int position=findFirstBitWithSetBit(XOR);
Integer XOR0=null, XOR1=null;
for(int i=0;i<a.length;i++){
if(getBitAtPosition(a[i], position)==0){
if(XOR0==null)
XOR0=a[i];
else
XOR0^=a[i];
}else{
if(XOR1==null)
XOR1=a[i];
else
XOR1^=a[i];
}
}
System.out.println(XOR0);
System.out.println(XOR1);
}
public static int getBitAtPosition(int x, int position){
return (x>>position)&;1;
}
public static int findFirstBitWithSetBit(int x){
int position=0;
while((x&;1)!=1){
position++;
x=x>>;1;
}
return position;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
@PKT
Your solution has a space complexity of O(n) and time complexity of O(n^2).
Hey Satyajeet here you go. Should work without any change. Please let me know as I could not verify this.
public class Main {
public static void main(String[] args) {
int a[]={2,3,2,3,3,4,5,4,2,2,5,6};
Integer XOR = null;
for(int i=0;i<a.length;i++){
if(XOR==null)
XOR=a[i];
else
XOR^=a[i];
}
int position=findFirstBitWithSetBit(XOR);
Integer XOR0=null, XOR1=null;
for(int i=0;i<a.length;i++){
if(getBitAtPosition(a[i], position)==0){
if(XOR0==null)
XOR0=a[i];
else
XOR0^=a[i];
}else{
if(XOR1==null)
XOR1=a[i];
else
XOR1^=a[i];
}
}
System.out.println(XOR0);
System.out.println(XOR1);
}
public static int getBitAtPosition(int x, int position){
return (x>>position)&1;
}
public static int findFirstBitWithSetBit(int x){
int position=0;
while((x&1)!=1){
position++;
x=x>>1;
}
return position;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
If you really find some answer helpful, please up-vote. It helps people in finding valid answers. :)
- Expressions March 27, 2013At each node i store the difference between petrol at i-1 node and distance between i-1 and i.
This would give the excess/deficit petrol at node i for further journey.
Now in this circle start from any node and proceed in one direction. Add the nodes on the way till the sum is positive. If it becomes negative move the start node backwards updating the sum.
Proceed as such.
Break out the loop once the end node reaches start node. If the result is positive the start node and end node is solution. If the result is negative no solution is possible.
1. XOR all the n numbers.
2. Result will be knocked out for all the even pairs as a^a=0 The result now contains only XOR of the two odd out numbers.
3. Find the first bit position in the result that is 1. Definitely this bit position both the odd numbers have different bit values. i.e. one has a 0 and another has a 1 at this position. Let this position be x
4. XOR the elements that have 1 at x bit position and XOR the elements that have 0 at x bit position. The two XOR results would give the two odd count numbers.
It can be done in O(1) Space
Create a static variable X
For Each New Node encountered
If X > New Node's Value
Not a BST
Break
Else
X= New Node's Value
This algo will return true for
10
8 12
6 14 2 18
But this is not a binary search tree. The problem being that all the nodes in left should be smaller than root node and not just the immediate left child. Similarly all the nodes in right should be larger than root node and not just the immediate right child
- Expressions March 26, 2013You simply take the inorder traversal of the binary tree and check if it is sorted. If yes it is a binary search tree else no.
- Expressions March 26, 2013@rfaccone
Can you please clarify how is NOTE - Yes and TONE - No as I could see all the four chars in the two words same?
If the % are probability we can simply generate a random number between 1 and 100 inclusive and then return the object based on range
import random
def returnProbable(x,y,z):
x = random.randint(1, 100)
if x in range(1,21):
return x
if x in range(20,91):
return y
if x in range(90,101):
return z
If the numbers are to be returned with fixed % we will have to decide the window in which the case would be valid. e.g. with 9 calls to the function the ratio will not be possible.
It will only be possible when the calls are in multiples of 10. In that case we can use xCount=2, yCount=8 and xCount=1. We can return any value as long as it is non zero. before returning decrease the count by 1. Once all three reach 0, reinitialize them to 2,8,1 respectively.
Sorry, I misunderstood the question.
- Expressions March 22, 2013Updated the code on below suggestion
a = [1,2,3,6]
k=3
for i in range(len(a)-1):
for j in range(i+1,len(a)):
if (a[i]+a[j])%k==0:
print a[i], a[j]
\b(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\b
- Expressions March 22, 2013Yes this is also called Tortoise and Hair algorithm.
- Expressions March 22, 2013Use Floyd's Cycle Finding Algorithm
int isListCircular(ListNode* head){
if(head==NULL)
return 0;
ListNode *fast=head, *slow=head;
while(fast && fast->next){
if(fast->next->next==slow)
return 1;
fast=fast->next->next;
slow=slow->next;
}
return 0;
}
Rather than allocating memory for a single input, use something like
struct node{
char a[100];
struct node* next;
};
This would help in removing the malloc overhead for every input.
- Expressions March 21, 2013If length of input > 100 characters.
- Expressions March 19, 2013What if the input is >100 characters.
- Expressions March 19, 2013Space should be O(1).
- Expressions March 19, 2013The interviewer wont let me use a stack. The expectation was to come up with linked list of character arrays.
Even with the stack the solution should pop the last read character if the user presses <backspace>
TestCases:
- Expressions October 30, 2013