Archive

Tag Archives: string

Question

Write an algorithm to identify prime numbers from a list of numbers ranging 0-100.

Solution

The main question is actually to write a program to check if a number is prime. There are 4 situations.

1. If number is 0 or 1, it is not prime.

2. if the number is 2, it is prime.

3. if the number is even, it is not prime.

4. if number is greater than 3, and not divisible by all odd numbers (except 1)  smaller than the square root of the input number, it is prime.

Sample

public class InterviewPracticeExtra05
{
	private static boolean is_prime(int input)
	{
		if (input <= 1) return false;
		if (input == 2) return true;
		if (input % 2 == 0) return false;
		for (int i = 3; i * i <= input; i += 2) {
			if (input % i == 0) return false;
		}
		return true;
	}

	public static void main(String[] args)
	{
		for (int i = 0; i <= 100; i++) {
			if (is_prime(i)) System.out.println(i);
		}
	}
}

Reference

Glassdoor

Question

Write a program to right-rotate a string by m characters. Right-rotating a string means moving m characters at the left of string to the right. Is it required the time complexity is O(n) and helper memory size is O(1). For example, right-rotate “abcdefghi” by 3 characters gives “defghiabc”.

Solution

There are 2 ways to do it. The first one is that we divide the string into 2 parts (XY). X is the part to move to the right and Y is the one moving on to the left. Reverse them in place 2 times.

XY: "abcdefghi"
R(X) R(T): "cbaihgfed"
YX: "defghiabc"

Secondly we can swap character one by one. Let p0 at position 0, p1 at position m. Swap their characters repeatedly with moving both pointer right by 1.

abcdefghij
dbcaefghij
decabfghij
defabcghij
defgbcahij
defghcabij
defghiabcj
defghijbca  <- p1 doesn't move since it reaches the end
defghijacb
defghijabc
#include <iostream>

// reverse the string between start and end
void reverse_string(char* start_pointer, char* end_pointer)
{
	while (start_pointer < end_pointer) {
		char temp_char = *start_pointer;
		*start_pointer = *end_pointer;
		*end_pointer = temp_char;
		start_pointer++;
		end_pointer--;
	}
}

// solution 1
void left_rotate_string_1(char* string_pointer, int n)
{
	if (string_pointer == NULL) return;

	int length = strlen(string_pointer);
	if (n > length || n <= 0) return;

	char* first_start_pointer = string_pointer;
	char* first_end_pointer = string_pointer + n - 1;
	char* second_start_pointer = string_pointer + n;
	char* second_end_pointer = string_pointer + length - 1;
	reverse_string(first_start_pointer, first_end_pointer);
	reverse_string(second_start_pointer, second_end_pointer);
	reverse_string(first_start_pointer, second_end_pointer);
}

// solution 2
void left_rotate_string_2(char* string_pointer, int n)
{
	if (string_pointer == NULL) return;

	int length = strlen(string_pointer);
	if (n > length || n <= 0) return;

	char* pointer_1 = string_pointer;
	char* pointer_2 = string_pointer + n;
	char* pointer_end = string_pointer + length - 1;
	while (pointer_1 != pointer_2) {
		char temp_char = *pointer_1;
		*pointer_1 = *pointer_2;
		*pointer_2 = temp_char;
		if (pointer_1 != pointer_end) pointer_1++;
		if (pointer_2 != pointer_end) pointer_2++;
	}
}

// main
int main()
{
	char string_1[] = "abcdefghij";
	left_rotate_string_1(string_1, 3);
	printf("%sn", string_1); // defghijabc

	char string_2[] = "abcdefghij";
	left_rotate_string_2(string_2, 3);
	printf("%sn", string_2); // defghijabc
}

Question

Given a function prototype: int continumax(char *output_string,char *input_string). Implement it to find the longest consecutive digits. This function must return the length of the longest digits. The found longest digits should be written to the memory location that output_string is pointing. For example, if input_string is “abcd12345ed125ss123456789”, function returns 9 and output_string becomes “123456789”.

Solution

This question must be implemented in C/C++. Just skip letters, count the length and save the head position to a temp pointer.

Sample

#include <iostream>

int continumax(char *output_string, char *input_string)
{
	int max_length = 0;
	char *max_string = new char[sizeof(input_string)];

	while (true) {

		// skip all non-digit characters
		while (*input_string != 0 && (*input_string < '0' || *input_string > '9')) input_string++;
		if (*input_string == 0) break;

		// current char is digit
		int length = 0;
		char *temp_string = input_string;
		while (*input_string!=0 && *input_string >= '0' && *input_string <= '9') {
			length++;
			input_string++;
		}

		// check if this is longer
		if (length > max_length) {
			max_length = length;
			max_string = temp_string;
		}
	}

	// write maximum string to output and add null to end.
	int i;
	for (i = 0; i < max_length; i++) output_string[i] = max_string[i];
	output_string[i] = 0;

	return max_length;
}

