CareerCup

I also want to know

linear search，binary search

#include <iostream>

using namespace std;

void reverse_by_word(char *str) {
    if (*str == '\0') {
        return;
    }
    char p[100];
    int index = 0;
    while (*str != ' ' && *str != '\0') {
        p[index++] = *str;
        ++str;
    }
    p[index] = '\0';
    reverse_by_word(++str);
    cout << p << " ";

}

int main() {
    char *str = "hello world";
    reverse_by_word(str);
    cout << endl;
}

c++

when x = 1, y = 1, we got x = 5, y = 8 after that

It' my solution:

#include <iostream>

using namespace std;

int main() {
    int final_sum;
    cin >> final_sum;
    int array[10] = {11, 1, 3, 9, 10, 2, 5, 7, 4, 8};
    int i = 0, j = 0, sum = array[0];
    while (j < 10) {
        while (sum < final_sum) {
            ++j;
            if (j >= 10) break;
            sum += array[j];
        }
        if (j >= 10) break;
        if (sum == final_sum) {
            for (int k = i; k <= j; ++k)
                cout << array[k] << " ";
            cout << endl;
            sum -= array[i];
            ++i;
        } else {
            sum -= array[i];
            ++i;
            sum -= array[j];
            --j;
        }
    }
    return 0;
}

It' my solution:

#include <iostream>

using namespace std;

int main() {
    int final_sum;
    cin >> final_sum;
    int array[10] = {11, 1, 3, 9, 10, 2, 5, 7, 4, 8};
    int i = 0, j = 0, sum = array[0];
    while (j < 10) {
        while (sum < final_sum) {
            ++j;
            if (j >= 10) break;
            sum += array[j];
        }
        if (j >= 10) break;
        if (sum == final_sum) {
            for (int k = i; k <= j; ++k)
                cout << array[k] << " ";
            cout << endl;
            sum -= array[i];
            ++i;
        } else {
            sum -= array[i];
            ++i;
            sum -= array[j];
            --j;
        }
    }
    return 0;
}

just valid or invalid?

1,2,3,6,7,14,15 another solution

merge sort first and then quickselect

#include <iostream>

using namespace std;

void reverse_array(int array[], int index, int len) {
    if (index >= len - 1) return;
    array[index] = array[index]^array[len - 1];
    array[len - 1] = array[index]^array[len - 1];
    array[index] = array[index]^array[len - 1];
    reverse_array(array, index + 1, len - 1);
}

int main() {
    int array[10];
    for (int i = 0; i < 10; ++i) 
        array[i] = i;
    reverse_array(array, 0, 10);
    for (int i = 0; i < 10; ++i) 
        cout << array[i] << endl;
}

I also use the same way. I also can't prove it! anyone?

two pointer: the pfirst goes n steps first then with psecond from start together, when the pfirst arrives at the end, the psecond point the nth node form the end.

find all the odds less than n, and bfs or dfs without marking the odd is used or not

@candis we should make distinction between the probability of read a line and the probability of get a line.
The probability of get a line = the probability of read a line * the probability not read the lines after the current line

equals 1 % (5 + 8) or 1 % 5 + 8?
in-order traversal?

@candis the probability to choose n - 2 line when there are n lines in the file is: 1 / (n - 2) * (n - 2) / (n - 1) * (n - 1) / n = 1 / n. and so on, for any line, the probability is 1 / n.

for {'a', 'b', ''c}:
000 {}
001 {'a'}
010 {'b'}
011 {'a', 'b'}
100 {'c'}
101 {'a', 'c'}
110 {'b', 'c'}
111 {'a', 'b', 'c'}

In the book 《programming pearls》 second edition, the 12th capter and the 10th question in the exercise. At last, the probabilty to choose any line is 1/n.
when there are n lines. the probabilty to choose n - 1line is 1 / (n - 1) * (n - 1) / n = 1/ n
the probabilty to choose n - 1 * the probability not choose n.

segment the s into tokens which are 4 charater length. Using the 4 characters' token as key to build inverted index.

for a sorted array, 3 sum problem can be done in O(n):

1 # !/usr/bin/python
  2 # -*- encoding: utf-8 -*-
  3 
  4 array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
  5 
  6 three_sum = 15
  7 
  8 start = 0
  9 end = 8
 10 while start <= end:
 11     if array[start] + array[end] == three_sum:
 12         print '%d\t%d\t=\t%d' % (array[start], array[end], three_sum)
 13         break
 14     elif array[start] + array[end] > three_sum:
 15         end -= 1
 16     elif array[start] + array[end] < three_sum:
 17         start += 1

I want to know why?

I think we can build an inverted list with positions from the raw string just with the keys from map, and check weather the inverted list has successive positions or not.

If this methods makes sense to anyone, please let me know.

The words in the examples are not successive!
If not need successive, we can use inverted list without postion, if need, we can use inverted list with position.
am I right?

1 # !/usr/bin/python
  2 # -*- encoding: utf-8 -*-
  3 
  4 class DoubleStackQueue:
  5 
  6     def __init__(self):
  7         self.first_stack = []
  8         self.second_stack = []
  9 
 10     def en_queue(self, el = None):
 11         self.first_stack.append(el)
 12 
 13     def de_queue(self):
 14         if len(self.second_stack) == 0:
 15             while len(self.first_stack) != 0:
 16                 self.second_stack.append(self.first_stack.pop())
 17         return self.second_stack.pop()
 18 
 19 if __name__ == '__main__':
 20     queue = DoubleStackQueue()
 21     queue.en_queue(1)
 22     queue.en_queue(2)
 23 
 24     print queue.de_queue()
 25     print queue.de_queue()
 26 
 27     queue.en_queue(3)
 28     print queue.de_queue()

how about this method?

1 #!/usr/bin/python
  2 #-*- encoding: utf-8 -*-
  3 
  4 a = [4, 7, 5, 1, 3, 8, 9, 6, 2]
  5 
  6 def find_max_until(a, max_value, max_index):
  7     tmp_max = 0
  8     tmp_index = 0
  9     for index in range(max_index):
 10         if tmp_max < a[index] and a[index] < max_value:
 11             tmp_max = a[index]
 12             tmp_index = index
 13     return tmp_max, tmp_index
 14 max_value = 100
 15 max_index = len(a)
 16 for i in range(3):
 17     max_value, max_index = find_max_until(a, max_value, max_index)
 18     print max_value, max_index