Convert String to ZigZag Bottom Up

 Posted on March 30, 2016  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) Example P A H N A P L S I I G Y I R ```And then read line by line: `"PAHNAPLSIIGYIR"` Write the code that will take a string and make this conversion given a number of rows: string convert(string text, int nRows); ````convert(“PAYPALISHIRING”, 3) should return "PAHNAPLSIIGYIR"`. [Read More]
String  zigzag  leetcode 

Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

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

Problem Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution Method 1 - Using hashset on str2 and boolean array or hashset on str2 Break down the problem into two tasks. i) Finding the non-unique i.e. repeating elements in str 1. Hashing can be used for this purpose. ii) Finding if all the characters hashed in the first string are available in the second string. [Read More]
kodeknight  String  two-string  Amazon  Interview Question  unique 

Given an array filled with char elements, find the max length of continuous white space

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

Problem Given array filled with char elements, can you suggest a most efficient way to find the max length of continuous white space? Solution Scan the array left to right, keep a count of white space. When you reach a non-whitespace character, check that count against the current max; if it’s higher, it becomes the new max. Set the count back to zero, continue scanning. Time complexity - O(n) [Read More]
max  String  morgan-stanley 

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 

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 

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 

Print letters followed by their frequency (Run Length Encoding)

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

Given a string ,Write a program to print letter followed by it’s frequency.This is also knows as Run Length Encoding. Example: Input aaabcc Output a3b1c2 Algorithm: 1.Pick the first character from the string and print it. 2.Count the number of subsequent occurrences of the picked character and then print the count. 3.Pick the next character and repeat step 2 till we reach end of the String. #include <iostream> #include<string> using namespace std; int main() { string str = "aaabcc"; int count=0; int i=0,j; int l = str. [Read More]
kodeknight  String  frequency  encoding 

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 (strii == strjj) break; if (j == tail) { strtailtail = strii; ++tail; } } strtailtail = '\\0'; } Time Complexity : O(N^2) [Read More]
kodeknight  String  java-code  duplicate  CrackingTheCodingInterview  remove-duplicates 

Find first non repeating character in a string

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

You are given a string, find its first non-repeating character?

Algorithm:

  1. Scan the string from left to right and construct the count array.
  2. Again, scan the string from left to right and check for count of each character, if you find an element who’s count is 1, return it.

Code :

#include<stdlib.h>  
#include<stdio.h>  
#define NO\_OF\_CHARS 256  
  
/\* The function returns index of first non-repeating  
   character in a string \*/  
int getFirstNonRepeating(char \*str)  
{  
 int \*count = (int \*)calloc(sizeof(int), NO\_OF\_CHARS);  
 int i;  
 for (i = 0; \*(str+i);  i++)  
   count\[\*(str+i)\]++;  
 int index = -1;  
  
 for (i = 0; \*(str+i);  i++)  
 {  
  if(count\[\*(str+i)\] == 1)  
  {  
    index = i;  
    break;  
  }  
 }  
 return index;  
}

Time complexity: O(N)

kodeknight  String  duplicate