int main()
{
	char input[] = "abcd12345ed125ss123456789";
	char *output = new char[sizeof(input)];
	int length = continumax(output, input);
	printf("Length: %dn", length);
	printf("Output: %sn", output);
}

Question

Given a integers m and n, generate all combination within 1 to n that would give the sum m. For example, for m=5 and n=5, the combinations are {5}, {4+1}, {3+2}.

Solution

This is a knapsack problem.

# knapsack that store the found combination
knapsack = array

# find combination of 1..n with sum target
find_combination(target, n)
    if target <= 0 or n <= 0 then return
    if target == n then found()

    # put n to knapsack, find combination involves n
    push n to knapsack
    remain = target - n
    find_combination(remain, n-1)

    # remove n from knapsack, find combination involves n-1
    pop knapsack
    find combination(target, n-1)

Sample

# knapsack that store the found combination
knapsack = []

# what to do with found combination in knapsack
def found(n):
    for number in knapsack: print "%d +" % number,
    print n

# find combination
def find_combination(target, n):
    if n <= 0 or target <= 0: return
    if n == target: found(n)

    # find combinations with n
    knapsack.append(n)
    find_combination(target - n, n - 1)

    # find combinations without n
    knapsack.pop()
    find_combination(target, n - 1)

# find combination of 25 with 1..20
find_combination(25, 20)
#include <iostream>
#include <list>
using namespace std;

list<int> knapsack;

void found(int n)
{
	// reverse print
	for (list<int>::const_iterator item = knapsack.begin(); item != knapsack.end(); item++)
		printf("%d + ", *item);
	printf("%dn", n);
}

void find_combination(int target, int n)
{
	if (n <= 0 || target <= 0) return;
	if (n == target) found(n);
	knapsack.push_back(n);
	find_combination(target - n, n - 1);
	knapsack.pop_back();
	find_combination(target, n - 1);
}

int main()
{
	find_combination(25, 20);
}
import java.util.Stack;

public class InterviewPractice21
{
	private static Stack<Integer> snapsack = new Stack<Integer>();

	private static void found(int n)
	{
		for (int item : snapsack) System.out.printf("%d + ", item);
		System.out.printf("%dn", n);
	}

	private static void find_combination(int target, int n)
	{
		if (target <= 0 || n <= 0) return;
		if (n == target) found(n);
		snapsack.push(n);
		find_combination(target - n, n - 1);
		snapsack.pop();
		find_combination(target, n - 1);
	}

	public static void main(String[] args)
	{
		find_combination(25, 20);
	}
}

Question

Convert the inputted string to an integer. For example, “345” will output 345.

Solution

Though it looks simple, in fact it is pretty tricky. First we need to make the concept clear.

1. Scan each character from the left to right, then multiply the previously obtained integer by ten before adding the scanned digit to it.

2. Integer can be positive or negative, check if the first character is ‘+’ or ‘-‘.

3. Check for exceptions such as non-digit or null input.

4. Check for overflow. Overflow means the inputted integer is greater than the maximum size of integer that can be stored in memory. In this case we should output 0, or throw an exception.

string_to_integer(string)
  if string is null then return 0
  positive_int = true
  long_number = 0
  for i equals 0 to length of string
    if i == 0
      if string[i] == '+' then
        continue
      else if string[i] == '-' then
        positive_int = false
        continue
    if string[i] >= 0 and string[i] <= 9 then
      digit = string[i] - '0'
      long_number = long_number * 10 + digit
      if int_overflow(long_number) then
        long_number = 0
        throw exception
    else
      long_number = 0
      throw exception
  if not positive_int then
    long_number = 0 - long_number
  return long_number

Example

import sys

def int_overflow(long):
    return not -sys.maxint-1 <= long <= sys.maxint

def string_to_integer(string):
    if string is None: return 0
    positive_int = True
    long_number = 0
    for i in xrange(0, len(string)):
        print string[i]
        if i == 0:
            if string[i] == '+':
                continue
            elif string[i] == '-':
                positive_int = False
                continue
        if ord('0') <= ord(string[i]) <= ord('9'):
            digit = ord(string[i]) - ord('0')
            long_number = long_number * 10 + digit
            if int_overflow(long_number):
                long_number = 0
                return Exception('integer overflew')
        else:
            long_number = 0
            return Exception('invalid digit in string')
    if not positive_int:
        long_number = 0 - long_number
    return long_number

print string_to_integer('-345')
enum Status {kValid = 0, kInvalid};
int g_nStatus = kValid;

