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 

Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0

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

Problem Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0 Example **Input : ** 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Output : 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Solution Method 1 - Using the extra space and O(n^2) solution [Read More]
kodeknight  Microsoft  2DArray  java-code  binary array  boolean  matrix  CrackingTheCodingInterview  zero 

Determine if a string has all unique characters

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

Problem: Implement an algorithm to determine if a string has all unique characters. Solution Solution1 - My first algorithm is a straightforward, brute force approach. Basically, we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2) because of the nested loop. bool uniqueChars(string myString) { for (int x = 0; x < myString. [Read More]
kodeknight  String  java-code  Bit Vector  CrackingTheCodingInterview  unique 

Remove duplicate characters in a string

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

Problem Given a string, Write a program to remove duplcate characters from the string. Input String : kodeknight Output String : kodenight Solution Method 1 : Brute force void removeDuplicates(char \*str) { if (!str) return; int len = strlen(str); if (len < 2) return; int tail = 1; for (int i = 1; i < len; ++i) { int j; for (j = 0; j < tail; ++j) if (str\[i\] == str\[j\]) break; if (j == tail) { str\[tail\] = str\[i\]; ++tail; } } str\[tail\] = '\\0'; } Time Complexity : O(N^2) [Read More]
kodeknight  String  java-code  duplicate  CrackingTheCodingInterview  remove-duplicates 

Replace all spaces in a string with “%20″ in c-style string

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

Problem Write a C program that will replace all spaces with ‘%20′ Example Input: “Mr John Smith " Output: “Mr%20John%20Smith Solution The algorithm is as follows: Count the number of spaces during the first scan of the string. Parse the string again from the end and for each character: If a space is encountered, store “%20”. Else, store the character as it is in the newly shifted location. [Read More]
kodeknight  String  java-code  Amazon  spaces  calloc  replace  CrackingTheCodingInterview  malloc 

Check if 2 strings are rotated versions of each other

 Posted on December 31, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem : Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ? OR Assume you have a method isSubstring() which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring.ie: ‘waterbottle’ is a rotation of ‘erbottlewat’ [Read More]
kodeknight  String  java-code  rotated array  CrackingTheCodingInterview 

Finding the Start of a Loop in a Linked List

 Posted on December 27, 2011  (Last modified on August 7, 2020)  |  9 minutes  |  Kinshuk Chandra

Problem  Given a circular linked list, implement an algorithm which returns node at the beginning of the loop. DEFINITION Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list. EXAMPLE input: A -> B -> C -> D -> E -> C [the same C as earlier] output: C Example head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ^ | | | +------------------------+ Answer here is 3. [Read More]
kodeknight  link list  java-code  Single Link List  loop  CrackingTheCodingInterview 

Anagram Checker–To check if 2 strings are anagrams

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

An anagram is a type of word, the result of rearra… Unknown - Jul 1, 2014An anagram is a type of word, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once. For example: orchestra can be rearranged into carthorse or cat can be rearranged into act. We can find out the anagram strings using below algorithm: [Read More]
kodeknight  String  java-code  anagrams  hashes  CrackingTheCodingInterview