## oglA

BAN USER- 0of 0 votes

AnswersWe toss a fair coin n times. A k-streak of flips is said to occur starting at toss i, if the outcome of all the k flips starting from i th flip is the same. For example, for the sequence HTTTHH, there is a 2-streak occurring at 2 nd toss, there is a 2-streak occurring at 3rd toss, and there is a 2-streak occurring at 5th toss. Here the total number of 2-streaks is 3 in the sequence HTTTHH. What is the expected number of k-streaks which you will see in n tosses of a fair coin ?

- oglA in United States| Report Duplicate | Flag | PURGE

Algorithm Math & Computation Probability - 0of 0 votes

AnswersOnce upon a time the following puzzle was suggested to pupils on a regional middle school olympiad on mathematics:

- oglA in India

A set of coins consists of 15 coins: 14 coins are valid while a remaining 15-th coin is a false one. All valid coins have one and the same weight while the false coin has a different weight. One valid coin is marked. Is it possible to identify a false coin balancing coins 3 times at most?

A jury member was a trainer of a team of undergraduates for programming contests. So a question on how to put the puzzle for programming arose naturally. Fin ally the problem was formulated as follows:

A set of coins consists of N coins: (N - 1) coins are valid while a remaining N-th coin is a false one. All valid coins have one and the same weight while the false coin has a different weight. One valid coin is marked. Write a program which for every input pair

a number N of coins under question,

a limit K of balancing

outputs either ``POSSIBLE" or ``IMPOSSIBLE" with respect to existence of a strategy to identify the false coin balancing coins K times at most.

Input

The first line of input contains a single integer T that represents a total amount of different pairs (N, K) to process.

Output

The output file should contain T lines with ``POSSIBLE" or ``IMPOSSIBLE" per line.

Sample Input

3

6 2

10 2

15 3

Sample Output

POSSIBLE

IMPOSSIBLE

POSSIBLE| Report Duplicate | Flag | PURGE

IIT-D Algorithm Data Structures - 1of 1 vote

AnswersRakesh likes skiing a lot. That's not very surprising, since skiing is really great. The problem with skiing is one have to slide downwards to gain speed. Also when reached the bottom most point one has to wait for ski-lift to get to higher altitude.

- oglA in India

Rakesh seeks your help to know the longest run possible with the given peaks. That altitude of different peaks is given by a grid of numbers. Look at this example:

7 2 3 4 5

36 37 38 34 6

33 44 46 40 7

24 43 42 41 8

35 32 47 30 9

One can ski down from one peak to a connected peak if and only if the height decreases. One peak is connected to another if it's at left, at right, above or below it. In the sample map, a possible ski path would be 36-33-24(start at 36, end at 24). Of course if one would ski 46-44-43-42-41-30-9....3-2, it would be a much longer run. In fact, it's the longest possible. There could be more than one longest ski path, but all Rakesh needs from you is to tell maximum number of peaks he could cover for a given map, in this case it is 14.

Input ::

All input comes from input.txt file. The first line contains the number of test cases N. Each test case starts with a line containing the name (it's a single string), the number of rows R and the number of columns C. After that follow R lines with C numbers each, defining the heights. R and C won't be bigger than 100.

Output ::

For each test case, print a line to output.txt containing the name of the area, a colon, a space and the length of the longest run (maximum points covered) one can slide down in that area.

Sample Input

2

Manali 10 5

56 14 51 58 88

26 94 24 39 41

24 16 8 51 51

76 72 77 43 10

38 50 59 84 81

5 23 37 71 77

96 10 93 53 82

94 15 96 69 9

74 0 62 38 96

37 54 55 82 38

Narkanda 5 5

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

Sample Output

Manali: 7

Narkanda: 25| Report Duplicate | Flag | PURGE

Java Developer Algorithm

Let X be the kth node from beginning and Y be the kth node from end. Following are the interesting cases that must be handled.

1) Y is next to X

2) X is next to Y

3) X and Y are same

4) X and Y donâ€™t exist (k is more than number of nodes in linked list)

SOLUTION USING SINGLE LINK LIST

#include<stdio.h>

#include<stdlib.h>

int main()

{

struct node

{

int data;

struct node *next;

}*head;

head=NULL;

int i,num,k,n;

struct node *temp,*temp1,*temp2;

printf("enter the number=");

scanf("%d",&num);

scanf("%d",&k);

for(i=1;i<=num;i++)

{

scanf("%d",&n);

if(head==NULL)

{

head=malloc(sizeof(struct node));

head->data=n;

temp=head;

}

else

{

temp->next=malloc(sizeof(struct node));

temp->next->data=n;

temp=temp->next;

}

}

temp->next=NULL;

temp=head;

i=1;

while(temp!=NULL)

{

if(i==k)

{

temp1=temp;

temp=temp->next;

}

else if(i==num-k-1)

{

temp2=temp;

temp=temp->next;

}

else

{

temp=temp->next;

}

i=i+1;

}

temp=temp1;

int c=temp->data;

temp=temp2;

int d=temp->data;

temp=temp1;

temp->data=d;

temp=temp2;

temp->data=c;

temp=head;

while(temp!=NULL)

{

printf("%d ",temp->data);

temp=temp->next;

}

return 0;

}

