A Needle in the Haystack

 Posted on May 5, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem  The program has to detect all occurences of the needle in the haystack. It should take the needle and the haystack as input, and output the positions of each occurence, as shown below. Input The input consists of a number of test cases. Each test case is composed of three lines, containing: the length of the needle, the needle itself, the haystack. Output For each test case your program should output all positions of the needle’s occurences within the haystack. [Read More]
kodeknight  String  KMP algorithm 

Match two board configurations of tic-tac-toe problem

 Posted on May 5, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem How will you match two board configurations of tic-tac-toe problem? Solution This is a quite unexpected interview question as it has nothing to do with your programming skills or algorithms. This is a plain simple question designed to check your problem solving skills. Consider the tic-tac-toe configurations : The trick in this question is that any board configuration is rotation invariant and what we mean by that is all 2 the configurations shown above are similar and must match in the logic we use for checking board configurations. [Read More]
kodeknight  game  maths  understand 

Given a set of numbers [1-N]. Subsets such that the sum of numbers in the subset is a prime number.

 Posted on May 5, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number. Solution  Method 1 - Using DP Maximum sum can be = N*(N+1) / 2 for any subset considered, as numbers are from 1 to N. Hence put S = (N*(N+1) / 2) in subset sum problem. For each number in the Sum S, check if there is subset of numbers from 1 to N that sum up to S - Yes that you can do with Subset Sum problem. [Read More]
kodeknight  Dynamic Programming  DP  subset  understand 

Petrol Bunk in a Circle.

 Posted on May 5, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem You have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit. [Read More]
kodeknight  Dynamic Programming  DP  google 

Get Sentence from raw text

 Posted on May 4, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

DP Code Given Above Has Some Issue I Fixed It: st… PaNThErA - Dec 0, 2015DP Code Given Above Has Some Issue I Fixed It: static boolean wordBreak(String str, Set tokenMap) { int size = str.length(); if (size == 0) return true; // Create the DP table to store results of subroblems. The value wb[i] // will be true if str[0..i-1] can be segmented into dictionary words, // otherwise false. [Read More]
backtracking  kodeknight  String  java-code  Dynamic Programming  DP  recursion  parse  understand 

Get Sentence from raw text

 Posted on May 4, 2014  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Problem Given a raw sentence without spaces and dictionary of words, break the raw sentence to sentence of words. String getSentence(String text, Setdictionary); // text is a string without spaces, you need to insert spaces into text, so each word seperated by the space in the resulting string exists in the dictionary, return the resulting string This problem is also known as wordbreaker problem. Example // getSentence(“iamastudentfromwaterloo”, {“from, “waterloo”, “hi”, “am”, “yes”, “i”, “a”, “student”}) -> “i am a student from waterloo” [Read More]
backtracking  kodeknight  String  java-code  Dynamic Programming  DP  recursion  parse  understand 

Count the number of digits in the number

 Posted on May 4, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given the integer, find the number of digits in the integer. Solution Method 1 - Brute force using loop Keep dividing the number, until it is 0. This will give us the count of number. Java code public static int getSize(long number) { int count = 0; while (number > 0) { count += 1; number = (number / 10); } return count; } Method 2 - Convert to string [Read More]
kodeknight  divide and conquer  count 

Finding the next palindrome for the given number

 Posted on May 4, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Hi Chandra, In Method 2, How would you handle a n… Vinay Sarang - Sep 6, 2014Hi Chandra, In Method 2, How would you handle a number with odd digits. Ex :: 31451 then output has to be 31513. Could you please share the algo for it. Thanks in advance, Vinay Keep the middle number somewhere, so the number will become, first+middle+reverse(first). Increment first until we get the right pallindrome. [Read More]
kodeknight  palindrome 

Finding the next palindrome for the given number

 Posted on May 4, 2014  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Problem Given a number, find the next smallest palindrome larger than this number. Example For example, if the input number is “2 3 5 4 5″, the output should be “2 3 6 3 2″. And if the input number is “9 9 9″, the output should be “1 0 0 1″. The input is assumed to be an array. Every entry in array represents a digit in input number. Let the array be ‘num[]‘ and size of array be ‘n’ [Read More]
kodeknight  palindrome 

Given the push and pop sequence on stack, verify if corresponding sequence is correct or not

 Posted on May 4, 2014  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Problem Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not.  Example For example, if 1, 2, 3, 4, 5 is a push sequence, 4, 5, 3, 2, 1 is a corresponding pop sequence, but the sequence 4, 3, 5, 1, 2 is not. Solution An intuitive thought on this problem is to create an auxiliary stack. [Read More]
kodeknight  stack