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(x-y) 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);
}
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
}
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 & (val-1) )
val = (val & (val-1));
// 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);
}
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()]);
}
You can find lots of stuff in these links, hope these help.
google.co.in/competition/howgooglesearchworks.html
pr.efactory.de/e-pagerank-algorithm.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 non-repeated 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;
}
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) + k-1) % n + 1;
}
or by iteration,
f[1] = 0
f[i] = (f[i-1]+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[i-1]+k)%i;
}
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/java-iaq.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 " + (start-end) + " bytes.");
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 = len-1;
while (b < e) {
while ( e < len && str[b]!=str[e] ) e++;
if (e >= len) b++,e=len-1;
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=e-1;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 ...
The whole array is also a subarray! Please update your question.
- Psycho October 17, 2013