The key data structure of the algorithm is the combination of Hash Map and Doubly-Linked List. We initialize a Hash Map in a per-defined size to store pairs, and use Doubly-Linked List to index the pairs in the order of data age.

Here is C++ code for LRU,

#include <iostream>

#include <vector>

#include <hash_map>

using namespace std;

using namespace stdext;

template<class K, class T>

struct LRUCacheEntry

{

K key;

T data;

LRUCacheEntry* prev;

LRUCacheEntry* next;

};

template<class K, class T>

class LRUCache

{

private:

hash_map< K, LRUCacheEntry<K,T>* > _mapping;

vector< LRUCacheEntry<K,T>* > _freeEntries;

LRUCacheEntry<K,T> * head;

LRUCacheEntry<K,T> * tail;

LRUCacheEntry<K,T> * entries;

public:

LRUCache(size_t size){

entries = new LRUCacheEntry<K,T>[size];

for (int i=0; i<size; i++)

_freeEntries.push_back(entries+i);

head = new LRUCacheEntry<K,T>;

tail = new LRUCacheEntry<K,T>;

head->prev = NULL;

head->next = tail;

tail->next = NULL;

tail->prev = head;

}

~LRUCache()

{

delete head;

delete tail;

delete [] entries;

}

void put(K key, T data)

{

LRUCacheEntry<K,T>* node = _mapping[key];

if(node)

{

// refresh the link list

detach(node);

node->data = data;

attach(node);

}

else{

if ( _freeEntries.empty() )

{

node = tail->prev;

detach(node);

_mapping.erase(node->key);

node->data = data;

node->key = key;

attach(node);

}

else{

node = _freeEntries.back();

_freeEntries.pop_back();

node->key = key;

node->data = data;

_mapping[key] = node;

attach(node);

}

}

}

T get(K key)

{

LRUCacheEntry<K,T>* node = _mapping[key];

if(node)

{

detach(node);

attach(node);

return node->data;

}

else return NULL;

}

private:

void detach(LRUCacheEntry<K,T>* node)

{

node->prev->next = node->next;

node->next->prev = node->prev;

}

void attach(LRUCacheEntry<K,T>* node)

{

node->next = head->next;

node->prev = head;

head->next = node;

node->next->prev = node;

}

};

package com.rakesh.topcoder;

import java.util.Scanner;

public class PerfectSquareWithAddition {

/**

* @param args

*/

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

System.out.println("Enter a numer..");

int n = input.nextInt();

int finalval = findPerfectSquare(n);

if(finalval == 0) System.out.println( n + " is a Perfect Square " );

else System.out.println(n + " is not a perfect square ");

}

public static int findPerfectSquare(int n){

int a=1;

while(n>0){

n -= a;

a += 2;

}

return n;

}

}

@Anonymous: small correction....... your code doesn't work for "1020". or any input that can have 10/20.

Here is the working and modified code.....

package com.rakesh.topcoder;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Scanner;

import java.util.Set;

public class GenAlphabetCodes {

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner input = new Scanner(System.in);

System.out

.println("Please enter any length number but combination of 1 to 26 ....... ");

String val = input.next();

System.out.println("All possible Alphabet codes for the give Number: "

+ val);

for (String string : decode(val)) {

System.out.println(string);

}

}

public static Set<String> decode(String in) {

char curChar = 'a';

Map<Integer, Character> numberToChar = new HashMap<Integer, Character>();

for (int i = 1; i <= 26; i++) {

numberToChar.put(i, curChar);

curChar++;

}

return decodeHelper(numberToChar, in, 0, new ArrayList<Character>());

}

private static Set<String> decodeHelper(

Map<Integer, Character> numberToChar, String in, int charAt,

ArrayList<Character> arrayList) {

Set<String> result = new HashSet<String>();

if (charAt >= in.length()) {

String str = "";

for (char c : arrayList) {

str += c;

}

result.add(str);

return result;

} else {

int charCode = Integer.valueOf(in.charAt(charAt) + "");

if (charCode == 0) {

int precCharCode = Integer.valueOf(in.charAt(charAt - 1) + "");

if (precCharCode == 1)

charCode = 10;

if (precCharCode == 2)

charCode = 20;

}

char curChar = numberToChar.get(charCode);

arrayList.add(curChar);

result.addAll(decodeHelper(numberToChar, in, charAt + 1, arrayList));

arrayList.remove(arrayList.size() - 1);

if (in.length() > charAt + 1) {

charCode = Integer.valueOf(in.substring(charAt, charAt + 2));

if (charCode <= 26) {

curChar = numberToChar.get(charCode);

arrayList.add(curChar);

result.addAll(decodeHelper(numberToChar, in, charAt + 2,

arrayList));

arrayList.remove(arrayList.size() - 1);

}

}

}

return result;

}

}

Output:

Please enter any digit number but combination of 1 to 26 .......

2010

All possible Alphabet codes for the give Number: 2010

taj

baj

btj

tj

btaj

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Here is the code for your own ArrayList program.

- oglA December 17, 2013