Psycho
BAN USERSimple guy. Loves Programming.
 0of 0 votes
AnswersState the difference between this two statement.
 Psycho in India
char str[] = "/root//foo/bar" ;
char *str = "/root//foo/bar" ;
Now, you have given an assignment str[in1] = str[in2]
where in1 and in2 both initialize with 0.
In first type of declaration no problem. But in second type of declaration 'Segmentation fault' is there. Why this happens? Report Duplicate  Flag  PURGE
Adobe Software Engineer / Developer C  0of 0 votes
AnswersJust Example : "Given 8 cue balls , one is weighing lesser than other 7. Find that(light weight) ball using just 2 chances on balance weight."
 Psycho in India
How to find a general solution to these kind of question? How to divide this set of balls? Is there any finer method or general formula? Report Duplicate  Flag  PURGE
Software Engineer / Developer Brain Teasers  0of 0 votes
AnswersAn unsorted array is given, where there is no specific range in which the elements occur. There is only one duplicate element present in it. Let it is a[i]. It should be within the half of the size of the array from where it appears for first time. i.e. the duplicate element should be within (i+(arr_size/2)), at ith index it appears for 1st time. Find the duplicate element with minimum number comparisons.
 Psycho in United States Report Duplicate  Flag  PURGE
Microsoft
 0 Answers C++ Topic : Related to 'Multiset' functionality
Consider this sample piece of code!
multiset<int> iends; multiset<int>::iterator et1; while(et1!=iends.end()){ multiset<int>::iterator te=et1; et1++; iends.erase(te); } while(et1!=iends.end()){ multiset<int>::iterator te=et1; iends.erase(te); et1++; }
What is the difference between this two pieces of code?
 Psycho December 09, 2012 Flag  PURGE
1. Sort the whole list of numbers in descending order.
2. If n == 1, print the single element that's the minimum difference.
3. Otherwise if n >= 2, create two variable x, y which denote the sum of two lists whose difference we want to minimize.
4. Assign the first two elements in x and y  i.e. initialize x with one value and y with other.
5. for rest of all the elements : a[i] , add the value to 'x' if (x+a[i]) <= y or add it to 'y'.
one thing we should remember that if the number of values assignment associated with 'x' equal to ceil(n/2)  we should stop adding value to it (x) and continue adding the values with 'y'.
After all these steps abs(xy) will give you the ultimate answer.
You asked for lexicographic order and don't want to convert it to character strings.
But according to lexicographic order your example shows "one > ten > eleven and so on".
Please edit your question : "Lexicographic order" seems pretty misleading. Your example tells what is the question.
The diameter of a tree T is the largest of the following quantities:
* the diameter of T’s left subtree
* the diameter of T’s right subtree
* the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
Call this function Ceil(root,input, 1)
//If input is more than the max key in BST, return 1
int Ceil(node *root, int input, int ans)
{
// Base case
if( root == NULL )
return ans;
// If root's key is equal or smaller, ceil must be in right subtree
// So iterate with previous value  possibly minus one if its going right.
if( root>key <= input )
return Ceil(root>right, input, ans);
// Else, either left subtree or root has the ceil value
// parent must be a possible candidate  iterate further
// to left to find smaller value than parent
return Ceil(root>left, input, root>key);
}

Psycho
October 06, 2013 This question is exactly similar to another popular question "Given two singly linked lists and they both intersect at one point (ie, forming a Y shaped list). Find where the two linked lists merge"
So we can simply boil down this question to simple question.
// As root>parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) {
int h1 = getHeight(p);
int h2 = getHeight(q);
// swap both nodes in case p is deeper than q.
if (h1 > h2) {
swap(h1, h2);
swap(p, q);
}
// invariant: h1 <= h2.
int dh = h2  h1;
// coming the deeper node to the same level w.r.t. root
for (int h = 0; h < dh; h++)
q = q>parent;
//At same level
while (p && q) {
if (p == q) return p;
p = p>parent;
q = q>parent;
}
return NULL; // p and q are not in the same tree
}