int StrToInt(const char* str)
{
      g_nStatus = kInvalid;
      long long num = 0;

      if(str != NULL)
      {
            const char* digit = str;

            // the first char in the string maybe '+' or '-'
            bool minus = false;
            if(*digit == '+')
                  digit ++;
            else if(*digit == '-')
            {
                  digit ++;
                  minus = true;
            }

            // the remaining chars in the string
            while(*digit != '/0')
            {
                  if(*digit >= '0' && *digit <= '9')
                  {
                        num = num * 10 + (*digit - '0');

                        // overflow
                        if(num > std::numeric_limits<int>::max())
                        {
                              num = 0;
                              break;
                        }

                        digit ++;
                  }
                  // if the char is not a digit, invalid input
                  else
                  {
                        num = 0;
                        break;
                  }
            }

            if(*digit == '/0')
            {
                  g_nStatus = kValid;
                  if(minus)
                        num = 0 - num;
            }
      }
      return static_cast<int>(num);
}

Question

Given a string, write an algorithm to find the character inside that appeared only once. For example, the result for string “abaccdeff” is b.

Solution

We can use a hashtable to count the appearance times for each character. Then rescan the hashtable for the character that appeared only once. These two step take O(n) each, therefore the overall time complexity is O(n).

# function to find char appeared once
def find_appeared_once(string):
    hashtable = {} # a hashtable

    # loop for each char in string
    for char in string:
        if char not in hashtable:
            hashtable[char] = 1
        else:
            hashtable[char] += 1

    # find the item appeared only once
    for char, count in hashtable.items():
        if count == 1:
            return char

# main
print find_appeared_once('abaccdeff')

 

#include <iostream.h>
#include <string.h>

char FirstNotRepeatingChar(char* pString)
{
      if(!pString)
            return 0;

      const int tableSize = 256;
      unsigned int hashTable[tableSize];
      for(unsigned int i = 0; i < tableSize; ++ i)
            hashTable[i] = 0;

      char* pHashKey = pString;
      while(*(pHashKey) != '/0')
            hashTable[*(pHashKey++)] ++;

      pHashKey = pString;
      while(*pHashKey != '/0')
      {
            if(hashTable[*pHashKey] == 1)
                  return *pHashKey;

            pHashKey++;
      }

      return *pHashKey;
}

int main()
{
    cout<<"请输入一串字符:"<<endl;
    char s[100];
    cin>>s;
    char* ps=s;
    cout<<FirstNotRepeatingChar(ps)<<endl;
    return 0;
}

//////////////////////////////////////////
请输入一串字符:
abaccdeff
b
Press any key to continue
///////////////////////////////////////////

 

 

Question

Simple task, reverse words in a sentence.

Solution

In Python, this can be simple because of the build-in functions. We can just split the sentence by spaces, reverse the list, and join them with spaces again.

In C++, this can be complicated. The following might be one of the possible answers. We have to scan from the head to tail, and find the position that a word starts and ends. Then reverse the letters in this word. At the end, reverse all the letters in the whole sentence.

Examples

# function to reverse a sentence
def reverse_sentence(sentence):
    return ' '.join(reversed(sentence.split()))

# main
print reverse_sentence("I am a student.")
print reverse_sentence("Testing 1 2 3")
#include <iostream>

using namespace std;

// function to reverse a word, in place
void reverse_word(string* word, int begin, int end)
{
	while (begin < end) {
		char letter = word->at(begin);
		word->at(begin) = word->at(end);
		word->at(end) = letter;
		begin++;
		end--;
	}
}

// function to reverse a sentence, in place
void reverse_sentence(string* sentence)
{
	int length = sentence->size();
	int pointer = 0;
	// for each character
	for (int i = 0; i < sentence->size(); i++) {
		// find word head
		if (pointer == -1) {
			if (sentence->at(i) != ' ') pointer = i;
			continue;
		}
		// find word tail
		if (sentence->at(i) == ' ') {
			reverse_word(sentence, pointer, i - 1);
			pointer = -1;
		}
		// end of string
		if (i == length - 1) {
			reverse_word(sentence, pointer, i - 1);
		}
	}
	// reverse letters for the whole sentence
	reverse_word(sentence, 0, sentence->size() - 1);
}

// main part
int main()
{
	string text = "I am a student.";
	reverse_sentence(&text);
	cout << text << endl;
}
public class InterviewPractice10
{
	private static String reverse_sentence(String sentence)
	{
		String[] splited = sentence.split(" ");
		StringBuilder builder = new StringBuilder();
		for (int i = splited.length - 1; i >= 0; i--) {
			builder.append(splited[i]);
			if (i > 0) builder.append(" ");
		}
		return builder.toString();
	}

	public static void main(String[] args)
	{
		System.out.println(reverse_sentence("I am a student."));
		System.out.println(reverse_sentence("Testing 1 2 3"));
	}
}
%d bloggers like this: