American Immigration Officials Are Now Asking People To Solve Computer Science Problems Before They Enter The Country

If you didn’t pay attention during college lectures, it can come back to bite you when you least expect it.

Immigration officers are now asking people to solve computer science problems to verify their antecedents, claims a Nigerian software engineer. “I was just asked to balance a Binary Search Tree by JFK’s airport immigration,” tweeted Celestine Omin, who’s a based out of Lagos, and was traveling to the US. “I was too tired to think of the BST solution,” he rues, saying that he’d just been on a 23 hour flight.

I was just asked to balance a Binary Search Tree by JFK's airport immigration. Welcome to America.

— Celestine Omin (@cyberomin) February 26, 2017

And it wasn’t just one question out of the blue – Omin says that he was asked around 10 computer science questions to verify if he really was a software engineer. What’s worse, it wasn’t even a trained software engineer quizzing him – he says that if he didn’t give the Wikipedia definition, his answers weren’t deemed to be correct. Omin says was given an A4 sheet to show his steps to the immigration official.

It’s not unusual to have immigration officials asking pointed questions about work and family life while entering the US, but detailed solutions to complex computer science problems are usually not on their checklist. But with increased concerns over terrorism and illegal immigration, American officials are presumably resorting to creative ways to weed out the bad guys. In the process, they’re going to make lots of software engineers very nervous – most engineers would admit that they’d be hard pressed to balance a Binary Search Tree off the cuff. In any case, here’s the solution; you can thank us later.

A Simple Solution is to traverse nodes in Inorder and one by one insert into a self-balancing BST like AVL tree. Time complexity of this solution is O(n Log n) and this solution doesn’t guarantee

An Efficient Solution can construct balanced BST in O(n) time with minimum possible height. Below are steps.

1. Traverse given BST in inorder and store result in an array. This step takes O(n) time. Note that this array would be sorted as inorder traversal of BST always produces sorted sequence.
2. Build a balanced BST from the above created sorted array using the recursive approach discussed here. This step also takes O(n) time as we traverse every element exactly once and processing an element takes O(1) time.