Bạn sẽ "viết 1 hàm tìm số có giá trị lớn thứ 2 trong dãy số cho trước" như thế nào?

ktd · May 12, 2016, 7:49am

Hi. Mình không xy ly truong hop mang co 1 phan tu nhe.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    //int arr_a[17] = {19, 0, 5, 7, 13, 15, 11, 6, 4, 5, 102, 11, 15, 15, 16, 18, 19};
    int arr_a[7] = {0,0,0,0,0,0,0};
    int max = arr_a[0];
    int max2 = 0;
    int i;
    //printf("%d", length_array);
    for (i = 0; i < 7; ++i) {
        printf("%d ", arr_a[i]);
    }
    printf("\n");
    for (i = 1; i < 7; ++i) {
        if ( arr_a[i] > max) {
            max = arr_a[i];
            max2 = arr_a[i-1];
        }
        else {
            if (max2 < arr_a[i]) {
                max2 = arr_a[i];
            }

        }
    }

    printf("\n");
    if (max2 == max)
        printf("tat ca phan tu trong mang = nhau");
    else
        printf("%d", max2);
    return 0;
}

nghia · May 12, 2016, 7:50am

Ok, đồng ý với bạn. Cần phải giải quyết tất cả các exception !

tdl · May 12, 2016, 7:52am

Nếu hàng dùng 1 lần thì

for (i = 0; i < sophantu; i++){
		if(a[i] > Smax_denhat){
			Smax_denhi = Smax_denhat;
			Smax_denhat = a[i];
		}
	}
if (Smax_denhi == Smax_denhat)
	printf("Mang nay co van de ma tui hong biet van de gi.");

Bookmark topic lại để dành

nguyenchiemminhvu · May 12, 2016, 8:06am

Đề không yêu cầu dùng vòng lặp gì thì em dùng vòng lặp while vậy

Sắp xếp mảng giảm dần, xong rồi tìm phần tử khác phần tử thứ nhất đầu tiên thứ nhất.
Phải vậy không anh @ltd

#include <iostream>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;

void find_max2(vector<double> &v)	{

	if (v.empty() || v.size() == 1)	{
		cout << "Non-sense input!" << endl;
		return;
	}

	std::sort(v.begin(), v.end(), [](double a, double b)	{ return a > b; });
	
	int i = 0, after_i = i + 1;
	while (i < v.size() - 1 && v[after_i] == v[i])	{
		i = after_i;
		after_i++;
	}

	if (v[after_i] == v[i])
		cout << "All elements have the same value" << endl;
	else
		cout << "Result: " << v[after_i] << endl;
}

int main()	
{
	vector<double> vec;

	int n;
	cout << "Enter number of elements: ";
	cin >> n;
	for (int i = 0; i < n; i++)	{
		vec.push_back(rand());
		cout << vec[i] << " ";
	}
	cout << endl;

	find_max2(vec);

	system("pause");
	return 0;
}

postace · May 12, 2016, 8:11am

Đề bài không giới hạn gì, nên em sẽ dùng cách bình thường nhất :

Tìm max
Duyệt mảng, tìm phần tử lớn thứ 2

ltd · May 12, 2016, 8:27am

Cách đó cũng ổn, nhưng có cách tốt hơn, cũng không khó mấy. Ví dụ như cách của @nguyenchiemminhvu

Vì Đã có câu trả lời của @nguyenchiemminhvu nên Đạt chia sẻ thế này.

Khi mình đi làm, không có chuyện giới hạn sẽ phải làm trong 1 vòng lặp hay hai vòng lặp. Nhớ một điều là hw thì rẻ mà developer thì mắc.

Nếu mình mắc thì nên đáng giá của nó. Mình có giá thì người khác cũng vậy, tức là viết code làm sao để người sau đọc hiểu và code theo nhanh nhất có thể.

Lúc đi học có ta có thể viết một hàm với rất nhiều if else loạn xạ. Giúp cho chương trình chạy nhanh hơn vài phần triệu giây. Nhưng làm cho developer khác tốn vài phút hoặc 1 ngày hoặc vài ngày chỉ để debug. Vậy có đáng không?

Solution lúc Đạt đi học sẽ là một vòng lặp với nhiều if else, cuối cùng chạy được. Nhưng rất khó hiểu và khó debug.
Solution lúc Đạt đi làm sẽ là xem thử ngôn ngữ có hỗ trợ hàm sort không, vì dụ như C++ STL hỗ trợ std::sort. Hoặc C hỗ trợ qsort. Hãy sử dụng nó, các hàm này là các hàm tối ưu tốt hơn hàm mình tự viết nhiều. Đừng reinvent the wheel.

Các bước thực hiện như sau:

1. Sắp sếp giảm dần mảng đã cho
- hàm sort của thư viện sẽ cho ra kết quả tối ưu nhất có thể trong khi ta tốn 1 phút để code dòng code này.
1. kiểm tra từ 1 tới n của mảng, nếu thấy số nhỏ hơn mang[0] thì đó chính là số max thứ 2

Ưu điểm:

Code nhanh, hàm sort tối ưu, logic đơn giản dễ debug.

Nhược điểm

Có thể chậm hơn chương trình if else tá lả vài phần triệu giây

Code C

#include <stdio.h>
 
int get_second_max(int * array, int len);
 
int main() {
    int array[10] = {1,2,9,9,9,3,4,5,7,0};
    printf("get_second_max: %d\n", get_second_max(array, 10));
}
 
