Archive

Tag Archives: stream

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

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

Given a sorted integer list and an integer, find two integer in the list such that the sum of the two integers equals the given integer. It is required that the time complexity must be O(n). For example, the sorted integer list is {1, 2, 4, 7, 11, 15} and an integer 15. The output is 4 and 11 since 4 + 11 = 15.

Solution

Since the integer list is sorted, it is actually not that difficult. We have to create 2 pointers, 1 at the head and 1 at the tail. Check the sum of them if they equals the given integer. If not, there are 2 conditions: sum is greater or smaller than the integer. if greated, move the tail pointer backward, else move the head pointer forward.

Example

# foundtion to find the integers
def find_two_suitable_int(list, wanted_sum):

    # check error
    if len(list) <= 1:
        print "list too short to work on"
        return (None, None)

    # pointers
    head = 0
    tail = len(list) - 1

    # find the integers
    while (tail > head):
        sum = list[head] + list[tail]
        if sum == wanted_sum:
            return (list[head], list[tail])
        elif sum > wanted_sum:
            tail = tail - 1
        else:
            head = head + 1

    # shows that no integers are found
    print "can't find suitable integers"
    return (None, None)

# main testing, output should be 11 and 4
list = [1, 2, 4, 7, 11, 15]
(x, y) = find_two_suitable_int(list, 15)
if x: print "the two integers are %s and %s" % (x, y)
#include <iostream.h>

bool FindTwoNumbersWithSum
(
int data[],           // 已经排序的 数组
unsigned int length,  // 数组长度
int sum,              //用户输入的 sum
int& num1,            // 输出符合和等于sum的第一个数
int& num2             // 第二个数
)
{
    bool found = false;
    if(length < 1)
        return found;

    int begin = 0;
    int end = length - 1;

    while(end > begin)
    {
        long curSum = data[begin] + data[end];

        if(curSum == sum)
        {
            num1 = data[begin];
            num2 = data[end];
            found = true;
            break;
        }
        else if(curSum > sum)
            end--;
        else
            begin++;
    }
    return found;
}

int main()
{
    int x,y;
    int a[6]={1,2,4,7,11,15};
    if(FindTwoNumbersWithSum(a,6,15,x,y) )
    {
        cout<<x<<endl<<y<<endl;
    }
    return 0;
}

Extended Question

如果输入的数组是没有排序的,但知道里面数字的范围,其他条件不变,
如何在O(n)时间里找到这两个数字?

关于第14题,

1.题目假定是,只要找出俩个数,的和等于给定的数,
其实是,当给定一排数,
4,5,7,10,12
然后给定一个数,22。
就有俩种可能了。因为22=10+12=10+5+7。
而恰恰与第4题,有关联了。望大家继续思考下。:)。

2.第14题,还有一种思路,如下俩个数组:
1、 2、  4、7、11、15     //用15减一下为
14、13、11、8、4、 0      //如果下面出现了和上面一样的数,稍加判断,就能找出这俩个数来了。

第一个数组向右扫描,第二个数组向左扫描。

Question

Given a linked list, find the Kth last node in a linked list. The last 0th node is the tail node in the linked list.

Solution

Easy task. Construct 2 pointers: P1 and P2. First, both of them are set to head. Move P2 to the next Kth node.

Example

# node structure
class node:
    data = None
    next = None
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

# get item
def get_item(head, k):
    pointer_1 = head
    pointer_2 = head
    for i in xrange(k+1):
        if pointer_2 is not None:
            pointer_2 = pointer_2.next
    while pointer_2 is not None:
        pointer_1 = pointer_1.next
        pointer_2 = pointer_2.next
    return pointer_1

# linked list
node_9 = node(9)
node_8 = node(8, node_9)
node_7 = node(7, node_8)
node_6 = node(6, node_7)
node_5 = node(5, node_6)
node_4 = node(4, node_5)
node_3 = node(3, node_4)
node_2 = node(2, node_3)
node_1 = node(1, node_2)

# main
head = node_1
print get_item(head, 0).data
print get_item(head, 9).data
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode
{
    char data;
    ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;

ListNode* fun(ListNode *head,int k)
{
    pone = ptwo = head;
    for(int i=0;i<=k-1;i++)
        ptwo=ptwo->next;
    while(ptwo!=NULL)
    {
        pone=pone->next;
        ptwo=ptwo->next;
    }
    return pone;
}

int main()
{
    char c;
    head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    p = head;
    while(c !='0')
    {
        q = (ListNode*)malloc(sizeof(ListNode));
        q->data = c;
        q->next = NULL;
        p->next = q;
        p = p->next;
        c = getchar();
    }
    cout<<"---------------"<<endl;
    cout<<fun(head,2)->data<<endl;

    return 0;
}

/////////////////////////////
1254863210
---------------
2
Press any key to continue
////////////////////////////

Question

Sum up 1 to n without using division, multiplication, for loop, while loop, if else, switch and condition statement (A?B:C).

Solution 1

Actually, for loop can be simulated through making use of the static property. Since static value will be stored in the class, we can increase the value every time we init a static class.

#include <iostream.h>

class Temp
{
public:
    Temp() {
        ++N;
        Sum += N;
    }
    static void Reset() { N = 0; Sum = 0; }
    static int GetSum() { return Sum; }

private:
    static int N;
    static int Sum;
};

int Temp::N = 0;
int Temp::Sum = 0;

int solution1_Sum(int n)
{
    Temp::Reset();
    Temp *a = new Temp[n];   //就是这个意思,new出n个数组。
    delete []a;
    a = 0;
    return Temp::GetSum();
}

int main()
{
    cout<<solution1_Sum(100)<<endl;
    return 0;
}

//运行结果:
//5050
//Press any key to continue

Solution 2

既然不能判断是不是应该终止递归,我们不妨定义两个函数。
一个函数充当递归函数的角色,另一个函数处理终止递归的情况,
我们需要做的就是在两个函数里二选一。

从二选一我们很自然的想到布尔变量,
比如ture/(1)的时候调用第一个函数,false/(0)的时候调用第二个函数。
那现在的问题是如和把数值变量n转换成布尔值。

如果对n连续做两次反运算,即!!n,那么非零的n转换为true,0转换为false。

#include <iostream.h>

class A;
A* Array[2];

class A
{
public:
    virtual int Sum (int n) { return 0; }
};

class B: public A
{
public:
    virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};

int solution2_Sum(int n)
{
    A a;
    B b;
    Array[0] = &a;
    Array[1] = &b;
    int value = Array[1]->Sum(n);
    //利用虚函数的特性,当Array[1]为0时,即Array[0] = &a; 执行A::Sum,
    //当Array[1]不为0时,即Array[1] = &b; 执行B::Sum。
    return value;
}

int main()
{
    cout<<solution2_Sum(100)<<endl;
    return 0;
}

//5050
//Press any key to continue

 

%d bloggers like this: