A passionate hard-core programmer.
A simple DP approach:
The function can be written as:
F(N, A, S) = F(N - 1, A, S - 1) + F(N - 1, A, S - 2) +........+ F(N - 1, A, S - A)
Where, The F(N, A, S) represents the number of ways of getting S with N dice each with A faces, numbered from 1 to A.
Explaining the above equation in words,
Find the number of ways of getting Sum (S - 1) from (N - 1) dice +
Find the number of ways of getting Sum (S - 2) from (N - 1) dice +
Find the number of ways of getting Sum (S - A) from (N - 1) dice
Carefully handle the base cases like:
1. N = 1, S > A
2. S < 1
1) By head, i mean start/first element of the list only.
2) Sum of counts yield 4 nodes( 3 + 1 ).Step#4 outputs value of count as 1.
Explaining once again: Fix hare at node C and move tortoise to node A. Move both hare and tortoise one step. Now, hare is at node D and tortoise is at node B. Now, next of B and next of D are same node C. So, the algo stops here.
Let me know you are facing any problem.
@buckCherry, Apologies. The concept of Double Linked List is not correct, same for cycle concepts.
Coming back to your initial doubt, how my algo works in your example?
In step#2, hare and tortoise meet at node C. Now move tortoise to node A. So, step#3 outputs 3 nodes( A, B and C).
In step#4, fixing hare at node C and moving tortoise at node A, move hare and tortoise one step until next of both are not equal. So, move hare to node D, and tortoise to node B. Now, next of both are equal, so stop here. The total number of nodes is 4 now.
NOTE: The above algo is inspired from Floyd's Cycle detection algo.
Please let me know if you have still any doubts.
@buckCherry, you are missing a key point. A cycle must contain at least 3 nodes. The example you are using fails because it contains a cycle of two nodes. In fact, this is not a cycle, rather it becomes a partial double linked list.
Hope you got it.
Do you even know the difference between a node and a pointer?
Node doesn't exist until memory is allocated for it. Can you tell how did you count three extra nodes?
So, you think the post is not relevant.
May i ask you where did you find the post is wrong.
Do not let other people think in your way. If they want, they will read.
If you have a better solution, why don't you post it and let other readers judge it.
And its not my blog. I read it there and found it a nice solution.
So, posted the link here.
CareerCup has not well defined indentation. If i would have posted the entire content, it would be messy to read. It is better to go through the link.
If you would have been interested in the solution, you would have been read it carefully. But, i guess you are only interested in downvoting and writing sarcastic comments.
Merge sort only uses extra pointers. We are not allocating any memory for nodes in merge sort.
Merge sort is best suited for linked list.
Follow this link for explanations and implementation:
@nitingupta180, Follow the below link::
It has a well explanation.
Read the question carefully. It has been clearly mentioned that
"Given a singly linked list which may or may not contain loop".
How will you come to know that the linked list is not having loop?
@Tarun.Yadav, i encourage you to give some counter examples.
Why do you think that there will always exist a triangle with those three co-ordinates? The positions can be co-linear.
@eugene.yarovoi, Before writing my thoughts, i experimented how firefox works in this respect. I found that they even keep browser history of 6 months old.
Here is my thought:
I would use a double linked list of dates. Each day, browser is accessed, i would be adding a new node to it. Now, each node of the double linked list will be another linked list for storing the URL's. I don't think timestamp is necessary here. We can add new visited pages to head of the list. In this way, the recent visited pages would be near the front of the list.
I liked your idea of treeSet. It will help if a user visits previously visited page. We need to adjust the nodes of the list.
Now, if the user wants to see the history by data, list will serve the purpose. If the user wants to search a particular URL, we can provide prefix searching like TRIE.
Let me know your thoughts.
@eugene.yarovoi, here is my approach:
void push( void** stack, int* top, void* data, size_t size )
stack[*top] = malloc( size );
for( i = 0; i < size; ++i )
( (char*)stack[*top] )[i] = ( (char*)data )[i];
int top = -1, data = 10;
char ch = 'a';
push( stack, &top, (void*)&data, sizeof( int ) );
push( stack, &top, (void*)&ch, sizeof( char ) );
printf( "%d ", *(int*)stack );
printf( "%c ", *(char*)stack );
I want you to check & comment if you find any issues here.
@Andy2000, after some mathematical calculations, i concluded that the distance will be minimum if we fix the meeting point as one of the person's co-ordinates. Can the meeting point be one of the person's position? If yes, the solution goes simple. O( N^2).
Let me know if i am missing anything.
void generateIPUtil( char* str, char* output, int depth, int countDot, int val )
if( !*str )
output[depth] = '\0';
if( countDot == 3 && output[depth-1] != '.' )
printf( "%s\n", output );
output[depth] = *str;
val = val * 10 + *str - '0';
if( val <= 255 )
if( countDot < 3)
output[depth + 1] = '.';
generateIPUtil( str+1, output, depth+2, countDot+1, 0 );
generateIPUtil( str+1, output, depth+1, countDot, val );
void generateIP( char* str )
generateIPUtil( str, output, 0, 0, 0 );
Working code here: ideone.com/GMs87
@ Nasser Ghazali, the code is fine. You can check the output here: ideone.com/fZ8LE
Regarding direction of output, check against input 52
This can be done in O(1) space.
Time complexity: O(MxN)
Find the max item in the row. Check whether it is the smallest in the column.
void foo(int (*arr)[COL])
int i,j,max, min;
for( i = 0; i < ROW; i++ )
for( j = 1; j < COL; j++ ) // find max in the row
if(arr[i][j] > arr[i][max])
min = 0;
for( j = 1; j < ROW; ++j ) // find min in the column
if(arr[j][max] < arr[min][max])
if( min == i ) // if both items are same
Here is the working code: ideone.com/XfGJV
@shreyans, Individual strings are being sorted so that after sorting the array, all the anagrams will be closer. Where did you find it not working?
can you provide counter example?
1. Take a BST with extra field count of occurrence.
2. Maintain a min heap of size 2 dealing with the frequency. Whenever any item occurrence is more than the frequency of the head, replace it & update heap.
3. At the last, the top of the heap gives the required item.
@Abhishank Sahu, the algo is working well with the inut set given by you. Can you provide the link where it didn't give the correct output?
int isValid(char* str,int k)
if(k<=0) return 0;
if(str[i]=='0' && (i==0 || str[i-1]=='0'))
void print(char* str,int k)
void countValidString(char* str,int depth,int k)
Complete working code: ideone.com/cDPgI
Why Dijkshtra? Just do DFS from one user to other. Meanwhile, keep minimum distance so far.
What is generated as a result of inorder traversal of BST?
Of course, A sorted list of data. I am changing the pointers in midway.
What made you think that the list will not be sorted?
@eugene.yarovoi,Thanks for pointing out the mistake. So, While updating the maxProfit, We also need to check that whether the new profit calculated is greater than the maxProfit calculated so far.
I have updated the solution.
@Raj, did you bother running my code?
I have checked my code against the input set given by you & it is correctly outputting 5.
I have updated my solution with the link where i checked. Please have a look.
Perform binary search.
int findFirstOccurrence(int* arr,int l,int h,int tofind)
if(l>h) return INT_MIN;
if(arr[mid]==tofind && (mid==l || arr[mid]>arr[mid-1]))
Complete code here: ideone.com/8q91s
Use references in the same way you use pointers.
virtual void show()
cout<<"A class show()"<<endl;
class B: public A
cout<<"B class show()"<<endl;
Complete code here: ideone.com/Zuebz
The problem boils down to:
Given an array, find two indices min & max such that A[max]-A[min] is maximum and max>min.
int findMAxProfit(int* A,int n) // n is the number of days
if(A[i]-A[min] > maxProfit) // if you want, update buy & sell day here
Complete code here: ideone.com/Xt1ZA
#define N 1
Complete code here: ideone.com/3kdhv
Time complexity: O(N)
int findTrappedWater(int* H,int size)
while(j<size && H[i]>H[j])
if(j!=size) // decreasing length histogram
Complete code here: ideone.com/xCsHn
There is a problem with a+b<0. Consider the below tree.
The preorder traversal is: 5,1,5
a*b==0 But a+b>0, the function returns TRUE. But, it should return FALSE.
An easy approach:
1. Name the levels as 1,2,3.... A cup numbered i will pour extra water into cups with number i+level and i+level+1.
I am using an integer array cup to store the amount of water in each cup. The same logic applies to the float also.
Here is the pseudo code:
void fillWater(int C,int L,int n,int* cup)
printf("cup number %d has %d water\n",i,cup[i]);
C: Capacity of each cup
L: Water poured in the first cup.
n: Number of cups
Complete working code here: ideone.com/7u7yU
void foo(int* res,int depth,int N,int tillnow)
if(!depth || i<=res[depth-1])
Complete code here: ideone.com/tyxoZ
Wrong! Merge sort needs even less number of comparisons.
It needs n ⌈lg n⌉ - 2^⌈lg n⌉ + 1 in worst case.
Which is 14 here.
void interleaving(char* s1,char* s2,char* res,int depth)
if(!*s1 && !*s2)
Complete code: ideone.com/35VNh
Hi, I’m Jamie from the Portsmouth USA and I am working as an account manager. I work for a ...
As per my understanding, the solution has nothing to do with "forest of binary trees". We can just crawl the parents of both nodes n1 and n2 upwards and see if their parents are same.
Sample code module below:
Please let me know if I missed anything:
- Aashish December 26, 2015