int cmp_int (const void * a, const void * b)
{
    return ( *(int*)b - *(int*)a );
}
 
int get_second_max(int * array, int size) {
    int max;
    int second_max;
    int i;
 
    qsort (array, size, sizeof (int), cmp_int);
    max = second_max = array[0];
 
    for(i = 1; i < size; ++i) {
        if ( max > array[i] ) {
            second_max = array[i];
            break;
        }
    }
 
    return second_max;
}

Code ++ có thể xem bài của Vũ:

nghia · May 12, 2016, 8:33am

Em ko đồng ý cách làm của @ltd cho lắm. code của a rất dễ hiểu nhưng qsort có time complexity avg là nlogn (worst case O(n^2 )). Thuật toán của e sẽ nhanh hơn a nếu n lớn.

ltd · May 12, 2016, 8:43am

OK, đó là lý thuyết. Nhưng Đạt hỏi Nghĩa là khi n lớn cỡ như thế nào thì mới xảy ra trường hợp này? Thực tế một chút, khi nào thì mình sẽ làm những công việc xử lý dữ liệu lớn thế này?

Requirements lúc đó sẽ khác rất nhiều, thời gian dành cho việc viết một thuật toán if-else loạn xạ nên dành ra để xem thử sort nào phù hợp với data của mình.

Ví dụ: dựa vào input của mình, tức là cái mảng nhận vào, mình sẽ tìm ra được thuật toán có best case. Gọi thư viện để sử dụng thuật toán phù hợp, sort, làm lại tương tự.

Tức là ta sẽ viết một cái interface nữa, dựa vào loại input, ta sẽ gọi thuật toán sort phù hợp. Code vẫn nhanh, logic vẫn dễ hiểu. Nên nhớ là thời gian code ngắn hơn thời gian debug và fix lỗi.

nghia · May 12, 2016, 8:52am

Em đồng ý với anh, em chưa đi làm nhưng sẽ tiếp thu ý kiến của anh về việc code đơn giản, dễ hiểu còn hơn là if else tá lả để rồi debug. Anh nghĩ nếu 1 ngày nào đó em đi phỏng vấn và anh là người phỏng vấn em thì anh thích được nghe câu trả lời nào hơn ( qsort hay if else tá lả) ?

nguyenchiemminhvu · May 12, 2016, 8:58am

Cứ trả lời hết cả 2 trường hợp luôn cho chắc

Gio · May 12, 2016, 9:54am

Dùng cái set hoặc hàm unique trong c++ cho tiện

template<class T>
T * findmax_k(vector<T> & v,int k){
      sort(v.begin(),v.end());
      auto it=unique(v.begin(),v.end());
      int size=distance(v.begin(),it);
      if(size<k) return NULL;
      return new T(*(it-k));
}

dangxunb · May 12, 2016, 9:16am

Bạn biết cả 2 và chỉ ra được cái hay cái dở của cả 2 cái thì ai chả thích.

ltd · May 12, 2016, 9:31am

@nghia, anh sẽ tuyển @Gio Vì @Gio sử dụng đúng công cụ cho đúng vấn đề.

@nghia cái quan trọng là cách em trình bày, em có thể nói rằng em thích làm cái này bởi vì …

Chỉ cần em thuyết phục được người phỏng vấn là được. Anh có đọc được ở đâu đó thì khả năng thuyết phục quan trọng hơn, làm sao em thuyết phục được khách hàng mua hoặc sử dụng sản phẩm của mình rất quan trọng.

Em đi phỏng vấn tức là đi “bán thân”, phải marketing sản phẩm thiệt ngon người ta mới “mua” lận.

frostphantom · May 12, 2016, 9:58am

em đã đọc đi đọc lại đề của anh đạt và trên voz rùi và em chắc chắn không thấy chỗ nào kêu phải dùng C hay C++ cả, vậy check nhanh cái máy có high-level language nào dùng cho tiện

def f(l):
    l1 = l
    m = max(l)
    l1 = [x for x in l if x!=m] 
    return max(l1)

Itachi_Citus · May 12, 2016, 9:52am

https://ideone.com/JAc9lC

frostphantom · May 12, 2016, 9:59am

hì hì, sửa rùi, em nhầm

Itachi_Citus · May 12, 2016, 10:04am

Thật ra giải pháp của @frostphantom tốt hơn của anh Đạt với @Gio nè, vừa “xài đúng công cụ cho đúng vấn đề”, vừa đảm bảo về mặt độ phức tạp thuật toán, tuy nhiên điểm yếu tiêu tốn thêm bộ nhớ.

ltd · May 12, 2016, 10:07am

À không, anh sẵn đang code C nên làm một cái bằng C ấy mà.
Dùng cái nào cũng được cả.

Code ví dụ của anh không chuẩn, vẫn có lỗi, không kiểm tra input etc… nhưng cái anh muốn nói tới là đừng có tập trung quá nhiều vào performance khi ta không có yêu cầu cụ thể về performance.

Cái quan trọng là logic đọc dễ hiểu. Vấn đề này software developer cãi nhau nhiều lắm. Anh theo chủ nghĩa dễ đọc dễ hiểu code ^^

thanhmssl10 · May 12, 2016, 10:10am

2 sec

a = [1,2,3,9,2,3,4,6,5,7,8,5,6]
a.sort()
print a
print a[-2]

ltd · May 12, 2016, 10:14am

a = [1,2,3,9,2,3,4,6,5,7,8,5,6]

sửa thành

a = [1,2,3,9,9,2,3,4,6,5,7,8,5,6]