Psycho
October 02, 2013 If in the first pass, we find a value with multiple bit set to 1, then choose any one of such bit position.
This is really good answer without modifying the input array.
void twoNumAppearOnce(int arr[], int size)
{
int i, val = 0, res1 = 0, res2 = 0;
for (i = 0; i < size; i ++)
val ^= arr[i];
// Check if there are multiple bits are set to one choose any one of them. I am choosing the right most set bit.
if ( val & (val1) )
val = (val & (val1));
// Get the first number  that bit is off in number
for ( i = 0; i < size; i ++ )
if ((val & arr[i]) == 0)
res1 ^= arr[i];
// Get the second number  that bit is on in number
for ( i = 0; i < size; i ++ )
if ((val & arr[i])!=0)
res2 ^= arr[i];
printf ("Values are %d %d\n", res1, res2);
}

Psycho
October 02, 2013 Using queue.
int arr[1000001];
void printKMax(int n, int k) {
deque<int> Qi(k);
int i;
for (i = 0; i < k; ++i) {
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back(); // Remove from rear
Qi.push_back(i);
}
for ( ; i < n; ++i) {
printf ("%d ", arr[Qi.front()]);
while ( (!Qi.empty()) && Qi.front() <= i  k)
Qi.pop_front(); // Remove from front of queue
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
Qi.push_back(i);
}
printf ("%d", arr[Qi.front()]);
}

Psycho
July 20, 2013 You can find lots of stuff in these links, hope these help.
google.co.in/competition/howgooglesearchworks.html
pr.efactory.de/epagerankalgorithm.shtml
google.co.in/intl/en/insidesearch/howsearchworks/algorithms.html
math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html
Deletion will take o(n) time in this case. You can take a circular array, where head will point the first character that came in the stream, and in the tail you can add the first character came currently in the stream. When a character is repeated, dirty the position in the circular array by replacing 1, if the character is pointed by head, increase the head pointer, till we found a non 1 value.
So, 1 array (hash) for holding the current status of the character. 1 circular array for the first nonrepeated character pointed by head of this array.
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int value;
struct node* next;
}node;
node* getNode (int val) {
node *element ;
element = (node *) malloc (sizeof(node)) ;
element>value = val ;
element>next = NULL ;
return element ;
}
node* addNode (node* head, node *element) {
node *temp = head ;
if ( head == NULL ) {
head = element ;
head>next = head ;
return head ;
}
while (temp>next != head)
temp = temp>next ;
temp>next = element ;
element>next = head ;
return head ;
}
void printList(node *head) {
node *temp = head ;
if (head) {
while ( temp>next != head ) {
printf ( "%d ", temp>value ) ;
temp = temp>next ;
}
printf ( "%d", temp>value ) ;
}
}
node* getKthNode (node *list, int k, int size) {
int oldVal = 0, i, newVal ;
node *temp = NULL, *element ;
for ( i = 2 ; i <= size ; i ++ ) {
newVal = (oldVal + k) % i ;
oldVal = newVal ;
}
newVal ++ ;
temp = list ;
if ( size == 1 )
return list ;
for ( i = 1 ; i < newVal; i++ ) {
list = list>next ;
free (temp) ;
temp = list ;
}
element = list ;
element>next = NULL ;
list = list>next ;
for ( i = newVal+1 ; i < size ; i++ ) {
list = list>next ;
free (temp) ;
list = list>next ;
}
free (list) ;
return element ;
}
int main() {
node *head = NULL, *temp ;
int size, i, val, k;
printf ( "\nEnter the sie :\t" ) ;
scanf ( "%d", &size ) ;
for ( i = 0 ; i < size ; i ++ ) {
printf ( "\nEnter the value :\t" ) ;
scanf ( "%d", &val ) ;
head = addNode (head, getNode(val)) ;
}
printf ( "\n" );
printList(head);
printf ( "\nEnter the k :\t" ) ;
scanf ( "%d", &k ) ;
temp = getKthNode (head, k, size) ;
if ( temp != NULL )
printf ( "\nLast node :\t%d\n", temp>value ) ;
return 0;
}

