Common algorithms of IOS interview

  • 2020-08-22 22:47:30
  • OfStack

This post shares the common algorithms used in IOS interviews, so let's take a look.

1. Perform descending sort (bubble sort) for the following 1 group of data. "24,17,85,13,9,54,76,45,5,63"


int main(int argc, char *argv[]) {

  int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63};

  int num = sizeof(array)/sizeof(int);

  for(int i = 0; i < num-1; i++) {

    for(int j = 0; j < num - 1 - i; j++) {

      if(array[j] < array[j+1]) {

        int tmp = array[j];

        array[j] = array[j+1];

        array[j+1] = tmp;

      }

    }

  }

  for(int i = 0; i < num; i++) {

    printf("%d", array[i]);

    if(i == num-1) {

      printf("\n");

    }

    else {

      printf(" ");

    }

  }

}

2. Carry out ascending sort (selective sort) for the following 1 group of data. "86, 37, 56, 29, 92, 73, 15, 63, 30, 8"


void sort(int a[],int n)
{

  int i, j, index;

  for(i = 0; i < n - 1; i++) {

    index = i;

    for(j = i + 1; j < n; j++) {

      if(a[index] > a[j]) {

        index = j;

      }

    }

    if(index != i) {

      int temp = a[i];

      a[i] = a[index];

      a[index] = temp;

    }

  }

}

int main(int argc, const char * argv[]) {

  int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};

  sort(numArr, 10);

  for (int i = 0; i < 10; i++) {

    printf("%d, ", numArr[i]);

  }

  printf("\n");

  return 0;

}

3. Quick sort algorithm


void sort(int *a, int left, int right) {

if(left >= right) {

return ;

}

int i = left;

int j = right;

int key = a[left];

while (i < j) {

while (i < j && key >= a[j]) {

j--;

}

a[i] = a[j];

while (i < j && key <= a[i]) {

  i++;

}

a[j] = a[i];

}

a[i] = key;

sort(a, left, i-1);

sort(a, i+1, right);

}

4. Merge sort


void merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) {

  int i = startIndex;

  int j = midIndex + 1;

  int k = startIndex;

  while (i != midIndex + 1 && j != endIndex + 1) {

    if (sourceArr[i] >= sourceArr[j]) {

      tempArr[k++] = sourceArr[j++];

    } else {

      tempArr[k++] = sourceArr[i++];

    }

  }

  while (i != midIndex + 1) {

    tempArr[k++] = sourceArr[i++];

  }

  while (j != endIndex + 1) {

    tempArr[k++] = sourceArr[j++];

  }

  for (i = startIndex; i <= endIndex; i++) {

    sourceArr[i] = tempArr[i];

  }

}


void sort(int souceArr[], int tempArr[], int startIndex, int endIndex) {

  int midIndex;

  if (startIndex < endIndex) {

    midIndex = (startIndex + endIndex) / 2;

    sort(souceArr, tempArr, startIndex, midIndex);

    sort(souceArr, tempArr, midIndex + 1, endIndex);

    merge(souceArr, tempArr, startIndex, midIndex, endIndex);

  }

}


int main(int argc, const char * argv[]) {

  int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};

  int tempArr[10];

  sort(numArr, tempArr, 0, 9);

  for (int i = 0; i < 10; i++) {

    printf("%d, ", numArr[i]);

  }

  printf("\n");

  return 0;

}

5. Implementation of 2-point search algorithm (unlimited programming language)


int bsearchWithoutRecursion(int array[],int low,int high,int target) {

while(low <= high) {

int mid = (low + high) / 2;

if(array[mid] > target)

high = mid - 1;

else if(array[mid] < target)

low = mid + 1;

else  //findthetarget

return mid;

}

//the array does not contain the target

return -1;

}

----------------------------------------

 The recursive implementation 

int binary_search(const int arr[],int low,int high,int key)
{

int mid=low + (high - low) / 2;

if(low > high)

return -1;

else{

if(arr[mid] == key)

return mid;

else if(arr[mid] > key)

return binary_search(arr, low, mid-1, key);

else

return binary_search(arr, mid+1, high, key);

}

}

6, how to achieve the list flip (linked list reverse order)?

Idea: Bring the second element to the front at a time.


#include <stdio.h>

#include <stdlib.h>


typedef struct NODE {

  struct NODE *next;

  int num;

}node;


node *createLinkList(int length) {

  if (length <= 0) {

    return NULL;

  }

  node *head,*p,*q;

  int number = 1;

  head = (node *)malloc(sizeof(node));

  head->num = 1;

  head->next = head;

  p = q = head;

  while (++number <= length) {

    p = (node *)malloc(sizeof(node));

    p->num = number;

    p->next = NULL;

    q->next = p;

    q = p;

  }

  return head;
}


