脸熟店面挂经

Job Hunting Interview
, , ,
1

I am accessed by their recuiter from Singapore in LinkedIn.
And I passed the 1st round phone screen, the questions mainly focus on the experience I have and management I got, and the project I currently work. The other behavioral questions like what’s the point you like/dislike your current job?

I was scheduled to have technical phone interview with someone in US.

Question:
Add (insert) the mathematical operators + or - (plus or minus) before any of the digits in the decimal numeric string "123456789" such that the resulting mathematical expression adds up to a particular target sum. Return all possible combinations. https://rosettacode.org/wiki/Sum_to_100

Example:
123 + 4 - 5 + 67 - 89 = 100

I started with some easy case,like “1”,“12”…
to analyz how to trace back with subset
to generalize the case, finally i wrote a rough draft function

It took most of time to complete the cases, and when he asked me the complexity of the function I wrote.
I gave wrong answer…but time is up, he didn’t ask me to consider again.

I did my best, it’s still rejected.

This question is similar to https://leetcode.com/problems/expression-add-operators/ except that it do not use “*” here.

2

也报一个

Given an array of numbers, remove the elements according to following conditions

  • remove an element arr[i] if and only if arr[i-1] < arr[i]

You might get the resulting array after removing the elements. Repeat the process until array remains unchanged. Return the number of steps in which the array remains unchanged.

Eg:
[6,3,1,8,9,4,3,2,8,9]

after 1st iteration we get

Step 1: [6,3,1,4,3,2] —> [8,9] is removed since 1<8<9 && 2<8<9
Step 2: [6,3,1,3,2] —> [4] is removed since 1<4
Step 3: [6,3,1,2] —> [3] is removed since 1<3
Step 4: [6,3,1] —> [2] is removed since 1<2

Answer: 4 (Total no. of steps are 4)

3

补充一个

  1. Vertical traverse
    After trying to figure out how to approach the problem for about 20 minutes, my interviewer was nice enough to give me a similar but slightly easier problem: Given a binary tree, print out the sum of each column. So given the above tree, the output should be 1 2 12 6 7
  2. Word searchHow did I approach it?
    ● I mentioned the obvious brute force solution: iterating over the words and comparing each word to the search term passed in. The runtime would be O(array.length * longest_word.length)
    ● Since you can preprocess the array, I tried to sort it in alphabetical order and then perform binary search on the search term, which should speed up the function slightly.
    ● I also tried a hash table implementation which store the first character of the string as the key and the value would be a linked list of all strings that start with that character. However, in the worst case where all words in the array start with the same letter, we would essentially be doing the brute force solution + the work of converting the array into a hash table.
    ● The correct solution involved building a trie containing all the words in the array and then traversing down the trie character by character to see if the search term passed in was contained within that trie. If we reached a leaf node in the trie and the word wasn’t complete, then we simply return false. To account for the wild card, when we get to that character in the trie represented by the wild card, we would simply move onto the next character.