Psycho
June 29, 2013 This is josephus problem..
This can be done either using recursion
int josephus(int n, int k)
{
if (n == 1)
return 1;
else
/* The position returned by josephus(n  1, k) is adjusted because the
recursive call josephus(n  1, k) considers the original position
k%n + 1 as position 1 */
return (josephus(n  1, k) + k1) % n + 1;
}
or by iteration,
f[1] = 0
f[i] = (f[i1]+k)%i
final result would be
f[n]+1
void precomp() {
int i;
val[1] = 0;
for (i = 2; i < MAX; i++)
val[i] = (val[i1]+k)%i;
}

Psycho
June 29, 2013 The boolean mapping was done with a 32bit CPU in mind. The int value has 32 bits so it can be processed in one operation.
Here's a solution from Peter Norvig's Java IAQ: Infrequently Answered Questions (norvig.com/javaiaq.html#sizeof) to measure the size (with some imprecision):
static Runtime runtime = Runtime.getRuntime();
...
long start, end;
Object obj;
runtime.gc();
start = runtime.freememory();
obj = new Object(); // Or whatever you want to look at
end = runtime.freememory();
System.out.println("That took " + (startend) + " bytes.");

Psycho
June 18, 2013 The solution consists of constructing the suffix array and then finding the number of distinct substrings based on the Longest Common Prefixes.
One key observation here is that:
If you look through the prefixes of each suffix of a string, you have covered all substrings of that string.
Let us take an example: BANANA
Suffixes are:
0) BANANA
1) ANANA
2) NANA
3) ANA
4) NA
5) A
It would be a lot easier to go through the prefixes if we sort the above set of suffixes, as we can skip the repeated prefixes easily.
Sorted set of suffixes:
5) A
3) ANA
1) ANANA
0) BANANA
4) NA
2) NANA
From now on,
LCP = Longest Common Prefix of 2 strings.
Initialize
ans = length(first suffix) = length("A") = 1.
Now consider the consecutive pairs of suffixes, i.e, [A, ANA], [ANA, ANANA], [ANANA, BANANA], etc. from the above set of sorted suffixes.
We can see that,
LCP("A", "ANA") = "A".
All characters that are not part of the common prefix contribute to a distinct substring. In the above case, they are 'N' and 'A'. So they should be added to ans.
So we have,
ans += length("ANA")  LCP("A", "ANA")
ans = ans + 3  1 = ans + 2 = 3
Do the same for the next pair of consecutive suffixes: ["ANA", "ANANA"]
LCP("ANA", "ANANA") = "ANA".
ans += length("ANANA")  length(LCP)
=> ans = ans + 5  3
=> ans = 3 + 2 = 5.
Similarly, we have:
LCP("ANANA", "BANANA") = 0
ans = ans + length("BANANA")  0 = 11
LCP("BANANA", "NA") = 0
ans = ans + length("NA")  0 = 13
LCP("NA", "NANA") = 2
ans = ans + length("NANA")  2 = 15
Hence the number of distinct substrings for the string "BANANA" = 15.
 Psycho March 13, 2013int b, e, i, j;
gets (str);
int len = strlen(str);
if (len<=0) continue;
b = 0; e = len1;
while (b < e) {
while ( e < len && str[b]!=str[e] ) e++;
if (e >= len) b++,e=len1;
else b++,e;
if (e<=b) {
i=b; j=e;
while (j<len&&str[i]==str[j]) i,j++;
if (j<len) e++;
}
}
for (i=0;i<=b;i++)
printf("%c",str[i]);
for (i=e1;i>=0;i)
printf("%c",str[i]);
printf("\n");
So, if your input is "amanaplanacanal"
then it will print first "amanaplanac"
then "analpanama"
So, final result will be "amanaplanacanalpanama"
RepOliviaJBlack, Consultant at Apkudo
I am Olivia from San Diego. I am working as a checker in the Thom McAn Store company. My strong ...
RepShirleyCWest, Software Engineer at Agilent Technologies
Hello, me Shirley and I from Savage. I am an artist and I love to doing art and I am ...
Open Chat in New Window
The whole array is also a subarray! Please update your question.
 Psycho October 17, 2013