void printLinkList(node *head) {

  if (head == NULL) {

    return;

  }

  node *p = head;

  while (p) {

    printf("%d ", p->num);

    p = p -> next;

  }

  printf("\n");

}


node *reverseFunc1(node *head) {

  if (head == NULL) {

    return head;


  }


  node *p,*q;

  p = head;

  q = NULL;

  while (p) {

    node *pNext = p -> next;

    p -> next = q;

    q = p;

    p = pNext;

  }

  return q;

}


int main(int argc, const char * argv[]) {

  node *head = createLinkList(7);

  if (head) {

    printLinkList(head);

    node *reHead = reverseFunc1(head);

    printLinkList(reHead);

    free(reHead);

  }

  free(head);

  return 0;

}

7. Realize the reverse output of 1 string "how are you" (unlimited programming language). If the given string is "hello world", the output should be "world hello".


int spliterFunc(char *p) {

  char c[100][100];

  int i = 0;

  int j = 0;


  while (*p != '\0') {

    if (*p == ' ') {

      i++;

      j = 0;

    } else {

      c[i][j] = *p;

      j++;

    }

    p++;


  }


  for (int k = i; k >= 0; k--) {

    printf("%s", c[k]);

    if (k > 0) {

      printf(" ");

    } else {

      printf("\n");

    }

  }

  return 0;


}

8. Given a string, output the position of the most prominent character appearing only once in the string? For example "abaccddeeef", the character is b and the output should be 2.


char *strOutPut(char *);


int compareDifferentChar(char, char *);


int main(int argc, const char * argv[]) {


  char *inputStr = "abaccddeeef";

  char *outputStr = strOutPut(inputStr);

  printf("%c \n", *outputStr);

  return 0;

}


char *strOutPut(char *s) {

  char str[100];

  char *p = s;

  int index = 0;

  while (*s != '\0') {

    if (compareDifferentChar(*s, p) == 1) {

      str[index] = *s;

      index++;

    }

    s++;

  }

  return &str;
}


int compareDifferentChar(char c, char *s) {

  int i = 0;

  while (*s != '\0' && i<= 1) {

    if (*s == c) {

      i++;

    }

    s++;
  }

  if (i == 1) {

    return 1;

  } else {

    return 0;

  }

}

9. The first order traversal of the 2-tree is FBACDEGH, and the second order traversal is ABDCEFGH. Please write the result of the second order traversal of the 2-tree.


ADECBHGF

First order + middle order traversal restore 2 tree: first order traversal is: ABDEGCFH in order traversal is: DBGEACHF

First, we get A, which is the root of the two-tree, from the first order. Back to the middle order, we can divide it into three parts:

The middle sequence of left subtree DBGE, root A, and the middle sequence of right subtree CHF

Then, return the sequence of the left subtree to the first order to obtain B as the root. In this way, return to the middle order of the left subtree and divide the left subtree into 3 parts again:

Left subtree D, left subtree root B, right subtree GE

Similarly, you get the root of the right subtree to be C

Similarly divide the right subtree into root C and the right subtree of the right subtree HF, noting that the left subtree is empty

If you only have one leaf and you don't have to do it again, GE and HF do it again, you can restore the two-tree.

Print primes between 2 and 100.


int main(int argc, const char * argv[]) {

  for (int i = 2; i < 100; i++) {

    int r = isPrime(i);

    if (r == 1) {

      printf("%ld ", i);

    }

  }

  return 0;

}


int isPrime(int n)
{

  int i, s;

  for(i = 2; i <= sqrt(n); i++)

    if(n % i == 0) return 0;

  return 1;

}

11. Find the greatest common divisor of two integers.


void sort(int a[],int n)
{

  int i, j, index;

  for(i = 0; i < n - 1; i++) {

    index = i;

    for(j = i + 1; j < n; j++) {

      if(a[index] > a[j]) {

        index = j;

      }

    }

    if(index != i) {

      int temp = a[i];

      a[i] = a[index];

      a[index] = temp;

    }

  }

}

int main(int argc, const char * argv[]) {

  int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};

  sort(numArr, 10);

  for (int i = 0; i < 10; i++) {

    printf("%d, ", numArr[i]);

  }

  printf("\n");

  return 0;

}
0

conclusion

The above are the common algorithm questions and answers that you may encounter in the IOS interview. I hope this article will be helpful to your interview. If you have any questions, please leave a message.


Related articles: